401909: GYM100571 B Troynacci Query

De Prezer loves functions. He has invented a new function f named Troynacci .

f(1) and f(2) are given to you. If i > 2, f(i) = af(i - 2) + bf(i - 1) .

De Prezer also has got a sequence x₁, x₂, ..., x_n .

De Prezer 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 x_i 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 10⁹ + 7 .

The first line of input contains two integers n and q.

The second line contains two integers f(1) and f(2) .

The third line of input contains two integers a and b .

The forth line of input contains n space separated integers x₁, x₂, ..., x_n .

The next q lines, each line contains two integers l and r .

1 ≤ n, q ≤ 10⁵

1 ≤ f(1), f(2), a, b ≤ 10⁹

0 ≤ x_i ≤ 10⁹ (for each 1 ≤ i ≤ n)

Print the final sequence in a single line.

6 6
1 1
1 1
0 0 0 0 0 0
1 6
1 1
4 5
2 2
4 4
5 6

2 2 2 5 7 9