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

There is an ultramarathon course totaling 100\;\mathrm{km}. Water stations are set up every 5\;\mathrm{km} along the course, including the start and goal, for a total of 21.

Takahashi is at the N\;\mathrm{km} point of this course. Find the position of the nearest water station to him.

Under the constraints of this problem, it can be proven that the nearest water station is uniquely determined.

Constraints

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

Sample Input 1

53

Sample Output 1

55

Takahashi is at the 53\;\mathrm{km} point of the course. The water station at the 55\;\mathrm{km} point is 2\;\mathrm{km} away, and there is no closer water station. Therefore, you should print 55.

Sample Input 2

21

Sample Output 2

20

Takahashi could also go back the way.

Sample Input 3

100

Sample Output 3

100

There are also water stations at the start and goal. Additionally, Takahashi may already be at a water station.

Problem Statement

Consider an xy-plane. The positive direction of the x-axis is in the direction of east, and the positive direction of the y-axis is in the direction of north.
Takahashi is initially at point (x, y) = (0, 0) and facing east (in the positive direction of the x-axis).

You are given a string T = t_1t_2\ldots t_N of length N consisting of S and R. Takahashi will do the following move for each i = 1, 2, \ldots, N in this order.

• If t_i = S, Takahashi advances in the current direction by distance 1.
• If t_i = R, Takahashi turns 90 degrees clockwise without changing his position. As a result, Takahashi's direction changes as follows.
  • If he is facing east (in the positive direction of the x-axis) before he turns, he will face south (in the negative direction of the y-axis) after he turns.
  • If he is facing south (in the negative direction of the y-axis) before he turns, he will face west (in the negative direction of the x-axis) after he turns.
  • If he is facing west (in the negative direction of the x-axis) before he turns, he will face north (in the positive direction of the y-axis) after he turns.
  • If he is facing north (in the positive direction of the y-axis) before he turns, he will face east (in the positive direction of the x-axis) after he turns.

Print the coordinates Takahashi is at after all the steps above have been done.

Constraints

• 1 \leq N \leq 10^5
• N is an integer.
• T is a string of length N consisting of S and R.

Sample Input 1

4
SSRS

Sample Output 1

2 -1

Takahashi is initially at (0, 0) facing east. Then, he moves as follows.

1. t_1 = S, so he advances in the direction of east by distance 1, arriving at (1, 0).
2. t_2 = S, so he advances in the direction of east by distance 1, arriving at (2, 0).
3. t_3 = R, so he turns 90 degrees clockwise, resulting in facing south.
4. t_4 = S, so he advances in the direction of south by distance 1, arriving at (2, -1).

Thus, Takahashi's final position, (x, y) = (2, -1), should be printed.

Sample Input 2

20
SRSRSSRSSSRSRRRRRSRR

Sample Output 2

0 1

Problem Statement

N people numbered 1,2,\ldots,N were in M photos. In each of the photos, they stood in a single line. In the i-th photo, the j-th person from the left is person a_{i,j}.

Two people who did not stand next to each other in any of the photos may be in a bad mood.

How many pairs of people may be in a bad mood? Here, we do not distinguish a pair of person x and person y, and a pair of person y and person x.

Constraints

• 2 \leq N \leq 50
• 1 \leq M \leq 50
• 1 \leq a_{i,j} \leq N
• a_{i,1},\ldots,a_{i,N} contain each of 1,\ldots,N exactly once.
• All values in the input are integers.

Sample Input 1

4 2
1 2 3 4
4 3 1 2

Sample Output 1

2

The pair of person 1 and person 4, and the pair of person 2 and person 4, may be in a bad mood.

Sample Input 2

3 3
1 2 3
3 1 2
1 2 3

Sample Output 2

0

Sample Input 3

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

Sample Output 3

6

Problem Statement

Takahashi has a red jewel of level N. (He has no other jewels.)
Takahashi can do the following operations any number of times.

• Convert a red jewel of level n (n is at least 2) into "a red jewel of level (n-1) and X blue jewels of level n".
• Convert a blue jewel of level n (n is at least 2) into "a red jewel of level (n-1) and Y blue jewels of level (n-1)".

Takahashi wants as many blue jewels of level 1 as possible. At most, how many blue jewels of level 1 can he obtain by the operations?

Constraints

• 1 \leq N \leq 10
• 1 \leq X \leq 5
• 1 \leq Y \leq 5
• All values in input are integers.

Sample Input 1

2 3 4

Sample Output 1

12

Takahashi can obtain 12 blue jewels of level 1 by the following conversions.

• First, he converts a red jewel of level 2 into a red jewel of level 1 and 3 blue jewels of level 2.
  • After this operation, Takahashi has 1 red jewel of level 1 and 3 blue jewels of level 2.
• Next, he repeats the following conversion 3 times: converting a blue jewel of level 2 into a red jewel of level 1 and 4 blue jewels of level 1.
  • After these operations, Takahashi has 4 red jewels of level 1 and 12 blue jewels of level 1.
• He cannot perform a conversion anymore.

He cannot obtain more than 12 blue jewels of level 1, so the answer is 12.

Sample Input 2

1 5 5

Sample Output 2

0

Takahashi may not be able to obtain a blue jewel of level 1.

Sample Input 3

10 5 5

Sample Output 3

3942349900

Note that the answer may not fit into a 32-bit integer type.

Problem Statement

We define sequences S_n as follows.

• S_1 is a sequence of length 1 containing a single 1.
• S_n (n is an integer greater than or equal to 2) is a sequence obtained by concatenating S_{n-1}, n, S_{n-1} in this order.

