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

The value calculated by the following formula is called \mathrm{BMI}[\mathrm{kg}/\mathrm{m}^2]. (\div denotes division.)

• \text{Weight}[\mathrm{kg}] \div \text{Height}[\mathrm{m}] \div \text{Height}[\mathrm{m}]

In Japan, a person whose \mathrm{BMI} is 25 \; \mathrm{kg}/\mathrm{m}^2 or more is considered obese.
Determine whether a person with height H[\mathrm{cm}] and weight W[\mathrm{kg}] is considered obese in Japan.

Constraints

• 1 \leq H \leq 300
• 1 \leq W \leq 300
• All input values are integers.

Sample Input 1

180 60

Sample Output 1

No

Since the height is 180 \; \mathrm{cm}=1.8 \; \mathrm{m}, the \mathrm{BMI} is 60 \; \mathrm{kg} \div 1.8 \; \mathrm{m} \div 1.8 \; \mathrm{m}=18.5\dots \; \mathrm{kg}/\mathrm{m}^2, so this person is not considered obese.

Sample Input 2

182 188

Sample Output 2

Yes

Sample Input 3

180 81

Sample Output 3

Yes

Problem Statement

There is a keyboard with 26 keys arranged on a number line.

The arrangement of this keyboard is represented by a string S, which is a permutation of ABCDEFGHIJKLMNOPQRSTUVWXYZ. The key corresponding to the character S_x is located at coordinate x (1 \leq x \leq 26). Here, S_x denotes the x-th character of S.

You will use this keyboard to input ABCDEFGHIJKLMNOPQRSTUVWXYZ in this order, typing each letter exactly once with your right index finger. To input a character, you need to move your finger to the coordinate of the key corresponding to that character and press the key.

Initially, your finger is at the coordinate of the key corresponding to A. Find the minimal possible total traveled distance of your finger from pressing the key for A to pressing the key for Z. Here, pressing a key does not contribute to the distance.

Constraints

• S is a permutation of ABCDEFGHIJKLMNOPQRSTUVWXYZ.

Sample Input 1

ABCDEFGHIJKLMNOPQRSTUVWXYZ

Sample Output 1

25

From pressing the key for A to pressing the key for Z, you need to move your finger 1 unit at a time in the positive direction, resulting in a total traveled distance of 25. It is impossible to press all keys with a total traveled distance less than 25, so print 25.

Sample Input 2

MGJYIZDKSBHPVENFLQURTCWOAX

Sample Output 2

223

Problem Statement

There are N sequences of integers.
The i-th (1 \leq i \leq N) sequence has L_i terms; the j-th (1 \leq j \leq L_i) term of the i-th sequence is a_{i, j}.

You are given Q queries. For the k-th (1 \leq k \leq Q) query, given integers s_k and t_k, find the t_k-th term of the s_k-th sequence.

Constraints

• 1 \leq N, Q \leq 2 \times 10^5
• L_i \geq 1 \, (1 \leq i \leq N)
• \sum_{i=1}^N L_i \leq 2 \times 10^5
• 1 \leq a_{i, j} \leq 10^9 \, (1 \leq i \leq N, 1 \leq j \leq L_i)
• 1 \leq s_k \leq N, 1 \leq t_k \leq L_{s_k} \, (1 \leq k \leq Q)
• All values in the input are integers.

Sample Input 1

2 2
3 1 4 7
2 5 9
1 3
2 1

Sample Output 1

7
5

The 1-st sequence is (1, 4, 7) and the 2-nd is (5, 9).
The answer to each query is as follows:

• The 3-rd term of the 1-st sequence is 7.
• The 1-st term of the 2-nd sequence is 5.

Sample Input 2

3 4
4 128 741 239 901
2 1 1
3 314 159 26535
1 1
2 2
3 3
1 4

Sample Output 2

128
1
26535
901

Problem Statement

There are N sticks with several balls stuck onto them. Each ball has a lowercase English letter written on it.

For each i = 1, 2, \ldots, N, the letters written on the balls stuck onto the i-th stick are represented by a string S_i. Specifically, the number of balls stuck onto the i-th stick is the length |S_i| of the string S_i, and S_i is the sequence of letters on the balls starting from one end of the stick.

Two sticks are considered the same when the sequence of letters on the balls starting from one end of one stick is equal to the sequence of letters starting from one end of the other stick. More formally, for integers i and j between 1 and N, inclusive, the i-th and j-th sticks are considered the same if and only if S_i equals S_j or its reversal.

Print the number of different sticks among the N sticks.

Constraints

• N is an integer.
• 2 \leq N \leq 2 \times 10^5
• S_i is a string consisting of lowercase English letters.
• |S_i| \geq 1
• \sum_{i = 1}^N |S_i| \leq 2 \times 10^5

Sample Input 1

6
a
abc
de
cba
de
abc

Sample Output 1

3

• S_2 = abc equals the reversal of S_4 = cba, so the second and fourth sticks are considered the same.
• S_2 = abc equals S_6 = abc, so the second and sixth sticks are considered the same.
• S_3 = de equals S_5 = de, so the third and fifth sticks are considered the same.

Therefore, there are three different sticks among the six: the first, second (same as the fourth and sixth), and third (same as the fifth).

Problem Statement

You are given a sequence A of length N.
Freely choose exactly K elements from A and remove them, then concatenate the remaining elements in their original order to form a new sequence B.
Find the minimum possible value of this: the maximum value of B minus the minimum value of B.

Constraints

• All inputs are integers.
• 1 \le K < N \le 2 \times 10^5
• 1 \le A_i \le 10^9

Sample Input 1

5 2
3 1 5 4 9

Sample Output 1

2

