De Prezer loves movies and series. He has watched the Troy for like 100 times and also he is a big fan of Supernatural series.So, he did some researches and found a cursed object which had n lights on it and initially all of them were turned off.Because of his love to the Troy, he called that object Troy.
He looked and saw a note on it in Khikulish (language of people of Khikuland): "Ma in hame rah umadim, hala migi ... ? ... Mage man De Prezer am k mikhay mano ... ? .... Man se sale ... To boro .... beshur manam miram ... o mishuram".
He doesn't know Khikulish, so just ignored the note and tested the Troy.
He realized that the light number i stays turned on for exactly ai seconds, and then it turns itself off (if it is turned on, in time t, in time t + ai - 1 it will be turned on, but on time t + ai it won't be) and the next light will be turned on (if i < n, next light is the light number i + 1, otherwise it is light with number 1).
For example if n = 2 and we turn on the first light in time 0, it will be turned on in hole interval [0, a1) and in hole interval [a1, a1 + a2) the second light will be turned on and so on.
In time 0 he turns on the light number 1.
De Prezer also loves query.So he gives you q queries.In each query he will give you integer t (the time a revengeful ghost attacked him) and you should print the number of the light that is turned on, in time t.
The first line of input contains two integers n and q.
The second line contains n space separated integers, a1, a2, ..., an .
The next q lines, each line contains a single integer t .
1 ≤ n, q ≤ 105
1 ≤ ai ≤ 109
1 ≤ t ≤ 1018
For each query, print the answer in one line.
5 7
1 2 3 4 5
1
2
3
7
14
15
16
2
2
3
4
5
1
2
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 x1, x2, ..., xn .
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 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 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 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 (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
De Prezer loves lcm (Least Common Multiple).Ha has got a sequence a1, a2, ..., an but doesn't know how to calculate lcm of two numbers.
De Prezer also loves query.So he asks you to answer to m queries on this sequence.
In each query, he gives you number x and you should print the following number :
lcm(ai, ai + 1, ..., ai + x - 1)
Answer can be very large, so print it modulo 109 + 7 .
The first line of input consists of 2 integers n and m.
The second line of input contains n space separated integers a1, a2, ..., an.
The next m lines, each line contains an integer x.
1 ≤ n ≤ 2 * 104
1 ≤ m ≤ 106
1 ≤ ai ≤ 60 (For each 1 ≤ i ≤ n)
1 ≤ x ≤ n
Print m lines, each answer to one query.
5 5
1 2 3 4 5
1
2
3
4
5
1
2
6
12
60
5 5
2 3 1 4 5
1
2
3
4
5
1
3
6
12
60
De Prezer loves troyic paths.Consider we have a graph with n vertices and m edges.Edges are directed in one way.And there is at most one edge from any vertex to any other vertex.If there is an edge from v to u, then c(v, u) is its color and w(v, u) is its length.Otherwise,c(v, u) = w(v, u) = - 1.
A sequence p1, p2, ..., pk is a troyic path is and only if for each 1 ≤ i ≤ k, 1 ≤ pi ≤ n and if i < k, then c(pi, pi + 1) > - 1 and if i + 1 < k, then c(pi, pi + 1) ≠ c(pi + 1, pi + 2) .
The length of such troyic path is 
and it's called a p1 - pk path.
In such graph, length of the shortest path from vertex v to u is the minimum length of all v - u paths.(The length of the shortest path from any vertex to itself equals 0)
De Prezer gives you a graph like above and a vertex s.
De Prezer also loves query. So he gives you q queries and in each query, gives you number t and you should print the length of the shortest path from s to t (or - 1 if there is no troyic path from s to t)
The first line of input contains three integers n and m and C, the number of vertices, the numbers of edges and the number of valid colors.
The next m lines, each line contains 4 integers v, u, w(v, u), c(v, u) (1 ≤ v, u ≤ n and v ≠ u and 1 ≤ w(v, u) ≤ 109 and 1 ≤ c(v, u) ≤ C).
The line after that contains integer s and q.
The next q lines, each line contains information of one query, number t.
1 ≤ n, m, C, q ≤ 105
m ≤ n(n - 1)
1 ≤ s, t ≤ n
For each query, print the answer.
5 4 1000
1 2 10 1
2 3 10 2
3 4 10 2
4 5 10 1
1 5
1
2
3
4
5
0
10
20
-1
-1
5 5 2
1 2 10 1
2 3 10 2
3 4 10 1
4 5 10 2
1 5 39 1
1 5
1
2
3
4
5
0
10
20
30
39
De Prezer loves rectangles.He has a n × m rectangle which there is a number in each of its cells. We show the number in the j - th column of the i - th row by ai, j.
De Prezer also loves query. So he gives you q queries. In each query, he gives you number k and asks you to print the number of subrectangles of this rectangle that the difference between the maximum element and the minimum element in them is at most k .
The first line of input contains 3 integers, n, m and q .
In the next n lines, there are informations of the rectangle. i - th line among them, contains m space separated integers, ai, 1, ai, 2, ..., ai, m .
The next q lines, each line contains a single integer k (for that query).
1 ≤ n, m ≤ 400
1 ≤ q ≤ 10
1 ≤ ai, j ≤ 109 (for each 1 ≤ i ≤ n and 1 ≤ j ≤ m)
0 ≤ k ≤ 109 (for each query)
For each query, print the answer in a single line.
5 4 6
451 451 452 452
452 452 452 452
451 452 450 450
451 451 451 451
452 452 450 450
0
2
773726
724963313
1
1
42
150
150
150
88
88
4 5 8
1314 1287 1286 1290 1295
1278 1271 1324 1317 1289
1305 1305 1284 1300 1309
1318 1296 1301 1274 1315
976296835
12
13
38
16
40
665711658
35
150
34
35
82
37
92
150
77
De Prezer loves TROYs. A TROY is a 1018 × 1018 square and there is either + 1 or - 1 in each cell of this square (actually it's a grid).
There are two types of operation :
1. Multiply all numbers in a row by - 1 .
2. Multyply all numbers in a column by - 1 .
De Prezer has found two TROYs, the number in the j - th column of the i - th row of the first TROY is ai, j and in the second TROY is bi, j .
De Prezer also loves query, so he gives you some queries.
First of all, you don't have any information about numbers in these two TROYs. Each query, gives the values x ,y, ax, y, bx, y (that you didn't get before), and you should tell him if it is can be possible to transform the first TROY to the second one (the values in the cells that we don't know, could be the way that we can transform the first TROY to the second one) using the operations above, with the information you got so far.
The first line of input contains integer n, the number of queries.
Each of the next n lines, contain 4 integers x ,y, ax, y, bx, y .
1 ≤ n ≤ 105
1 ≤ x, y ≤ 1018 and 
For each query, print a single string in a line, "Yes" or "No" (Without quotes).
3
829054240386762533 576622723736087196 +1 -1
659693256240999920 576622723736087196 +1 +1
395697514003384346 576622723736087196 +1 +1
Yes
Yes
Yes
4
1 1 +1 -1
1 2 +1 -1
2 1 +1 -1
2 2 +1 +1
Yes
Yes
Yes
No