Problem Statement

You are given N integers A_1, A_2, \dots, A_N. Also, define B_i = A_i \times A_{i+1}\ (1 \leq i \leq N-1).

Print B_1, B_2, \dots, B_{N-1} in this order, separated by spaces.

Constraints

• 2 \leq N \leq 100
• 1 \leq A_i \leq 100
• All input values are integers.

Sample Input 1

3
3 4 6

Sample Output 1

12 24

We have B_1 = A_1 \times A_2 = 12, B_2 = A_2 \times A_3 = 24.

Sample Input 2

5
22 75 26 45 72

Sample Output 2

1650 1950 1170 3240

Problem Statement

AtCoder Inc. sells merchandise through its online shop.

Takahashi has decided to purchase N types of products from there.
For each integer i from 1 to N, the i-th type of product has a price of P_i yen each, and he will buy Q_i of this.

Additionally, he must pay a shipping fee.
The shipping fee is 0 yen if the total price of the products purchased is S yen or above, and K yen otherwise.

He will pay the total price of the products purchased plus the shipping fee.
Calculate the amount he will pay.

Constraints

• 1\leq N\leq 100
• 1\leq S\leq 10000
• 1\leq K\leq 10000
• 1\leq P_i\leq 10000
• 1\leq Q_i\leq 100
• All input values are integers.

Sample Input 1

2 2000 500
1000 1
100 6

Sample Output 1

2100

Takahashi buys one product for 1000 yen and six products for 100 yen each.
Thus, the total price of the products is 1000\times 1+100\times 6=1600 yen.
Since the total amount for the products is less than 2000 yen, the shipping fee will be 500 yen.
Therefore, the amount Takahashi will pay is 1600+500=2100 yen.

Sample Input 2

3 2000 500
1000 1
100 6
5000 1

Sample Output 2

6600

The total price of the products is 1000\times 1+100\times 6+5000\times 1=6600 yen.
Since the total amount for the products is not less than 2000 yen, the shipping fee will be 0 yen.
Therefore, the amount Takahashi will pay is 6600+0=6600 yen.

Sample Input 3

2 2000 500
1000 1
1000 1

Sample Output 3

2000

There may be multiple products with the same price per item.

Problem Statement

There are N platforms arranged in a row. The height of the i-th platform from the left is H_i.

Takahashi is initially standing on the leftmost platform.

Since he likes heights, he will repeat the following move as long as possible.

• If the platform he is standing on is not the rightmost one, and the next platform to the right has a height greater than that of the current platform, step onto the next platform.

Find the height of the final platform he will stand on.

Constraints

• 2 \leq N \leq 10^5
• 1 \leq H_i \leq 10^9
• All values in input are integers.

Sample Input 1

5
1 5 10 4 2

Sample Output 1

10

Takahashi is initially standing on the leftmost platform, whose height is 1. The next platform to the right has a height of 5 and is higher than the current platform, so he steps onto it.

He is now standing on the 2-nd platform from the left, whose height is 5. The next platform to the right has a height of 10 and is higher than the current platform, so he steps onto it.

He is now standing on the 3-rd platform from the left, whose height is 10. The next platform to the right has a height of 4 and is lower than the current platform, so he stops moving.

Thus, the height of the final platform Takahashi will stand on is 10.

Sample Input 2

3
100 1000 100000

Sample Output 2

100000

Sample Input 3

4
27 1828 1828 9242

Sample Output 3

1828

Problem Statement

You are given N strings of length six each, consisting of digits. Let S_i be the i-th (i = 1, 2, \dots, N) of them.

You are also given M strings of length three each, consisting of digits. Let T_j be the j-th (j = 1, 2, \dots, M) of them.

Find the number of strings among S_1, S_2, \dots, S_N whose last three characters coincide with one or more of T_1, T_2, \dots, T_M.

Constraints

• 1 \leq N, M \leq 1000
• N and M are integers.
• S_i is a string of length 6 consisting of digits, for all i = 1, 2, \dots, N.
• T_j is a string of length 3 consisting of digits, for all j = 1, 2, \dots, M.

Sample Input 1

