Problem Statement

You are given an integer N at least 100. Print the last two digits of N.

Strictly speaking, print the tens and ones digits of N in this order.

Constraints

• 100 \le N \le 999
• N is an integer.

Sample Input 1

254

Sample Output 1

54

The last two digits of 254 are 54, which should be printed.

Sample Input 2

101

Sample Output 2

01

The last two digits of 101 are 01, which should be printed.

Problem Statement

For a positive integer X, the Dragon String of level X is a string of length (X+3) formed by one L, X occurrences of o, one n, and one g arranged in this order.

You are given a positive integer N. Print the Dragon String of level N.
Note that uppercase and lowercase letters are distinguished.

Constraints

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

Sample Input 1

3

Sample Output 1

Looong

Arranging one L, three os, one n, and one g in this order yields Looong.

Sample Input 2

1

Sample Output 2

Long

Problem Statement

Takahashi bought a table clock.
The clock shows the time as shown in Figure 1 at \mathrm{AB}:\mathrm{CD} in the 24-hour system.
For example, the clock in Figure 2 shows 7:58.

The format of the time is formally described as follows.
Suppose that the current time is m minutes past h in the 24-hour system. Here, the 24-hour system represents the hour by an integer between 0 and 23 (inclusive), and the minute by an integer between 0 and 59 (inclusive).
Let A be the tens digit of h, B be the ones digit of h, C be the tens digit of m, and D be the ones digit of m. (Here, if h has only one digit, we consider that it has a leading zero; the same applies to m.)
Then, the clock shows A in its top-left, B in its bottom-left, C in its top-right, and D in its bottom-right.

Takahashi has decided to call a time a confusing time if it satisfies the following condition:

• after swapping the top-right and bottom-left digits on the clock, it still reads a valid time in the 24-hour system.

For example, the clock in Figure 3 shows 20:13. After swapping its top-right and bottom-left digits, it reads 21:03. Thus, 20:13 is a confusing time.

The clock now shows H:M.
Find the next confusing time (including now) in the 24-hour system.

Constraints

• 0 \leq H \leq 23
• 0 \leq M \leq 59
• H and M are integers.

Sample Input 1

1 23

Sample Output 1

1 23

1:23 is a confusing time because, after swapping its top-right and bottom-left digits on the clock, it reads 2:13.
Thus, the answer is 1:23.
Your answer is considered correct even if you print 01 23 with a leading zero.

Sample Input 2

19 57

Sample Output 2

20 0

The next confusing time after 19:57 is 20:00.

Sample Input 3

20 40

Sample Output 3

21 0

Note that 24:00 is an invalid notation in the 24-hour system.

Problem Statement

You are given N strings, each of length 2, consisting of uppercase English letters and digits. The i-th string is S_i.
Determine whether the following three conditions are all satisfied.
・For every string, the first character is one of H, D, C, and S.
・For every string, the second character is one of A, 2, 3, 4, 5, 6, 7, 8, 9, T, J, Q, K.
・All strings are pairwise different. That is, if i \neq j, then S_i \neq S_j.

Constraints

• 1 \leq N \leq 52
• S_i is a string of length 2 consisting of uppercase English letters and digits.

Sample Input 1

4
H3
DA
D3
SK

Sample Output 1

Yes

One can verify that the three conditions are all satisfied.

Sample Input 2

5
H3
DA
CK
H3
S7

Sample Output 2

No

Both S_1 and S_4 are H3, violating the third condition.

Sample Input 3

4
3H
AD
3D
KS

Sample Output 3

No

Sample Input 4

5
00
AA
XX
YY
ZZ

Sample Output 4

No

Problem Statement

Artist Takasago has created an object in the shape of a fish skeleton.

The object consists of N ribs and one spine. The ribs are numbered 1 through N.

He wants to write one string on each of the N+1 bones, satisfying all of the following conditions.

• The length of the string written on the spine is N.
• For each rib i = 1, \dots, N, the following hold.
  • The length of the string written on rib i is A_i.
  • The B_i-th character of the string written on rib i equals the i-th character of the string written on the spine.
• Each of the strings written on the N+1 bones is one of S_1, \cdots, S_M (duplicates allowed).

S_1, \cdots, S_M are strings consisting of lowercase English letters, and they are all distinct.

For each j = 1, \cdots, M, answer the following question.

• Among the ways to write strings satisfying the conditions, is there one where the string written on the spine is S_j?

Constraints

• N is an integer.
• 1 \leq N \leq 10
• A_i and B_i are integers. (1 \leq i \leq N)
• 1 \leq B_i \leq A_i \leq 10 (1 \leq i \leq N)
• M is an integer.
• 1 \leq M \leq 200\,000
• S_j is a string consisting of lowercase English letters. (1 \leq j \leq M)
• 1 \leq |S_j| \leq 10 (1 \leq j \leq M)
• S_1, \cdots, S_M are pairwise distinct.

Sample Input 1

5
5 3
5 2
4 1
5 1
3 2
8
retro
chris
itchy
tuna
crab
rock
cod
ash

