Problem Statement

There are N people in an xy-plane. Person i is at (X_i, Y_i). The positions of all people are different.

We have a string S of length N consisting of L and R.
If S_i = R, Person i is facing right; if S_i = L, Person i is facing left. All people simultaneously start walking in the direction they are facing. Here, right and left correspond to the positive and negative x-direction, respectively.

For example, the figure below shows the movement of people when (X_1, Y_1) = (2, 3), (X_2, Y_2) = (1, 1), (X_3, Y_3) =(4, 1), S = RRL.

We say that there is a collision when two people walking in opposite directions come to the same position. Will there be a collision if all people continue walking indefinitely?

Constraints

• 2 \leq N \leq 2 \times 10^5
• 0 \leq X_i \leq 10^9
• 0 \leq Y_i \leq 10^9
• (X_i, Y_i) \neq (X_j, Y_j) if i \neq j.
• All X_i and Y_i are integers.
• S is a string of length N consisting of L and R.

Sample Input 1

3
2 3
1 1
4 1
RRL

Sample Output 1

Yes

This input corresponds to the example in the Problem Statement.
If all people continue walking, Person 2 and Person 3 will collide. Thus, Yes should be printed.

Sample Input 2

2
1 1
2 1
RR

Sample Output 2

No

Since Person 1 and Person 2 walk in the same direction, they never collide.

Sample Input 3

10
1 3
1 4
0 0
0 2
0 4
3 1
2 4
4 2
4 4
3 3
RLRRRLRLRR

Sample Output 3

Yes

Problem Statement

You are given positive integers N and Q, and a string S of length N consisting of lowercase English letters.

Process Q queries. Each query is of one of the following two types.

• 1 x: Perform the following x times in a row: delete the last character of S and append it to the beginning.
• 2 x: Print the x-th character of S.

Constraints

• 2 \le N \le 5 \times 10^5
• 1 \le Q \le 5 \times 10^5
• 1 \le x \le N
• |S|=N
• S consists of lowercase English letters.
• At least one query in the format 2 x.
• N, Q, x are all integers.

Sample Input 1

3 3
abc
2 2
1 1
2 2

Sample Output 1

b
a

In the 1-st query, S is abc, so the 2-nd character b should be printed. In the 2-nd query, S is changed from abc to cab. In the 3-rd query, S is cab, so the 2-nd character a should be printed.

Sample Input 2

10 8
dsuccxulnl
2 4
2 7
1 2
2 7
1 1
1 2
1 3
2 5

Sample Output 2

c
u
c
u

Problem Statement

A polyomino is a puzzle piece in the shape of a connected polygon made by connecting several squares by their edges.

There is a grid with four rows and four columns, and three polyominoes that fit within the grid.
The shape of the i-th polyomino is represented by 16 characters P_{i,j,k} (1 \leq j, k \leq 4). They describe the state of the grid when the i-th polyomino is placed on it. If P_{i, j, k} is #, the square at the j-th row from the top and k-th column from the left is occupied by the polyomino; if it is ., the square is not occupied. (Refer to the figures at Sample Input/Output 1.)

You want to fill the grid with all three polyominoes so that all of the following conditions are satisfied.

• All squares of the grid are covered by the polyominoes.
• The polyominoes must not overlap each other.
• The polyominoes must not stick out of the grid.
• The polyominoes may be freely translated and rotated but may not be flipped over.

Can the grid be filled with the polyominoes to satisfy these conditions?

Constraints

• P_{i, j, k} is # or ..
• The given polyominoes are connected. In other words, the squares that make up a polyomino can be reached from each other by following only the squares up, down, left, and right.
• The given polyominoes are not empty.

Sample Input 1

....
###.
.#..
....
....
.###
.##.
....
..#.
.##.
.##.
.##.

Sample Output 1

Yes

The figure below shows the shapes of the polyominoes corresponding to Sample Input 1.

In this case, you can fill the grid with them to satisfy the conditions in the problem statement by placing them as shown in the figure below.

Thus, the answer is Yes.

Sample Input 2

###.
#.#.
##..
....
....
..#.
....
....
####
##..
#...
#...

