Problem Statement

Takahashi is learning AtCoderish Language.

He memorizes AtCoderish words corresponding to English words.

He knows that red, blue, and green in English respectively correspond to SSS, FFF, and MMM in AtCoderish, and he knows no other words.

You are given a string S consisting of lowercase English letters. If S equals an English word that Takahashi knows corresponds to an AtCoderish word, output the AtCoderish word corresponding to S; otherwise, output the string Unknown.

Constraints

• S is a string of length between 1 and 10, inclusive, consisting of English letters.

Sample Input 1

red

Sample Output 1

SSS

red in English corresponds to SSS in AtCoderish.

Sample Input 2

atcoder

Sample Output 2

Unknown

Problem Statement

There is a rectangle in the xy-plane. Each edge of this rectangle is parallel to the x- or y-axis, and its area is not zero.

Given the coordinates of three of the four vertices of this rectangle, (x_1, y_1), (x_2, y_2), and (x_3, y_3), find the coordinates of the other vertex.

Constraints

• -100 \leq x_i, y_i \leq 100
• There uniquely exists a rectangle with all of (x_1, y_1), (x_2, y_2), (x_3, y_3) as vertices, edges parallel to the x- or y-axis, and a non-zero area.
• All values in input are integers.

Sample Input 1

-1 -1
-1 2
3 2

Sample Output 1

3 -1

The other vertex of the rectangle with vertices (-1, -1), (-1, 2), (3, 2) is (3, -1).

Sample Input 2

-60 -40
-60 -80
-20 -80

Sample Output 2

-20 -40

Problem Statement

Takahashi is at the origin on a two-dimensional coordinate plane.

The cost for him to move from point (a, b) to point (c, d) is \sqrt{(a - c)^2 + (b - d)^2}.

Find the total cost when he starts at the origin, visits N points (X_1, Y_1), \ldots, (X_N, Y_N) in this order, and then returns to the origin.

Constraints

• 1 \leq N \leq 2 \times 10^5
• -10^9 \leq X_i, Y_i \leq 10^9
• All input values are integers.

Sample Input 1

2
1 2
-1 0

Sample Output 1

6.06449510224597979401

The journey consists of the following three steps:

• Move from (0, 0) to (1, 2). The cost is \sqrt{(0 - 1)^2 + (0 - 2)^2} = \sqrt{5} = 2.236067977....
• Move from (1, 2) to (-1, 0). The cost is \sqrt{(1 - (-1))^2 + (2 - 0)^2} = \sqrt{8} = 2.828427124....
• Move from (-1, 0) to (0, 0). The cost is \sqrt{(-1 - 0)^2 + (0 - 0)^2} = \sqrt{1} = 1.

The total cost is 6.064495102....

Sample Input 2

7
-14142 13562
-17320 50807
-22360 67977
24494 89742
-26457 51311
28284 27124
31622 77660

Sample Output 2

384694.57587932075868509383

Sample Input 3

5
-100000 100000
100000 -100000
-100000 100000
100000 -100000
-100000 100000

Sample Output 3

1414213.56237309504880168872

Problem Statement

Note: This problem has almost the same setting as Problem F. Only the parts in bold in the main text and constraints differ.

You are holding a ring with both hands. This ring consists of N\ (N \geq 3) parts numbered 1,2,\dots,N, where parts i and i+1 (1 \leq i \leq N-1) are adjacent, and parts 1 and N are also adjacent.

Initially, your left hand is holding part 1, and your right hand is holding part 2. In one operation, you can do the following:

• Move one of your hands to an adjacent part of the part it is currently holding. However, you can do this only if the other hand is not on the destination part.

The following figure shows the initial state and examples of operations that can and cannot be made from there. The number written on each part of the ring represents the part number, and the circles labeled L and R represent your left and right hands, respectively.

You need to follow Q instructions given to you in order. The i-th (1 \leq i \leq Q) instruction is represented by a character H_i and an integer T_i, meaning the following:

• Perform some number of operations (possibly zero) so that your left hand (if H_i is L) or your right hand (if H_i is R) is holding part T_i. Here, you must not move the other hand not specified by H_i.

It is guaranteed that only achievable instructions are given.

Find the minimum total number of operations required to follow all the instructions.

Constraints

• 3 \leq N \leq 100
• 1 \leq Q \leq 100
• H_i is L or R.
• 1 \leq T_i \leq N
• N, Q, and T_i are integers.
• Only achievable instructions are given (see the problem statement for details).

Sample Input 1

6 3
R 4
L 5
R 6

Sample Output 1

8

By performing the following operations, you can follow all Q instructions in order.

1. Move your right hand as part 2 \rightarrow 3 \rightarrow 4 to follow the first instruction.
2. Move your left hand as part 1 \rightarrow 6 \rightarrow 5 to follow the second instruction.
3. Move your right hand as part 4 \rightarrow 3 \rightarrow 2 \rightarrow 1 \rightarrow 6 to follow the third instruction.

In this case, the total number of operations is 2+2+4=8, which is the minimum. (Note that when following the third instruction, you cannot move your right hand as part 4 \rightarrow 5 \rightarrow 6.)

Sample Input 2

100 2
L 1
R 2

Sample Output 2

0

There are cases where you can follow the instructions without performing any operations.

Sample Input 3

30 8
R 23
R 26
R 29
L 20
R 29
R 19
L 7
L 16

Sample Output 3

92

Problem Statement

You are given an integer sequence of length N, A=(A_1,A_2,\ldots,A_N).
Find the number of triples of integers (i,j,k) satisfying 1\leq i<j<k\leq N that satisfy the following condition:

Exactly two distinct values are contained in A_i,A_j,A_k. That is, two of A_i,A_j,A_k are equal, and the remaining one is different.

Constraints

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

Sample Input 1

5
3 2 5 2 2

Sample Output 1

6

For example, (i,j,k)=(1,2,4) satisfies the condition because exactly two distinct values, 2 and 3, are contained in A_1=3, A_2=2, and A_4=2.
Including this, the six triples (i,j,k)=(1,2,4),(1,2,5),(1,4,5),(2,3,4),(2,3,5),(3,4,5) satisfy the condition.
Therefore, print 6.

Sample Input 2

3
1 1 1

Sample Output 2

0

There may be no triples that satisfy the condition.