问题2474--Daliwa2474: Daliwa
时间限制: 1 Sec 内存限制: 256 MB
提交: 6 解决: 1
[提交] [状态] [讨论版] [命题人:]题目描述
Daw found a function f named Daliwa.
f(1) and f(2) are given to you. If i > 2, f(i) = af(i-2) + bf(i-1).
Daw also has got a sequence x1, x2, ……, xn.
Daw also loves query. So he gives you q queries. In each query, he gives you numbers l and r(l ⩽ r) and for each i that l ⩽ i ⩽ r, you should increase xi by f(i - l + 1).
At last, you should print the final sequence. Of course, members of sequence could be very large, so you should print them modulo 109 + 7.
输入
The input contains multiple test cases. The first line of input contain a integers T, the number of cases.
The first line of each cases of input contains two integers n and q.
The second line contains two integers f(1) and f(2).
The thrid line of input contains two integers a and b.
The forth line of input contains n space separated integers x1, x2, ……, xn.
The next q lines, each line contains two integers l and r.
1 ⩽ n, q ⩽ 105
1 ⩽ f(1), f(2), a, b ⩽ 109
0 ⩽ xi ⩽ 109(1 ⩽ i ⩽ n)
The number of n for all tests must not exceed 200000
The number of q for all tests must not exceed 200000
输出
For each cases, print the final sequence in a single line.
样例输入
2
6 6
1 1
1 1
0 0 0 0 0 0
1 6
1 1
4 5
2 2
4 4
5 6
4 2
1 2
3 4
2 3 4 5
2 4
1 3
样例输出
2 2 2 5 7 9
3 6 17 16
来源/分类
[提交] [状态]