Problem Statement

One day, Takahashi got up at exactly B minutes past A o'clock (in 24-hour clock), and Aoki got up at exactly D minutes and 1 second past C o'clock.
If Takahashi got up earlier than Aoki, print Takahashi; otherwise, print Aoki.

Constraints

• 0 \leq A \leq 23
• 0 \leq B \leq 59
• 0 \leq C \leq 23
• 0 \leq D \leq 59
• All values in input are integers.

Sample Input 1

7 0 6 30

Sample Output 1

Aoki

Takahashi got up at 7 sharp, and Aoki got up at 30 minutes and 1 second past 6 o'clock. Aoki was the first to get up, so Aoki should be printed.

Sample Input 2

7 30 7 30

Sample Output 2

Takahashi

Takahashi got up at exactly half past 7, and Aoki got up at 30 minutes and 1 second past 7 o'clock. Just by one second, Takahashi was the first to get up, so Takahashi should be printed.

Sample Input 3

0 0 23 59

Sample Output 3

Takahashi

0:00 in a day is one minute before 0:01, not one minute past 23:59 ("24:00"). Thus, Takahashi was the first to get up, so Takahashi should be printed.

Problem Statement

You are given a string S of even length consisting of lowercase English letters. Let |S| be the length of S, and S_i be the i-th character of S.

Perform the following operation for each i = 1, 2, \ldots, \frac{|S|}{2} in this order, and print the final S.

• Swap S_{2i-1} and S_{2i}.

Constraints

• S is a string of even length consisting of lowercase English letters.
• The length of S is at most 100.

Sample Input 1

abcdef

Sample Output 1

badcfe

Initially, S = abcdef.
Performing the operation for i = 1 swaps S_1 and S_2, making S = bacdef.
Performing the operation for i = 2 swaps S_3 and S_4, making S = badcef.
Performing the operation for i = 3 swaps S_5 and S_6, making S = badcfe.
Thus, badcfe should be printed.

Sample Input 2

aaaa

Sample Output 2

aaaa

Sample Input 3

atcoderbeginnercontest

Sample Output 3

taocedbrgeniencrnoetts

Problem Statement

There are N cities numbered 1, \dots, N, and M roads connecting cities.
The i-th road (1 \leq i \leq M) connects city A_i and city B_i.

Print N lines as follows.

• Let d_i be the number of cities directly connected to city i \, (1 \leq i \leq N), and those cities be city a_{i, 1}, \dots, city a_{i, d_i}, in ascending order.
• The i-th line (1 \leq i \leq N) should contain d_i + 1 integers d_i, a_{i, 1}, \dots, a_{i, d_i} in this order, separated by spaces.

Constraints

• 2 \leq N \leq 10^5
• 1 \leq M \leq 10^5
• 1 \leq A_i \lt B_i \leq N \, (1 \leq i \leq M)
• (A_i, B_i) \neq (A_j, B_j) if (i \neq j).
• All values in the input are integers.

Sample Input 1

6 6
3 6
1 3
5 6
2 5
1 2
1 6

Sample Output 1

3 2 3 6
2 1 5
2 1 6
0
2 2 6
3 1 3 5

The cities directly connected to city 1 are city 2, city 3, and city 6. Thus, we have d_1 = 3, a_{1, 1} = 2, a_{1, 2} = 3, a_{1, 3} = 6, so you should print 3, 2, 3, 6 in the first line in this order, separated by spaces.

Note that a_{i, 1}, \dots, a_{i, d_i} must be in ascending order. For instance, it is unacceptable to print 3, 3, 2, 6 in the first line in this order.

Sample Input 2

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

Sample Output 2

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

Problem Statement

You are given a positive integer N. Print a string of length (N+1), s_0s_1\ldots s_N, defined as follows.

For each i = 0, 1, 2, \ldots, N,

• if there is a divisor j of N that is between 1 and 9, inclusive, and i is a multiple of N/j, then s_i is the digit corresponding to the smallest such j (s_i will thus be one of 1, 2, ..., 9);
• if no such j exists, then s_i is -.

Constraints

• 1 \leq N \leq 1000
• All input values are integers.

Sample Input 1

12

Sample Output 1

1-643-2-346-1

We will explain how to determine s_i for some i.

• For i = 0, the divisors j of N between 1 and 9 such that i is a multiple of N/j are 1, 2, 3, 4, 6. The smallest of these is 1, so s_0 = 1.

• For i = 4, the divisors j of N between 1 and 9 such that i is a multiple of N/j are 3, 6. The smallest of these is 3, so s_4 = 3.

• For i = 11, there are no divisors j of N between 1 and 9 such that i is a multiple of N/j, so s_{11} = -.

Sample Input 2

7

Sample Output 2

17777771

Sample Input 3

1

Sample Output 3

11

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