Problem Statement

In the calendar of AtCoder Kingdom, a year consists of M months from month 1 to month M, and each month consists of D days from day 1 to day D.

What day follows year y, month m, day d in this calendar?

Constraints

• 1000 \leq y \leq 9000
• 1 \leq m \leq M \leq 99
• 1 \leq d \leq D \leq 99
• All input values are integers.

Sample Input 1

12 30
2023 12 30

Sample Output 1

2024 1 1

In the calendar of the kingdom, a year consists of 12 months, and each month consists of 30 days. Thus, the day following year 2023, month 12, day 30 is year 2024, month 1, day 1.

Sample Input 2

36 72
6789 23 45

Sample Output 2

6789 23 46

In the calendar of the kingdom, one year consists of 36 months, and each month consists of 72 days. Thus, the day following year 6789, month 23, day 45 is year 6789, month 23, day 46.

Sample Input 3

12 30
2012 6 20

Sample Output 3

2012 6 21

Problem Statement

There are 4 squares lined up horizontally.

You are given a string S of length 4 consisting of 0 and 1.
If the i-th character of S is 1, there is a person in the i-th square from the left;
if the i-th character of S is 0, there is no person in the i-th square from the left.

Now, everyone will move to the next square to the right simultaneously. By this move, the person who was originally in the rightmost square will disappear.

Determine if there will be a person in each square after the move. Print the result as a string in the same format as S. (See also Sample Input / Output for clarity.)

Constraints

• S is a string of length 4 consisting of 0 and 1.

Sample Input 1

1011

Sample Output 1

0101

After the move, the person who was originally in the 1-st square will move to the 2-nd square,
the person in the 3-rd square to the 4-th square,
and the person in the 4-th square will disappear.

Sample Input 2

0000

Sample Output 2

0000

Sample Input 3

1111

Sample Output 3

0111

Problem Statement

In this problem, an input file contains multiple test cases.
You are first given an integer T. Solve the following problem for T test cases.

• We have N positive integers A_1, A_2, ..., A_N. How many of them are odd?

Constraints

• 1 \leq T \leq 100
• 1 \leq N \leq 100
• 1 \leq A_i \leq 10^9
• All values in the input are integers.

Sample Input 1

4
3
1 2 3
2
20 23
10
6 10 4 1 5 9 8 6 5 1
1
1000000000

Sample Output 1

2
1
5
0

This input contains four test cases.

The second and third lines correspond to the first test case, where N = 3, A_1 = 1, A_2 = 2, A_3 = 3.
We have two odd numbers in A_1, A_2, and A_3, so the first line should contain 2.

Problem Statement

Tiles are aligned in N horizontal rows and N vertical columns. Each tile has a grid with A horizontal rows and B vertical columns. On the whole, the tiles form a grid X with (A\times N) horizontal rows and (B\times N) vertical columns.
For 1\leq i,j \leq N, Tile (i,j) denotes the tile at the i-th row from the top and the j-th column from the left.

Each square of X is painted as follows.

• Each tile is either a white tile or a black tile.
• Every square in a white tile is painted white; every square in a black tile is painted black.
• Tile (1,1) is a white tile.
• Two tiles sharing a side have different colors. Here, Tile (a,b) and Tile (c,d) are said to be sharing a side if and only if |a-c|+|b-d|=1 (where |x| denotes the absolute value of x).

Print the grid X in the format specified in the Output section.

Constraints

• 1 \leq N,A,B \leq 10
• All values in input are integers.

Sample Input 1

4 3 2

Sample Output 1

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

Sample Input 2

5 1 5

Sample Output 2

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

Sample Input 3

4 4 1

Sample Output 3

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

Sample Input 4

1 4 4

Sample Output 4

....
....
....
....

Problem Statement

You are given two strings S and T. Determine whether it is possible to make S equal T by performing the following operation some number of times (possibly zero).

Between two consecutive equal characters in S, insert a character equal to these characters. That is, take the following three steps.