3 3
142857
004159
071028
159
287
857

Sample Output 1

2

The last three characters of S_1 are 857, which coincide with T_3.
The last three characters of S_2 are 159, which coincide with T_1.
The last three characters of S_3 are 028, which do not coincide with T_1, T_2, or T_3.

Thus, the answer is 2.

Sample Input 2

5 4
235983
109467
823476
592801
000333
333
108
467
983

Sample Output 2

3

Sample Input 3

4 4
000000
123456
987111
000000
000
111
999
111

Sample Output 3

3

Problem Statement

There are N people numbered 1, 2, \ldots, N on a two-dimensional plane, and person i is at the point represented by the coordinates (X_i,Y_i).

Person 1 has been infected with a virus. The virus spreads to people within a distance of D from an infected person.

Here, the distance is defined as the Euclidean distance, that is, for two points (a_1, a_2) and (b_1, b_2), the distance between these two points is \sqrt {(a_1-b_1)^2 + (a_2-b_2)^2}.

After a sufficient amount of time has passed, that is, when all people within a distance of D from person i are infected with the virus if person i is infected, determine whether person i is infected with the virus for each i.

Constraints

• 1 \leq N, D \leq 2000
• -1000 \leq X_i, Y_i \leq 1000
• (X_i, Y_i) \neq (X_j, Y_j) if i \neq j.
• All input values are integers.

Sample Input 1

4 5
2 -1
3 1
8 8
0 5

Sample Output 1

Yes
Yes
No
Yes

The distance between person 1 and person 2 is \sqrt 5, so person 2 gets infected with the virus.
Also, the distance between person 2 and person 4 is 5, so person 4 gets infected with the virus.
Person 3 has no one within a distance of 5, so they will not be infected with the virus.

Sample Input 2

3 1
0 0
-1000 -1000
1000 1000

Sample Output 2

Yes
No
No

Sample Input 3

9 4
3 2
6 -1
1 6
6 5
-2 -3
5 3
2 -3
2 1
2 6

Sample Output 3

Yes
No
No
Yes
Yes
Yes
Yes
Yes
No

Problem Statement

For a non-negative integer K, we define a level-K carpet as follows:

• A level-0 carpet is a 1 \times 1 grid consisting of a single black cell.
• For K > 0, a level-K carpet is a 3^K \times 3^K grid. When this grid is divided into nine 3^{K-1} \times 3^{K-1} blocks:
  • The central block consists entirely of white cells.
  • The other eight blocks are level-(K-1) carpets.

You are given a non-negative integer N.
Print a level-N carpet according to the specified format.

Constraints

• 0 \leq N \leq 6
• N is an integer.

Sample Input 1

1

Sample Output 1

###
#.#
###

A level-1 carpet is a 3 \times 3 grid as follows:

When output according to the specified format, it looks like the sample output.

Sample Input 2

2

Sample Output 2

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

A level-2 carpet is a 9 \times 9 grid.

Problem Statement

The Republic of AtCoder has N cities numbered 1 through N and N-1 roads numbered 1 through N-1. Road i connects City A_i and City B_i bidirectionally. It is guaranteed that one can travel between every pair of cities using roads.

Takahashi will depart City 1 and have a journey by repeating the following.

• If there are unvisited cities that are directly connected to the city Takahashi is in now, he goes to the city with the smallest number among those cities.
• Otherwise,
  • if he is in City 1, he ends the journey;
  • otherwise, he goes to the city he was in just before visiting the current city for the first time.

Find the sequence of cities visited by Takahashi in the order he visits them.

Constraints

• 2 \leq N \leq 2\times 10^5
• 1\leq A_i,B_i \leq N
• It is possible to travel between every pair of cities using roads.

Sample Input 1

4
1 2
4 2
3 1

Sample Output 1

1 2 4 2 1 3 1

His journey will be as follows.

