All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
The Mock Turtle went to the ocean's school to become a true turtle! However instead of practicing the usual operations of addition, subtraction and division taught by the lecturers, she was always playing with parentheses.
A parentheses is defined using the following rules:
- An empty string is a parentheses.
- If X is a parentheses, then (X) is also a parentheses
- If X and Y are parentheses, then XY is also a parentheses
- Every parentheses can be created using the previous rules only.
A parentheses contains k blocks if it can be represented as the concatenation of exactly k non empty parentheses, but can not be represented as the concatenation of more than k non empty parentheses. For example ()(()) contains two blocks (i.e. () and (())) and (()()) contains just one block.
Every time Alice meets with the Mock Turtle they create two arrays of integers a and b both of length N, and play the following game T times: First Alice thinks of two integers L and R, then the Mock Turtle chooses two integers i, j such that L ≤ i, j ≤ R and builds all the parentheses of length ai that contains bj blocks. Since the Mock Turtle loves building parentheses, she will choose i, j in such a way that number of parentheses of length ai that contains bj blocks are maximized.
The first line of the input contains two integers N, T .
The following two lines containing N space separated integers representing the elements of array a and b respectively.
Then follows T lines, each one have two integers L and R representing one game.
For each game, output a single line containing the answer to the problem, since this number can be very large print it modulo 109+7.
- 1 ≤ N, T ≤ 105
- 1 ≤ ai, bi ≤ 2·105, ai is even
- 1 ≤ L ≤ R ≤ N
Input: 5 2 4 6 2 4 8 3 3 3 3 3 2 4 1 5 Output: 1 3
In the first query the Mock Turtle can build only the parentheses ()()()
In the second query the three possible parentheses are
|Tags||alei, catalan, combinatorics, cook73, medium|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.