Problem Statement

There are three dice, each with six faces.
Each die has 1,2,3,4,5,6 written on its faces.

When these dice are rolled simultaneously, is it possible for the sum of the rolled values to be X?

Constraints

• X is an integer between 1 and 20, inclusive.

Sample Input 1

15

Sample Output 1

Yes

For example, if the rolled values are 4,5,6, the sum is 15.

Sample Input 2

2

Sample Output 2

No

Problem Statement

You are given a string S. Here, the first character of S is an uppercase English letter, and the second and subsequent characters are lowercase English letters.

Print the string formed by concatenating the first character of S and UPC in this order.

Constraints

• S is a string of length between 1 and 100, inclusive.
• The first character of S is an uppercase English letter.
• The second and subsequent characters of S are lowercase English letters.

Sample Input 1

Kyoto

Sample Output 1

KUPC

The first character of Kyoto is K, so concatenate K and UPC, and print KUPC.

Sample Input 2

Tohoku

Sample Output 2

TUPC

Problem Statement

N players, who are numbered 1, \ldots, N, have played a game. Player i has scored A_i, and a player with a smaller score ranks higher.

The player who ranks the second lowest will receive a booby prize. Who is this player? Answer with an integer representing the player.

Constraints

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

Sample Input 1

6
1 123 12345 12 1234 123456

Sample Output 1

3

It is Player 3 who ranks fifth among the six players.

Sample Input 2

5
3 1 4 15 9

Sample Output 2

5

Problem Statement

You are given an integer sequence A=(A_1,A_2,\ldots,A_N) of length N. Here, each element of A is either -1 or an integer between 1 and N, inclusive.

Determine whether there exists an integer sequence P=(P_1,P_2,\ldots,P_N) of length N that satisfies all of the following conditions, and if it exists, find one.

• P is a permutation of (1,2,\ldots,N).
• For i=1,2,\ldots,N, if A_i \neq -1, then P_i=A_i holds.

Constraints

• 1\le N\le 10
• A_i=-1 or 1\le A_i \le N
• All input values are integers.

Sample Input 1

4
-1 -1 2 -1

Sample Output 1

Yes
3 1 2 4

P=(3,1,2,4) satisfies all conditions.

Besides this, P=(1,3,2,4) or P=(4,3,2,1) also satisfies all conditions.

Sample Input 2

5
-1 -1 1 -1 1

Sample Output 2

No

There is no P that satisfies all conditions.

Sample Input 3

7
3 -1 4 -1 5 -1 2

Sample Output 3

Yes
3 7 4 1 5 6 2

Problem Statement

There are N buildings arranged in a line at equal intervals. The height of the i-th building from the front is H_i.

You want to decorate some of these buildings with illuminations so that both of the following conditions are satisfied:

• The chosen buildings all have the same height.
• The chosen buildings are arranged at equal intervals.

What is the maximum number of buildings you can choose? If you choose exactly one building, it is considered to satisfy the conditions.

Constraints

• 1 \leq N \leq 3000
• 1 \leq H_i \leq 3000
• All input values are integers.

Sample Input 1

8
5 7 5 7 7 5 7 7

Sample Output 1

3

Choosing the 2nd, 5th, and 8th buildings from the front satisfies the conditions.

Sample Input 2

10
100 200 300 400 500 600 700 800 900 1000

Sample Output 2

1

Choosing just one building is considered to satisfy the conditions.

Sample Input 3

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

Sample Output 3

3

Problem Statement

This problem is an easier version of Problem G.

There is a slot machine with three reels.
The arrangement of symbols on the i-th reel is represented by the string S_i. Here, S_i is a string of length M consisting of digits.

Each reel has a corresponding button. For each non-negative integer t, Takahashi can either choose and press one button or do nothing exactly t seconds after the reels start spinning.
If he presses the button corresponding to the i-th reel exactly t seconds after the reels start spinning, the i-th reel will stop and display the ((t \bmod M)+1)-th character of S_i.
Here, t \bmod M denotes the remainder when t is divided by M.

Takahashi wants to stop all the reels so that all the displayed characters are the same.
Find the minimum possible number of seconds from the start of the spin until all the reels are stopped so that his goal is achieved.
If this is impossible, report that fact.

Constraints

• 1 \leq M \leq 100
• M is an integer.
• S_i is a string of length M consisting of digits.

Sample Input 1

10
1937458062
8124690357
2385760149

Sample Output 1

6

Takahashi can stop each reel as follows so that 6 seconds after the reels start spinning, all the reels display 8.

• Press the button corresponding to the second reel 0 seconds after the reels start spinning. The second reel stops and displays 8, the ((0 \bmod 10)+1=1)-st character of S_2.
• Press the button corresponding to the third reel 2 seconds after the reels start spinning. The third reel stops and displays 8, the ((2 \bmod 10)+1=3)-rd character of S_3.
• Press the button corresponding to the first reel 6 seconds after the reels start spinning. The first reel stops and displays 8, the ((6 \bmod 10)+1=7)-th character of S_1.

There is no way to make the reels display the same character in 5 or fewer seconds, so print 6.

Sample Input 2

20
01234567890123456789
01234567890123456789
01234567890123456789

Sample Output 2

20

Note that he must stop all the reels and make them display the same character.

Sample Input 3

5
11111
22222
33333

Sample Output 3

-1

It is impossible to stop the reels so that all the displayed characters are the same.
In this case, print -1.

Problem Statement

There is a sequence that contains one 0, A=(0).
Additionally, you are given a string of length N, S=s_1s_2\ldots s_N, consisting of L and R.

For each i=1, 2, \ldots, N in this order, the following will be done.

• If s_i is L, insert i to the immediate left of i-1 in A.
• If s_i is R, insert i to the immediate right of i-1 in A.

Find the final contents of A.

Constraints

• 1\leq N \leq 5\times 10^5
• N is an integer.
• |S| = N
• s_i is L or R.

Sample Input 1

5
LRRLR

Sample Output 1

1 2 4 5 3 0

Initially, A=(0).
S_1 is L, which makes it A=(1,0).
S_2 is R, which makes it A=(1,2,0).
S_3 is R, which makes it A=(1,2,3,0).
S_4 is L, which makes it A=(1,2,4,3,0).
S_5 is R, which makes it A=(1,2,4,5,3,0).

Sample Input 2

7
LLLLLLL

Sample Output 2

7 6 5 4 3 2 1 0

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

On a number line, there are N fish swimming.

Fish i, which has a weight of W_i, is at the coordinate X_i at time 0 and moves at a speed of V_i in the positive direction.

Takahashi will choose an arbitrary real number t greater than or equal to 0 and do the following action at time t just once.
Action: Choose an arbitrary real number x. Catch all fish whose coordinates are between x and x+A, inclusive.

Find the maximum total weight of fish that he can catch.

Constraints

• 1 \leq N \leq 2000
• 1 \leq A \leq 10^4
• 1 \leq W_i\leq 10^4
• 0 \leq X_i\leq 10^4
• 1 \leq V_i\leq 10^4
• All values in the input are integers.

Sample Input 1

3 10
100 0 100
1 10 30
10 20 10

Sample Output 1

111

At time 0.25, fish 1, 2, and 3 are at the coordinates 25, 17.5, and 22.5, respectively. Thus, the action done at this time with x=16 catches all the fish.

Sample Input 2

3 10
100 100 100
1 10 30
10 20 10

Sample Output 2

100

One optimal choice is to do the action at time 0 with x=100.

Sample Input 3

4 10
1000 100 10
100 99 1
10 0 100
1 1 1

Sample Output 3

1110

One optimal choice is to do the action at time 1 with x=100.