• Start in City 1.
• The unvisited cities directly connected to City 1 are City 2 and 3. Go to the city with the smaller number, that is, City 2.
• The unvisited city directly connected to City 2 is City 4. Go there.
• There is no unvisited city directly connected to City 4. Go back to City 2.
• There is no unvisited city directly connected to City 2. Go to City 1, where he was in just before visiting City 2 for the first time.
• The unvisited city directly connected to City 1 is City 3. Go there.
• There is no unvisited city directly connected to City 3. Go back to City 1.
• There is no unvisited city directly connected to City 1. End the journey.

Sample Input 2

5
1 2
1 3
1 4
1 5

Sample Output 2

1 2 1 3 1 4 1 5 1

Problem Statement

Person 0, Person 1, \ldots, and Person (N-1) are sitting around a turntable in counterclockwise order, evenly spaced. Dish p_i is in front of Person i on the table.
You may perform the following operation 0 or more times:

• Rotate the turntable by one N-th of a counterclockwise turn. The dish that was in front of Person i right before the rotation is now in front of Person (i+1) \bmod N.

When you are finished, Person i gains frustration of k, where k is the minimum integer such that Dish i is in front of either Person (i-k) \bmod N or Person (i+k) \bmod N.
Find the minimum possible sum of frustration of the N people.

Constraints

• 3 \leq N \leq 2 \times 10^5
• 0 \leq p_i \leq N-1
• p_i \neq p_j if i \neq j.
• All values in input are integers.

Sample Input 1

4
1 2 0 3

Sample Output 1

2

The figure below shows the table after one operation.

Here, the sum of their frustration is 2 because:

• Person 0 gains a frustration of 1 since Dish 0 is in front of Person 3\ (=(0-1) \bmod 4);
• Person 1 gains a frustration of 0 since Dish 1 is in front of Person 1\ (=(1+0) \bmod 4);
• Person 2 gains a frustration of 0 since Dish 2 is in front of Person 2\ (=(2+0) \bmod 4);
• Person 3 gains a frustration of 1 since Dish 3 is in front of Person 0\ (=(3+1) \bmod 4).

We cannot make the sum of their frustration less than 2, so the answer is 2.

Sample Input 2

3
0 1 2

Sample Output 2

0

Sample Input 3

10
3 9 6 1 7 2 8 0 5 4

Sample Output 3

20

Problem Statement

There are N boxes numbered 1,2,\ldots,N, and 10^{100} balls numbered 1,2,\dots,10^{100}. Initially, box i contains just ball i.

Process a total of Q operations that will be performed.

There are three types of operations: 1, 2, and 3.

Type 1: Put all contents of box Y into box X. It is guaranteed that X \neq Y.

1 X Y

Type 2: Put ball k+1 into box X, where k is the current total number of balls contained in the boxes.

2 X

Type 3: Report the number of the box that contains ball X.

3 X

Constraints

• All values in the input are integers.
• 2 \le N \le 3 \times 10^5
• 1 \le Q \le 3 \times 10^5
• For each type-1 operation, 1 \le X,Y \le N and X \neq Y.
• For each type-2 operation, 1 \le X \le N.
• For each type-3 operation, ball X is contained in some box at that point.
• There is at least one type-3 operation.

Sample Input 1

5 10
3 5
1 1 4
2 1
2 4
3 7
1 3 1
3 4
1 1 4
3 7
3 6

Sample Output 1

5
4
3
1
3

This input contains ten operations.

• The first operation is of type 3. Ball 5 is in box 5.
• The second operation is of type 1. Put all contents of box 4 into box 1.
  • Box 1 now contains balls 1 and 4, and box 4 is now empty.
• The third operation is of type 2. Put ball 6 into box 1.
• The fourth operation is of type 2. Put ball 7 into box 4.
• The fifth operation is of type 3. Ball 7 is in box 4.
• The sixth operation is of type 1. Put all contents of box 1 into box 3.
  • Box 3 now contains balls 1, 3, 4, and 6, and box 1 is now empty.
• The seventh operation is of type 3. Ball 4 is in box 3.
• The eighth operation is of type 1. Put all contents of box 4 into box 1.
  • Box 1 now contains ball 7, and box 4 is now empty.
• The ninth operation is of type 3. Ball 7 is in box 1.
• The tenth operation is of type 3. Ball 6 is in box 3.