For example, S_2 and S_3 is defined as follows.

• S_2 is a concatenation of S_1, 2, and S_1, in this order, so it is 1,2,1.
• S_3 is a concatenation of S_2, 3, and S_2, in this order, so it is 1,2,1,3,1,2,1.

Given N, print the entire sequence S_N.

Constraints

• N is an integer.
• 1 \leq N \leq 16

Sample Input 1

2

Sample Output 1

1 2 1

As described in the Problem Statement, S_2 is 1,2,1.

Sample Input 2

1

Sample Output 2

1

Sample Input 3

4

Sample Output 3

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

• S_4 is a concatenation of S_3, 4, and S_3, in this order.

Problem Statement

Takahashi is trying to catch many Snuke.

There are five pits at coordinates 0, 1, 2, 3, and 4 on a number line, connected to Snuke's nest.

Now, N Snuke will appear from the pits. It is known that the i-th Snuke will appear from the pit at coordinate X_i at time T_i, and its size is A_i.

Takahashi is at coordinate 0 at time 0 and can move on the line at a speed of at most 1.
He can catch a Snuke appearing from a pit if and only if he is at the coordinate of that pit exactly when it appears.
The time it takes to catch a Snuke is negligible.

Find the maximum sum of the sizes of Snuke that Takahashi can catch by moving optimally.

Constraints

• 1 \leq N \leq 10^5
• 0 < T_1 < T_2 < \ldots < T_N \leq 10^5
• 0 \leq X_i \leq 4
• 1 \leq A_i \leq 10^9
• All values in input are integers.

Sample Input 1

3
1 0 100
3 3 10
5 4 1

Sample Output 1

101

The optimal strategy is as follows.

• Wait at coordinate 0 to catch the first Snuke at time 1.
• Go to coordinate 4 to catch the third Snuke at time 5.

It is impossible to catch both the first and second Snuke, so this is the best he can.

Sample Input 2

3
1 4 1
2 4 1
3 4 1

Sample Output 2

0

Takahashi cannot catch any Snuke.

Sample Input 3

10
1 4 602436426
2 1 623690081
3 3 262703497
4 4 628894325
5 3 450968417
6 1 161735902
7 1 707723857
8 2 802329211
9 0 317063340
10 2 125660016

Sample Output 3

2978279323

Problem Statement

There are N baskets numbered 1, 2, \ldots, N arranged in a circle.
For each 1\leq i \leq N-1, basket i+1 is to the immediate right of basket i, and basket 1 is to the immediate right of basket N.

Basket i now contains A_i apples.

Takahashi starts in front of basket 1 and repeats the following action.

• If the basket he is facing contains an apple, take one and eat it. Then, regardless of whether he has eaten an apple now, go on to the next basket to the immediate right.

Find the number of apples remaining in each basket when Takahashi has eaten exactly K apples in total.

Constraints

• 1 \leq N \leq 10^5
• 0 \leq A_i \leq 10^{12}
• 1 \leq K \leq 10^{12}
• There are at least K apples in total. That is, \sum_{i=1}^{N}A_i\geq K.
• All values in the input are integers.

Sample Input 1

3 3
1 3 0

Sample Output 1

0 1 0 

Takahashi will do the following.

• Basket 1, which he is facing, contains an apple, so he takes one and eats it. Then, he goes on to basket 2. Now, the baskets have 0,3,0 apples.
• Basket 2, which he is facing, contains an apple, so he takes one and eats it. Then, he goes on to basket 3. Now, the baskets have 0,2,0 apples.
• Basket 3, which he is facing, contains no apple. Then, he goes on to basket 1. Now, the baskets have 0,2,0 apples.
• Basket 1, which he is facing, contains no apple. Then, he goes on to basket 2. Now, the baskets have 0,2,0 apples.
• Basket 2, which he is facing, contains an apple, so he takes one and eats it. Then, he goes on to basket 3. Now, the baskets have 0,1,0 apple(s).

Sample Input 2

2 1000000000000
1000000000000 1000000000000

Sample Output 2

500000000000 500000000000 

Problem Statement

There are apple trees lined up on a number line, and N apples fall from the trees.
Specifically, for each 1\leq i\leq N, an apple falls at coordinate X_i at time T_i.

Takahashi has a basket with durability D and length W, and he can take the following action exactly once.

Choose positive integers S and L. He sets up the basket to cover the range L-0.5\leq x\leq L+W-0.5 at time S-0.5, and retrieves it at time S+D-0.5. He gets all the apples that fell into the range covered by the basket between the time it was set up and the time it was retrieved.

He cannot move the basket once it has been set up, nor can he set it up again once it has been retrieved.
Find the maximum number of apples that he can get.

Constraints

• 1 \leq N\leq 2\times 10^5
• 1 \leq D\leq 2\times 10^5
• 1 \leq W\leq 2\times 10^5
• 1 \leq T_i\leq 2\times 10^5
• 1 \leq X_i\leq 2\times 10^5
• All pairs (T_i,X_i) are different.
• All input values are integers.

Sample Input 1

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

Sample Output 1

5

If Takahashi chooses S=3 and L=2, he will set up the basket to cover the range 1.5\leq x\leq 4.5 from time 2.5 to 6.5. Then, he gets the following five apples:

• The apple that falls at coordinate X_2=4 at time T_2=3
• The apple that falls at coordinate X_3=4 at time T_3=6
• The apple that falls at coordinate X_4=2 at time T_4=5
• The apple that falls at coordinate X_5=2 at time T_5=4
• The apple that falls at coordinate X_6=3 at time T_6=4

There is no way to get six or more apples, so print 5.