Problem Statement

Two children are playing tag on a number line. (In the game of tag, the child called "it" tries to catch the other child.) The child who is "it" is now at coordinate ~A~ , and he can travel the distance of ~V~ per second. The other child is now at coordinate ~B~ , and she can travel the distance of ~W~ per second.

He can catch her when his coordinate is the same as hers. Determine whether he can catch her within ~T~ seconds (including exactly ~T~ seconds later). We assume that both children move optimally.

Constraints

• ~-10^9 \leq A,B \leq 10^9~
• ~1 \leq V,W \leq 10^9~
• ~1 \leq T \leq 10^9~
• ~A \neq B~
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

~A~ ~V~

~B~ ~W~

~T~

Output

If "it" can catch the other child, print YES ; otherwise, print NO .

Sample Input 1

1 2
3 1
3

Sample Output 1

YES

Sample Input 2

1 2
3 2
3

Sample Output 2

NO

Sample Input 3

1 2
3 3
3

Sample Output 3

NO

Problem Statement

We have ~N~ bulbs arranged on a number line, numbered ~1~ to ~N~ from left to right. Bulb ~i~ is at coordinate ~i~ .

Each bulb has a non-negative integer parameter called intensity. When there is a bulb of intensity ~d~ at coordinate ~x~ , the bulb illuminates the segment from coordinate ~x-d-0.5~ to ~x+d+0.5~ . Initially, the intensity of Bulb ~i~ is ~A_i~ . We will now do the following operation ~K~ times in a row:

• For each integer ~i~ between ~1~ and ~N~ (inclusive), let ~B_i~ be the number of bulbs illuminating coordinate ~i~ . Then, change the intensity of each bulb ~i~ to ~B_i~ .

Find the intensity of each bulb after the ~K~ operations.

Constraints

• ~1 \leq N \leq 2 \times 10^5~
• ~1 \leq K \leq 2 \times 10^5~
• ~0 \leq A_i \leq N~

Input

Input is given from Standard Input in the following format:

~N~ ~K~

~A_1~ ~A_2~ ~\ldots~ ~A_N~

Output