Sample Output 1

Yes
Yes
No
No
No
No
No
No

By writing chris, retro, tuna, retro, cod on ribs 1,2,3,4,5 respectively, the conditions are satisfied with retro written on the spine.

• The length of retro is 5.
• For each rib, the following hold.
  • The string written on rib 1 is chris, which has length 5. Its third character is r, which equals the first character of retro.
  • The string written on rib 2 is retro, which has length 5. Its second character is e, which equals the second character of retro.
  • The string written on rib 3 is tuna, which has length 4. Its first character is t, which equals the third character of retro.
  • The string written on rib 4 is retro, which has length 5. Its first character is r, which equals the fourth character of retro.
  • The string written on rib 5 is cod, which has length 3. Its second character is o, which equals the fifth character of retro.

By writing itchy, chris, rock, itchy, ash on ribs 1,2,3,4,5 respectively, the conditions are satisfied with chris written on the spine.

Sample Input 2

5
5 1
5 2
5 3
5 4
5 5
8
retro
chris
itchy
tuna
crab
rock
cod
ash

Sample Output 2

Yes
Yes
Yes
No
No
No
No
No

Problem Statement

You are given two integer sequences A and B, each of length N. Choose integers i, j (1 \leq i, j \leq N) to maximize the value of A_i + B_j.

Constraints

• 1 \leq N \leq 5 \times 10^5
• |A_i| \leq 10^9 (i=1,2,\dots,N)
• |B_j| \leq 10^9 (j=1,2,\dots,N)
• All input values are integers.

Sample Input 1

2
-1 5
3 -7

Sample Output 1

8

For (i,j) = (1,1), (1,2), (2,1), (2,2), the values of A_i + B_j are 2, -8, 8, -2 respectively, and (i,j) = (2,1) achieves the maximum value 8.

Sample Input 2

6
15 12 3 -13 -1 -19
7 17 -13 -10 18 4

Sample Output 2

33

Problem Statement

For i=1,2,\dots,N, let B_i denote the integer formed by concatenating A_i ones.
More formally, B_i=\sum_{j=0}^{A_i-1}{10^j}.
Find \sum_{i=1}^{N}{B_i}.

Constraints

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

Sample Input 1

4
3 3 3 3

Sample Output 1

444

B_1=B_2=B_3=B_4=111, so B_1+B_2+B_3+B_4=444.

Sample Input 2

3
30 10 20

Sample Output 2

111111111122222222223333333333

The answer may be very large.

Sample Input 3

10
1 2 3 4 5 6 7 8 9 10

Sample Output 3

1234567900

Problem Statement

You are given integers A,B,X,Y.

A piece is placed on a two-dimensional plane. Initially, the piece is at coordinate (0,0).

You can perform the following operation zero or more times:

• Let the current coordinate of the piece be (x,y). Move the piece to one of the coordinates (x-1,y),(x+1,y),(x,y-1),(x,y+1).

The cost of the k-th operation (k \geq 1) depends on the parity of k, as follows:

• If k is odd: Let the current coordinate of the piece be (x,y). The cost of moving to (x-1,y) or (x+1,y) is A, and the cost of moving to (x,y-1) or (x,y+1) is B.
• If k is even: Let the current coordinate of the piece be (x,y). The cost of moving to (x-1,y) or (x+1,y) is B, and the cost of moving to (x,y-1) or (x,y+1) is A.

Find the minimum total cost required to move the piece to coordinate (X,Y).

T test cases are given; solve each one.

Constraints

• 1\le T\le 2\times 10^5
• 1\le A,B\le 10^9
• -10^9\le X,Y\le 10^9
• All input values are integers.

Sample Input 1

5
1 2 -1 2
8 5 0 0
7 13 9 4
1 1 0 100
31 9 -74 -60

Sample Output 1

4
0
103
100
1332

Consider the first test case.

The following moves cost 4 in total:

• Move the piece from (0,0) to (-1,0). This costs 1.
• Move the piece from (-1,0) to (-1,1). This costs 1.
• Move the piece from (-1,1) to (-1,2). This costs 2.

It is impossible to move the piece to (-1,2) with a total cost less than 4, so output 4 on the first line.

Problem Statement

You are given a length-N integer sequence A=(A_1,A_2,\dots,A_N).
You can perform the following operation on A any number of times.

• Choose an integer i with 1 \leq i \leq N. For every integer j that is a positive divisor of i, add 1 to A_j.

Determine whether it is possible to make all elements of A equal, and if it is possible, find the minimum number of operations required to do so.

Constraints

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

Sample Input 1

3
4 7 4

Sample Output 1

3

If you choose i=3 for the first operation, you get A=(5,7,5).
If you choose i=3 for the second operation, you get A=(6,7,6).
If you choose i=3 for the third operation, you get A=(7,7,7).
It is impossible to make all elements of A equal with fewer than three operations, so the answer is 3.

Sample Input 2

5
1 3 4 5 6

Sample Output 2

5

Sample Input 3

2
5 2

Sample Output 3

-1