1. Let N be the current length of S, and S = S_1S_2\ldots S_N.
2. Choose an integer i between 1 and N-1 (inclusive) such that S_i = S_{i+1}. (If there is no such i, do nothing and terminate the operation now, skipping step 3.)
3. Insert a single copy of the character S_i(= S_{i+1}) between the i-th and (i+1)-th characters of S. Now, S is a string of length N+1: S_1S_2\ldots S_i S_i S_{i+1} \ldots S_N.

Constraints

• Each of S and T is a string of length between 2 and 2 \times 10^5 (inclusive) consisting of lowercase English letters.

Sample Input 1

abbaac
abbbbaaac

Sample Output 1

Yes

You can make S = abbaac equal T = abbbbaaac by the following three operations.

• First, insert b between the 2-nd and 3-rd characters of S. Now, S = abbbaac.
• Next, insert b again between the 2-nd and 3-rd characters of S. Now, S = abbbbaac.
• Lastly, insert a between the 6-th and 7-th characters of S. Now, S = abbbbaaac.

Thus, Yes should be printed.

Sample Input 2

xyzz
xyyzz

Sample Output 2

No

No sequence of operations makes S = xyzz equal T = xyyzz. Thus, No should be printed.

Problem Statement

You are given strictly increasing sequences of length N and M: A=(A _ 1,A _ 2,\ldots,A _ N) and B=(B _ 1,B _ 2,\ldots,B _ M). Here, A _ i\neq B _ j for every i and j (1\leq i\leq N,1\leq j\leq M).

Let C=(C _ 1,C _ 2,\ldots,C _ {N+M}) be a strictly increasing sequence of length N+M that results from the following procedure.

• Let C be the concatenation of A and B. Formally, let C _ i=A _ i for i=1,2,\ldots,N, and C _ i=B _ {i-N} for i=N+1,N+2,\ldots,N+M.
• Sort C in ascending order.

For each of A _ 1,A _ 2,\ldots,A _ N, B _ 1,B _ 2,\ldots,B _ M, find its position in C. More formally, for each i=1,2,\ldots,N, find k such that C _ k=A _ i, and for each j=1,2,\ldots,M, find k such that C _ k=B _ j.

Constraints

• 1\leq N,M\leq 10^5
• 1\leq A _ 1\lt A _ 2\lt\cdots\lt A _ N\leq 10^9
• 1\leq B _ 1\lt B _ 2\lt\cdots\lt B _ M\leq 10^9
• A _ i\neq B _ j for every i and j (1\leq i\leq N,1\leq j\leq M).
• All values in the input are integers.

Sample Input 1

4 3
3 14 15 92
6 53 58

Sample Output 1

1 3 4 7
2 5 6

C will be (3,6,14,15,53,58,92). Here, the 1-st, 3-rd, 4-th, 7-th elements are from A=(3,14,15,92), and the 2-nd, 5-th, 6-th elements are from B=(6,53,58).

Sample Input 2

4 4
1 2 3 4
100 200 300 400

Sample Output 2

1 2 3 4
5 6 7 8

Sample Input 3

8 12
3 4 10 15 17 18 22 30
5 7 11 13 14 16 19 21 23 24 27 28

Sample Output 3

1 2 5 9 11 12 15 20
3 4 6 7 8 10 13 14 16 17 18 19

Problem Statement

Let us regard an integer k as "similar to 250" if the following condition is satisfied:

• k is represented as k=p \times q^3 with primes p<q.

How many integers less than or equal to N are "similar to 250"?

Constraints

• N is an integer between 1 and 10^{18} (inclusive)

Sample Input 1

250

Sample Output 1

2

• 54 = 2 \times 3^3 is "similar to 250".
• 250 = 2 \times 5^3 is "similar to 250".

The two integers above are all the integers "similar to 250".

Sample Input 2

1

Sample Output 2

0

Sample Input 3

123456789012345

Sample Output 3

226863

Problem Statement

We have a variable X and N kinds of operations that change the value of X. Operation i is represented as a pair of integers (T_i,A_i), and is the following operation:

