Problem Statement

When you asked some guy in your class his name, he called himself S, where S is a string of length between 3 and 20 (inclusive) consisting of lowercase English letters. You have decided to choose some three consecutive characters from S and make it his nickname. Print a string that is a valid nickname for him.

Constraints

• 3 \leq |S| \leq 20
• S consists of lowercase English letters.

Sample Input 1

takahashi

Sample Output 1

tak

Sample Input 2

naohiro

Sample Output 2

nao

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.

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

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.

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)

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

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