Problem Statement

In a parallel universe, AtCoder holds AtCoder Big Contest, where 10^{16} problems are given at once.
The IDs of the problems are as follows, from the 1-st problem in order: A, B, ..., Z, AA, AB, ..., ZZ, AAA, ...

In other words, the IDs are given in the following order:

• the strings of length 1 consisting of uppercase English letters, in lexicographical order;
• the strings of length 2 consisting of uppercase English letters, in lexicographical order;
• the strings of length 3 consisting of uppercase English letters, in lexicographical order;
• ...

Given a string S that is an ID of a problem given in this contest, find the index of the problem. (See also Samples.)

Constraints

• S is a valid ID of a problem given in AtCoder Big Contest.

Sample Input 1

AB

Sample Output 1

28

The problem whose ID is AB is the 28-th problem of AtCoder Big Contest, so 28 should be printed.

Sample Input 2

C

Sample Output 2

3

The problem whose ID is C is the 3-rd problem of AtCoder Big Contest, so 3 should be printed.

Sample Input 3

BRUTMHYHIIZP

Sample Output 3

10000000000000000

The problem whose ID is BRUTMHYHIIZP is the 10^{16}-th (last) problem of AtCoder Big Contest, so 10^{16} should be printed as an integer.

Problem Statement

Takahashi is planning an N-day train trip.
For each day, he can pay the regular fare or use a one-day pass.

Here, for 1\leq i\leq N, the regular fare for the i-th day of the trip is F_i yen.
On the other hand, a batch of D one-day passes is sold for P yen. You can buy as many passes as you want, but only in units of D.
Each purchased pass can be used on any day, and it is fine to have some leftovers at the end of the trip.

Find the minimum possible total cost for the N-day trip, that is, the cost of purchasing one-day passes plus the total regular fare for the days not covered by one-day passes.

Constraints

• 1\leq N\leq 2\times 10^5
• 1\leq D\leq 2\times 10^5
• 1\leq P\leq 10^9
• 1\leq F_i\leq 10^9
• All input values are integers.

Sample Input 1

5 2 10
7 1 6 3 6

Sample Output 1

20

If he buys just one batch of one-day passes and uses them for the first and third days, the total cost will be (10\times 1)+(0+1+0+3+6)=20, which is the minimum cost needed.
Thus, print 20.

Sample Input 2

3 1 10
1 2 3

Sample Output 2

6

The minimum cost is achieved by paying the regular fare for all three days.

Sample Input 3

8 3 1000000000
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

Sample Output 3

3000000000

The minimum cost is achieved by buying three batches of one-day passes and using them for all eight days.
Note that the answer may not fit into a 32-bit integer type.

Problem Statement

You are given a sequence of length N: A=(A_1,A_2,\ldots,A_N).
Find the number of triples (i,j,k) that satisfy both of the following conditions.

• 1\leq i \lt j \lt k \leq N
• A_i, A_j, and A_k are distinct.

Constraints

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

Sample Input 1

4
3 1 4 1

Sample Output 1

2

The two triples (i,j,k) satisfying the conditions are (1,2,3) and (1,3,4).

Sample Input 2

10
99999 99998 99997 99996 99995 99994 99993 99992 99991 99990

Sample Output 2

120

Sample Input 3

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

Sample Output 3

355

Problem Statement

You are given an undirected graph G with N vertices and M edges. For i = 1, 2, \ldots, M, the i-th edge is an undirected edge connecting vertices u_i and v_i.

A graph with N vertices is called good if the following condition holds for all i = 1, 2, \ldots, K:

• there is no path connecting vertices x_i and y_i in G.

The given graph G is good.

You are given Q independent questions. Answer all of them. For i = 1, 2, \ldots, Q, the i-th question is as follows.

• Is the graph G^{(i)} obtained by adding an undirected edge connecting vertices p_i and q_i to the given graph G good?

Constraints

• 2 \leq N \leq 2 \times 10^5
• 0 \leq M \leq 2 \times10^5
• 1 \leq u_i, v_i \leq N
• 1 \leq K \leq 2 \times 10^5
• 1 \leq x_i, y_i \leq N
• x_i \neq y_i
• i \neq j \implies \lbrace x_i, y_i \rbrace \neq \lbrace x_j, y_j \rbrace
• For all i = 1, 2, \ldots, K, there is no path connecting vertices x_i and y_i.
• 1 \leq Q \leq 2 \times 10^5
• 1 \leq p_i, q_i \leq N
• p_i \neq q_i
• All input values are integers.

Sample Input 1

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

Sample Output 1

No
No
Yes
Yes

• For the first question, the graph G^{(1)} is not good because it has a path 1 \rightarrow 2 \rightarrow 5 connecting vertices x_1 = 1 and y_1 = 5. Therefore, print No.
• For the second question, the graph G^{(2)} is not good because it has a path 2 \rightarrow 6 connecting vertices x_2 = 2 and y_2 = 6. Therefore, print No.
• For the third question, the graph G^{(3)} is good. Therefore, print Yes.
• For the fourth question, the graph G^{(4)} is good. Therefore, print Yes.

As seen in this sample input, note that the given graph G may have self-loops or multi-edges.

Problem Statement

A robot is at the origin of a coordinate plane where the positive x-axis points to the right and the positive y-axis points upwards. Initially, the robot is facing the positive x-direction.

You will perform the following operation for i=1,\ldots,N in this order.

• Rotate the robot 90 degrees clockwise or counterclockwise. Then, the robot moves forward A_i units in the direction it is facing.

Can the direction of rotation be chosen so that the robot will be at the coordinates (X,Y) after the N operations?

If it is possible, determine which direction, clockwise or counterclockwise, should be chosen for each operation.

Constraints

• 1 \leq N \leq 80
• 1 \leq A_i \leq 10^7
• -10^9\leq X,Y \leq 10^9
• All input values are integers.

Sample Input 1

3 -2 4
3 2 1

Sample Output 1

Yes
LLR

Initially, the robot is at (0,0) and facing the positive x-direction. The following choices can put the robot at the coordinates (X,Y) after the N operations.

• First operation: Rotate the robot 90 degrees counterclockwise to face the positive y-direction. The robot moves forward A_1=3 units in the direction it is facing, and moves to (0,3).
• Second operation: Rotate the robot 90 degrees counterclockwise to face the negative x-direction. The robot moves forward A_2=2 units in the direction it is facing, and moves to (-2,3).
• Third operation: Rotate the robot 90 degrees clockwise to face the positive y-direction. The robot moves forward A_3=1 unit in the direction it is facing, and moves to (-2,4).

Sample Input 2

1 0 0
1

Sample Output 2

No

Sample Input 3

4 0 0
1 1 1 1

Sample Output 3

Yes
LRRR

Outputs such as LLLL and RRRR are also accepted.

Sample Input 4

14 2543269 -1705099
3 14 159 2653 58979 323846 2643383 2795028 841971 69399 37510 58 20 9

Sample Output 4

Yes
LLLLLLLLLRLRRR