Consider removing exactly two elements from A=(3,1,5,4,9).

• For example, if you remove the 2nd element 1 and the 5th element 9, the resulting sequence is B=(3,5,4).
  • In this case, the maximum value of B is 5 and the minimum value is 3, so (maximum value of B) - (minimum value of B) =2, which is the minimum possible value.

Sample Input 2

6 5
1 1 1 1 1 1

Sample Output 2

0

Sample Input 3

8 3
31 43 26 6 18 36 22 13

Sample Output 3

18

Problem Statement

There is a perfect binary tree with 2^{10^{100}}-1 vertices, numbered 1,2,...,2^{10^{100}}-1.
Vertex 1 is the root. For each 1\leq i < 2^{10^{100}-1}, Vertex i has two children: Vertex 2i to the left and Vertex 2i+1 to the right.

Takahashi starts at Vertex X and performs N moves, represented by a string S. The i-th move is as follows.

• If the i-th character of S is U, go to the parent of the vertex he is on now.
• If the i-th character of S is L, go to the left child of the vertex he is on now.
• If the i-th character of S is R, go to the right child of the vertex he is on now.

Find the index of the vertex Takahashi will be on after N moves. In the given cases, it is guaranteed that the answer is at most 10^{18}.

Constraints

• 1 \leq N \leq 10^6
• 1 \leq X \leq 10^{18}
• N and X are integers.
• S has a length of N and consists of U, L, and R.
• When Takahashi is at the root, he never attempts to go to the parent.
• When Takahashi is at a leaf, he never attempts to go to a child.
• The index of the vertex Takahashi is on after N moves is at most 10^{18}.

Sample Input 1

3 2
URL

Sample Output 1

6

The perfect binary tree has the following structure.

In the three moves, Takahashi goes 2 \to 1 \to 3 \to 6.

Sample Input 2

4 500000000000000000
RRUU

Sample Output 2

500000000000000000

During the process, Takahashi may be at a vertex whose index exceeds 10^{18}.

Sample Input 3

30 123456789
LRULURLURLULULRURRLRULRRRUURRU

Sample Output 3

126419752371

Problem Statement

We have a grid with 2 rows and L columns. Let (i,j) denote the square at the i-th row from the top (i\in\lbrace1,2\rbrace) and j-th column from the left (1\leq j\leq L). (i,j) has an integer x _ {i,j} written on it.

Find the number of integers j such that x _ {1,j}=x _ {2,j}.

Here, the description of x _ {i,j} is given to you as the run-length compressions of (x _ {1,1},x _ {1,2},\ldots,x _ {1,L}) and (x _ {2,1},x _ {2,2},\ldots,x _ {2,L}) into sequences of lengths N _ 1 and N _ 2, respectively: ((v _ {1,1},l _ {1,1}),\ldots,(v _ {1,N _ 1},l _ {1,N _ 1})) and ((v _ {2,1},l _ {2,1}),\ldots,(v _ {2,N _ 2},l _ {2,N _ 2})).

Here, the run-length compression of a sequence A is a sequence of pairs (v _ i,l _ i) of an element v _ i of A and a positive integer l _ i obtained as follows.

1. Split A between each pair of different adjacent elements.
2. For each sequence B _ 1,B _ 2,\ldots,B _ k after the split, let v _ i be the element of B _ i and l _ i be the length of B _ i.

Constraints

• 1\leq L\leq 10 ^ {12}
• 1\leq N _ 1,N _ 2\leq 10 ^ 5
• 1\leq v _ {i,j}\leq 10 ^ 9\ (i\in\lbrace1,2\rbrace,1\leq j\leq N _ i)
• 1\leq l _ {i,j}\leq L\ (i\in\lbrace1,2\rbrace,1\leq j\leq N _ i)
• v _ {i,j}\neq v _ {i,j+1}\ (i\in\lbrace1,2\rbrace,1\leq j\lt N _ i)
• l _ {i,1}+l _ {i,2}+\cdots+l _ {i,N _ i}=L\ (i\in\lbrace1,2\rbrace)
• All values in the input are integers.

Sample Input 1

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

Sample Output 1

4

The grid is shown below.

We have four integers j such that x _ {1,j}=x _ {2,j}: j=1,2,5,8. Thus, you should print 4.

Sample Input 2

10000000000 1 1
1 10000000000
1 10000000000

Sample Output 2

10000000000

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

Sample Input 3

1000 4 7
19 79
33 463
19 178
33 280
19 255
33 92
34 25
19 96
12 11
19 490
33 31

Sample Output 3

380

Problem Statement

You are given a sequence of non-negative integers A = (A_1, A_2, \ldots, A_N) of length N.

You can perform the following operation on A zero or more times:

• Choose an integer i with 1 \le i \le N - 1, decrease A_i by 1, and increase A_{i+1} by 1.

Find the minimum number of operations required to make A strictly increasing.

It can be proved that the answer is less than 2^{63}.

You are given T test cases; solve each.

Constraints

• 1 \le T \le 3 \times 10^5
• 1 \le N \le 2 \times 10^5
• 0 \le A_i \le 10^9
• The sum of N across all test cases is at most 6 \times 10^5.
• All input values are integers.

Sample Input 1

4
3
0 1 0
4
4 6 3 5
7
1 2 3 4 5 6 7
10
11 9 1 3 17 19 10 19 17 3

Sample Output 1

3
5
0
78

Consider the first test case.

By performing the following operations, A can be made strictly increasing in three operations:

• Choose i=1. A becomes (-1, 2, 0).
• Choose i=2. A becomes (-1, 1, 1).
• Choose i=2. A becomes (-1, 0, 2).

It is impossible to make A strictly increasing in fewer than three operations, so output 3.