All submissions for this problem are available.
You are given a simple recursive function f, f(i) = 3*f(i-2) + 4*f(i-1).
You also have an array x of size n with values initialized to 0
Then, you will be given q queries in the form l, r where l <= r. For each i in the range l ≤ i ≤ r, you should increase the value of xi by f(i-l+1).
Atlast, you have to print the array x after q queries. No need to print the array for every query.
First line contains two integers n and q.
Second line contains the values for f(1) and f(2) which is used to build the function f.
The next q lines contains two integers l and r.
Print the final values in the array x in a single line seperated by a space. Since the values can be too large, you should print them modulo 10^9 + 7.
- 1 ≤ n, q ≤ 10^5
- 1 ≤ f(1), f(2) ≤ 10^9
- 1 ≤ l ≤ r ≤ n
Input: 2 2 5 2 1 2 1 2 Output: 10 4
|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, rust, SCALA, swift, 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, kotlin, PERL6, TEXT, SCM chicken, CLOJ, COB, FS|
Fetching successful submissions