Print the intensity ~A{'}_i~ of each bulb ~i~ after the ~K~ operations to Standard Output in the following format:

~A{'}_1~ ~A{'}_2~ ~\ldots~ ~A{'}_N~

Sample Input 1

5 1
1 0 0 1 0

Sample Output 1

1 2 2 1 2

Initially, only Bulb ~1~ illuminates coordinate ~1~ , so the intensity of Bulb ~1~ becomes ~1~ after the operation. Similarly, the bulbs initially illuminating coordinate ~2~ are Bulb ~1~ and ~2~ , so the intensity of Bulb ~2~ becomes ~2~ .

Sample Input 2

5 2
1 0 0 1 0

Sample Output 2

3 3 4 4 3

Problem Statement

We have a rooted binary tree with ~N~ vertices, where the vertices are numbered ~1~ to ~N~ . Vertex ~1~ is the root, and the parent of Vertex ~i~ ( ~i \geq 2~ ) is Vertex ~\left[ \frac{i}{2} \right]~ .

Each vertex has one item in it. The item in Vertex ~i~ has a value of ~V_i~ and a weight of ~W_i~ . Now, process the following query ~Q~ times:

• Given are a vertex ~v~ of the tree and a positive integer ~L~ . Let us choose some (possibly none) of the items in ~v~ and the ancestors of ~v~ so that their total weight is at most ~L~ . Find the maximum possible total value of the chosen items.

Here, Vertex ~u~ is said to be an ancestor of Vertex ~v~ when ~u~ is an indirect parent of ~v~ , that is, there exists a sequence of vertices ~w_1,w_2,\ldots,w_k~ ( ~k\geq 2~ ) where ~w_1=v~ , ~w_k=u~ , and ~w_{i+1}~ is the parent of ~w_i~ for each ~i~ .

Constraints

• All values in input are integers.
• ~1 \leq N < 2^{18}~
• ~1 \leq Q \leq 10^5~
• ~1 \leq V_i \leq 10^5~
• ~1 \leq W_i \leq 10^5~
• For the values ~v~ and ~L~ given in each query, ~1 \leq v \leq N~ and ~1 \leq L \leq 10^5~ .

Input

Let ~v_i~ and ~L_i~ be the values ~v~ and ~L~ given in the ~i~ -th query. Then, Input is given from Standard Input in the following format:

~N~

~V_1~ ~W_1~

~:~

~V_N~ ~W_N~

~Q~

~v_1~ ~L_1~

~:~

~v_Q~ ~L_Q~

Output

For each integer ~i~ from ~1~ through ~Q~ , the ~i~ -th line should contain the response to the ~i~ -th query.

Sample Input 1

3
1 2
2 3
3 4
3
1 1
2 5
3 5

Sample Output 1

0
3
3

In the first query, we are given only one choice: the item with ~(V, W)=(1,2)~ . Since ~L = 1~ , we cannot actually choose it, so our response should be ~0~ .

In the second query, we are given two choices: the items with ~(V, W)=(1,2)~ and ~(V, W)=(2,3)~ . Since ~L = 5~ , we can choose both of them, so our response should be ~3~ .

Sample Input 2

15
123 119
129 120
132 112
126 109
118 103
115 109
102 100
130 120
105 105
132 115
104 102
107 107
127 116
121 104
121 115
8
8 234
9 244
10 226
11 227
12 240
13 237
14 206
15 227

Sample Output 2

256
255
250
247
255
259
223
253

Problem Statement

Given are ~N~ pairwise distinct non-negative integers ~A_1,A_2,\ldots,A_N~ . Find the number of ways to choose a set of between ~1~ and ~K~ numbers (inclusive) from the given numbers so that the following two conditions are satisfied:

• The bitwise AND of the chosen numbers is ~S~ .
• The bitwise OR of the chosen numbers is ~T~ .

Constraints

• ~1 \leq N \leq 50~
• ~1 \leq K \leq N~
• ~0 \leq A_i < 2^{18}~
• ~0 \leq S < 2^{18}~
• ~0 \leq T < 2^{18}~
• ~A_i \neq A_j~ ( ~1 \leq i < j \leq N~ )

Input

Input is given from Standard Input in the following format:

~N~ ~K~ ~S~ ~T~

~A_1~ ~A_2~ ~...~ ~A_N~

Output

Print the answer.

Sample Input 1

3 3 0 3
1 2 3

Sample Output 1

2

The conditions are satisfied when we choose ~\\{1,2\\}~ or ~\\{1,2,3\\}~ .

Sample Input 2

5 3 1 7
3 4 9 1 5

Sample Output 2

2

Sample Input 3

5 4 0 15
3 4 9 1 5

Sample Output 3

3

Problem Statement

In a two-dimensional plane, we have a rectangle ~R~ whose vertices are ~(0,0)~ , ~(W,0)~ , ~(0,H)~ , and ~(W,H)~ , where ~W~ and ~H~ are positive integers. Here, find the number of triangles ~\Delta~ in the plane that satisfy all of the following conditions:

• Each vertex of ~\Delta~ is a grid point, that is, has integer ~x~ - and ~y~ -coordinates.
• ~\Delta~ and ~R~ shares no vertex.
• Each vertex of ~\Delta~ lies on the perimeter of ~R~ , and all the vertices belong to different sides of ~R~ .
• ~\Delta~ contains at most ~K~ grid points strictly within itself (excluding its perimeter and vertices).

Constraints

• ~1 \leq W \leq 10^5~
• ~1 \leq H \leq 10^5~
• ~0 \leq K \leq 10^5~

Input

Input is given from Standard Input in the following format:

~W~ ~H~ ~K~

Output

Print the answer.

Sample Input 1

2 3 1

Sample Output 1

12

For example, the triangle with the vertices ~(1,0)~ , ~(0,2)~ , and ~(2,2)~ contains just one grid point within itself and thus satisfies the condition.

Sample Input 2

5 4 5

Sample Output 2

132

Sample Input 3

100 100 1000

Sample Output 3

461316

Problem Statement

Count the number of strings ~S~ that satisfy the following constraints, modulo ~10^9 + 7~ .

• The length of ~S~ is exactly ~N~ .
• ~S~ consists of digits ( 0 ... 9 ).
• You are given ~Q~ intervals. For each ~i (1 \leq i \leq Q)~ , the integer represented by ~S[l_i \ldots r_i]~ (the substring of ~S~ between the ~l_i~ -th ( ~1~ -based) character and the ~r_i~ -th character, inclusive) must be a multiple of ~9~ .

Here, the string ~S~ and its substrings may have leading zeroes. For example, 002019 represents the integer ~2019~ .

Constraints

• ~1 \leq N \leq 10^9~
• ~1 \leq Q \leq 15~
• ~1 \leq l_i \leq r_i \leq N~

Input

Input is given from Standard Input in the following format:

~N~

~Q~

~l_1~ ~r_1~

~:~

~l_Q~ ~r_Q~

Output

Print the number of strings that satisfy the conditions, modulo ~10^9 + 7~ .

Sample Input 1

4
2
1 2
2 4

Sample Output 1

136

For example, ~S = ~ 9072 satisfies the conditions because both ~S[1 \ldots 2] = ~ 90 and ~S[2 \ldots 4] = ~ 072 represent multiples of ~9~ .

Sample Input 2

6
3
2 5
3 5
1 3

Sample Output 2

2720

Sample Input 3

20
10
2 15
5 6
1 12
7 9
2 17
5 15
2 4
16 17
2 12
8 17

Sample Output 3

862268030