• if T_i=1, it replaces the value of X with X\ {\rm and}\ A_i;
• if T_i=2, it replaces the value of X with X\ {\rm or}\ A_i;
• if T_i=3, it replaces the value of X with X\ {\rm xor}\ A_i.

Initialize X with the value of C and execute the following procedures in order:

• Perform Operation 1, and then print the resulting value of X.
• Next, perform Operation 1, 2 in this order, and then print the value of X.
• Next, perform Operation 1, 2, 3 in this order, and then print the value of X.
• \vdots
• Next, perform Operation 1, 2, \ldots, N in this order, and then print the value of X.

Constraints

• 1 \leq N \leq 2\times 10^5
• 1\leq T_i \leq 3
• 0\leq A_i \lt 2^{30}
• 0\leq C \lt 2^{30}
• All values in input are integers.

Sample Input 1

3 10
3 3
2 5
1 12

Sample Output 1

9
15
12

The initial value of X is 10.

• Operation 1 changes X to 9.
• Next, Operation 1 changes X to 10, and then Operation 2 changes it to 15.
• Next, Operation 1 changes X to 12, and then Operation 2 changes it to 13, and then Operation 3 changes it to 12.

Sample Input 2

9 12
1 1
2 2
3 3
1 4
2 5
3 6
1 7
2 8
3 9

Sample Output 2

0
2
1
0
5
3
3
11
2

Problem Statement

There are N cities numbered 1 through N, and M buses that go between these cities. The i-th bus (1 \leq i \leq M) departs from City A_i at time S_i+0.5 and arrive at City B_i at time T_i+0.5.

Takahashi will travel between these N cities. When he is in City p at time t, he will do the following.

1. If there is a bus that departs from City p not earlier than time t, take the bus that departs the earliest among those buses to get to another city.
2. If there is no such bus, do nothing and stay in City p.

Takahashi repeats doing the above until there is no bus to take. It is guaranteed that all M buses depart at different times, so the bus to take is always uniquely determined. Additionally, the time needed to change buses is negligible.

Here is your task: process Q queries, the i-th (1 \leq i \leq Q) of which is as follows.

• If Takahashi begins his travel in City Y_i at time X_i, in which city or on which bus will he be at time Z_i?

Constraints

• 2 \leq N \leq 10^5
• 1 \leq M \leq 10^5
• 1 \leq Q \leq 10^5
• 1 \leq A_i,B_i \leq N\ (1 \leq i \leq M)
• A_i \neq B_i\ (1 \leq i \leq M)
• 1 \leq S_i \lt T_i \leq 10^9\ (1 \leq i \leq M)
• S_i \neq S_j\ (i \neq j)
• 1 \leq X_i \lt Z_i \leq 10^9\ (1 \leq i \leq Q)
• 1 \leq Y_i \leq N\ (1 \leq i \leq Q)
• All values in input are integers.

Sample Input 1

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

Sample Output 1

2 3
2
3

In the first query, Takahashi will travel as follows.

1. Start in City 1 at time 1.
2. Take the bus that departs from City 1 at time 1.5 and arrives at City 2 at time 3.5.
3. Take the bus that departs from City 2 at time 3.5 and arrives at City 3 at time 5.5.
4. Since no bus departs from City 3 at time 5.5 or later, stay in City 3 (forever).

At time 5, he will be on the bus that departs from City 2 and arrives at City 3. Thus, as specified in the Output section, we should print 2 and 3 with a space between them.

Sample Input 2

8 10 10
4 3 329982133 872113932
6 8 101082040 756263297
4 7 515073851 793074419
8 7 899017043 941751547
5 7 295510441 597348810
7 2 688716395 890599546
6 1 414221915 748470452
6 4 810915860 904512496
3 1 497469654 973509612
4 1 307142272 872178157
374358788 4 509276232
243448834 6 585993193
156350864 4 682491610
131643541 8 836902943
152874385 6 495945159
382276121 1 481368090
552433623 2 884584430
580376205 2 639442239
108790644 7 879874292
883275610 1 994982498

Sample Output 2

4
6 1
4 1
8
6 1
1
2
2
7 2
1