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
De Prezer loves palindrome strings. A string s1s2...sn is palindrome if and only if it is equal to its reverse.
De Prezer also loves queries.
You are given string s of length n and m queries. There are 3 types of queries :
1. 1 p x : Modify sp = x where 1 ≤ p ≤ n and x is a lower case English letter.
2. 2 p : Print the length of the largest palindrome substring of s like slsl + 1...sr such that l ≤ p ≤ r and r - p = p - l. (1 ≤ p ≤ n)
3. 3 p : Print the length of the largest palindrome substring of s like slsl + 1...sr such that l ≤ p and p + 1 ≤ r and r - p - 1 = p - l. (1 ≤ p ≤ n - 1) or - 1 if there is no such substring.
The first line of input contains s and m.
Next m lines contain queries.
1 ≤ n, m ≤ 105
s only contains lower case English letters.
For each query of type 2 and 3 print the answer in a single line.
abcd 3
3 1
1 2 c
3 2
-1
2
abcba 6
2 3
1 3 b
2 3
3 2
1 1 b
3 2
5
5
2
4
De Prezer loves trees. A tree of order n is a connected graph with n vertexes and n - 1 edges.
De Prezer also loves query.
De Prezer has a weighted tree of order n (each edge has a length). The distance between two vertexes is the sum of length of edges between them and we show it by d(v, u) (distance between vertexes u and v).
De Prezer ask you to perform q queries on this tree.
Each query gives you numbers v, l and you should tell him the number of vertexes like u such that d(v, u) ≤ l (including v itself).
The first line of input contains integers n and q .
The next n - 1 lines contain edges. Each line contains an edge a, b, w, two endpoints and the weight.
The next q lines, contain queries.
1 ≤ n, q ≤ 105
1 ≤ v ≤ n
1 ≤ l ≤ 1014
1 ≤ a, b ≤ n
1 ≤ w ≤ 109
For each query, print a single integer in a single line.
4 6
1 2 3
2 3 10
3 4 51
1 2
1 10
3 30
3 51
2 60
2 61
1
2
3
4
3
4
5 5
1 2 100
1 3 100
1 4 10
1 5 200
1 99
1 199
1 299
4 100
4 110
2
4
5
2
4