Sample Output 2

Yes

As in the first polyomino in Sample Input 2, a polyomino may be in the shape of a polygon with a hole.

Sample Input 3

##..
#..#
####
....
....
##..
.##.
....
.#..
.#..
.#..
.#..

Sample Output 3

No

Note that the polyominoes may not be flipped over when filling the grid.

Sample Input 4

....
..#.
....
....
....
..#.
....
....
....
..#.
....
....

Sample Output 4

No

Sample Input 5

....
####
#...
#...
....
####
...#
..##
....
..##
..#.
..##

Sample Output 5

No

Sample Input 6

###.
.##.
..#.
.###
....
...#
..##
...#
....
#...
#...
#...

Sample Output 6

Yes

Problem Statement

There is a tree with N vertices numbered 1 to N. For each i\ (2 \leq i \leq N), there is an edge connecting vertex i and vertex \lfloor \frac{i}{2} \rfloor. There are no other edges.

In this tree, find the number of vertices whose distance from vertex X is K. Here, the distance between two vertices u and v is defined as the number of edges in the simple path connecting vertices u and v.

You have T test cases to solve.

Constraints

• 1\leq T \leq 10^5
• 1\leq N \leq 10^{18}
• 1\leq X \leq N
• 0\leq K \leq N-1
• All input values are integers.

Sample Input 1

5
10 2 0
10 2 1
10 2 2
10 2 3
10 2 4

Sample Output 1

1
3
4
2
0

The tree for N=10 is shown in the following figure.

Here,

• There is 1 vertex, 2, whose distance from vertex 2 is 0.
• There are 3 vertices, 1,4,5, whose distance from vertex 2 is 1.
• There are 4 vertices, 3,8,9,10, whose distance from vertex 2 is 2.
• There are 2 vertices, 6,7, whose distance from vertex 2 is 3.
• There are no vertices whose distance from vertex 2 is 4.

Sample Input 2

10
822981260158260522 52 20
760713016476190629 2314654 57
1312150450968417 1132551176249851 7
1000000000000000000 1083770654 79
234122432773361868 170290518806790 23
536187734191890310 61862 14
594688604155374934 53288633578 39
1000000000000000000 120160810 78
89013034180999835 14853481725739 94
463213054346948152 825589 73

Sample Output 2

1556480
140703128616960
8
17732923532771328
65536
24576
2147483640
33776997205278720
7881299347898368
27021597764222976

Problem Statement

You are planning to travel from coordinate 0 to coordinate X_N on a number line, then turn around and return to coordinate 0. Here, you can only move in the positive direction on the outbound trip and in the negative direction on the return trip.
You will travel by car. The car consumes one liter of fuel for every unit distance it travels. You can carry up to H liters of fuel and cannot move without fuel.
For each i = 1, 2, \ldots, N-1, there is a gas station at coordinate X_i, where you can get F_i liters of fuel for P_i yen. However, you cannot carry more than H liters of fuel. More precisely, if you have x liters of fuel and use the gas station at coordinate X_i, you must pay P_i yen, and your amount of fuel becomes \min(x + F_i, H) liters. Each gas station can be used at most once in total during the round trip.
Determine if you can achieve this plan when you initially have H liters of fuel, and if it is possible, find the minimum amount of money required.

Constraints

• 1 \leq N, H \leq 300
• 0 < X_1 < X_2 < \ldots < X_N \leq 10^5
• 1 \leq P_i \leq 10^5
• 1 \leq F_i \leq H
• All input values are integers.

Sample Input 1

4 10
2 5 9 11
8 10
5 8
4 9

Sample Output 1

9

You can achieve the plan by using the gas station at coordinate 5 on the outbound trip and the one at coordinate 9 on the return trip, paying a total of 9 yen.
It is impossible to achieve the plan by paying 8 yen or less. Note that you cannot use the same gas station on both the outbound and return trips.

Sample Input 2

1 1
100000

Sample Output 2

-1

Sample Input 3

5 20
4 13 16 18 23
1 16
2 8
4 11
8 13

Sample Output 3

13