Problem Statement

The ASCII values of the lowercase English letters a, b, \ldots, z are 97,98,\ldots,122 in this order.

Given an integer N between 97 and 122, print the letter whose ASCII value is N.

Constraints

• N is an integer between 97 and 122 (inclusive).

Sample Input 1

97

Sample Output 1

a

97 is the ASCII value of a.

Sample Input 2

122

Sample Output 2

z

Problem Statement

There are N people numbered 1, 2, \ldots, N, sitting in this clockwise order around a round table. In particular, person 1 is sitting next to person N in the clockwise direction.

For each i = 1, 2, \ldots, N, person i has a name S_i and an age A_i. Here, no two people have the same name or the same age.

Starting from the youngest person, print the names of all N people in the order of their seating positions in clockwise order.

Constraints

• 2 \leq N \leq 100
• N is an integer.
• S_i is a string of length between 1 and 10, consisting of lowercase English letters.
• i \neq j \implies S_i \neq S_j
• 0 \leq A_i \leq 10^9
• A_i is an integer.
• i \neq j \implies A_i \neq A_j

Sample Input 1

5
alice 31
bob 41
carol 5
dave 92
ellen 65

Sample Output 1

carol
dave
ellen
alice
bob

The youngest person is person 3. Therefore, starting from person 3, print the names in the clockwise order of their seating positions: person 3, person 4, person 5, person 1, and person 2.

Sample Input 2

2
takahashi 1000000000
aoki 999999999

Sample Output 2

aoki
takahashi

Problem Statement

You are given a horizontally written text. Convert it to vertical writing, filling spaces with *.

You are given N strings S_1, S_2, \dots, S_N consisting of lowercase English letters. Let M be the maximum length of these strings.

Print M strings T_1, T_2, \dots, T_M that satisfy the following conditions:

• Each T_i consists of lowercase English letters and *.
• Each T_i does not end with *.
• For each 1 \leq i \leq N, the following holds:
  • For each 1 \leq j \leq |S_i|, the (N-i+1)-th character of T_j exists, and the concatenation of the (N-i+1)-th characters of T_1, T_2, \dots, T_{|S_i|} in this order equals S_i.
  • For each |S_i| + 1 \leq j \leq M, the (N-i+1)-th character of T_j either does not exist or is *.

Here, |S_i| denotes the length of the string S_i.

Constraints

• N is an integer between 1 and 100, inclusive.
• Each S_i is a string of lowercase English letters with length between 1 and 100, inclusive.

Sample Input 1

3
abc
de
fghi

Sample Output 1

fda
geb
h*c
i

Placing * as the 2nd character of T_3 puts the c in the correct position. On the other hand, placing * as the 2nd and 3rd characters of T_4 would make T_4 end with *, which violates the condition.

Sample Input 2

3
atcoder
beginner
contest

Sample Output 2

cba
oet
ngc
tio
end
sne
ter
*r

Problem Statement

Takahashi is playing a game called Chess960. He has decided to write a code that determines if a random initial state satisfies the conditions of Chess960.

You are given a string S of length eight. S has exactly one K and Q, and exactly two R's, B's , and N's. Determine if S satisfies all of the following conditions.

• Suppose that the x-th and y-th (x < y) characters from the left of S are B; then, x and y have different parities.

• K is between two R's. More formally, suppose that the x-th and y-th (x < y) characters from the left of S are R and the z-th is K; then x< z < y.

Constraints

• S is a string of length 8 that contains exactly one K and Q, and exactly two R's, B's , and N's.

Sample Input 1

RNBQKBNR

Sample Output 1

Yes

The 3-rd and 6-th characters are B, and 3 and 6 have different parities. Also, K is between the two R's. Thus, the conditions are fulfilled.

Sample Input 2

KRRBBNNQ

Sample Output 2

No

K is not between the two R's.

Sample Input 3

BRKRBQNN

Sample Output 3

No

Problem Statement

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

Determine if there is an even number represented as the sum of two different elements of A. If it exists, find the maximum such number.

Constraints

• 2\leq N \leq 2\times 10^5
• 0\leq A_i\leq 10^9
• The elements of A are distinct.
• All values in the input are integers.

Sample Input 1

3
2 3 4

Sample Output 1

6

The values represented as the sum of two distinct elements of A are 5, 6, and 7. We have an even number here, and the maximum is 6.

Sample Input 2

2
1 0

Sample Output 2

-1

The value represented as the sum of two distinct elements of A is 1. We have no even number here, so -1 should be printed.

Problem Statement

You are given strictly increasing sequences of length N and M: A=(A _ 1,A _ 2,\ldots,A _ N) and B=(B _ 1,B _ 2,\ldots,B _ M). Here, A _ i\neq B _ j for every i and j (1\leq i\leq N,1\leq j\leq M).

Let C=(C _ 1,C _ 2,\ldots,C _ {N+M}) be a strictly increasing sequence of length N+M that results from the following procedure.

• Let C be the concatenation of A and B. Formally, let C _ i=A _ i for i=1,2,\ldots,N, and C _ i=B _ {i-N} for i=N+1,N+2,\ldots,N+M.
• Sort C in ascending order.

For each of A _ 1,A _ 2,\ldots,A _ N, B _ 1,B _ 2,\ldots,B _ M, find its position in C. More formally, for each i=1,2,\ldots,N, find k such that C _ k=A _ i, and for each j=1,2,\ldots,M, find k such that C _ k=B _ j.

Constraints

• 1\leq N,M\leq 10^5
• 1\leq A _ 1\lt A _ 2\lt\cdots\lt A _ N\leq 10^9
• 1\leq B _ 1\lt B _ 2\lt\cdots\lt B _ M\leq 10^9
• A _ i\neq B _ j for every i and j (1\leq i\leq N,1\leq j\leq M).
• All values in the input are integers.

Sample Input 1

4 3
3 14 15 92
6 53 58

Sample Output 1

1 3 4 7
2 5 6

C will be (3,6,14,15,53,58,92). Here, the 1-st, 3-rd, 4-th, 7-th elements are from A=(3,14,15,92), and the 2-nd, 5-th, 6-th elements are from B=(6,53,58).

Sample Input 2

4 4
1 2 3 4
100 200 300 400

Sample Output 2

1 2 3 4
5 6 7 8

Sample Input 3

8 12
3 4 10 15 17 18 22 30
5 7 11 13 14 16 19 21 23 24 27 28

Sample Output 3

1 2 5 9 11 12 15 20
3 4 6 7 8 10 13 14 16 17 18 19

Problem Statement

For non-negative integers l and r (l < r), let S(l, r) denote the sequence (l, l+1, \ldots, r-2, r-1) formed by arranging integers from l through r-1 in order. Furthermore, a sequence is called a good sequence if and only if it can be represented as S(2^i j, 2^i (j+1)) using non-negative integers i and j.

You are given non-negative integers L and R (L < R). Divide the sequence S(L, R) into the fewest number of good sequences, and print that number of sequences and the division. More formally, find the minimum positive integer M for which there is a sequence of pairs of non-negative integers (l_1, r_1), (l_2, r_2), \ldots, (l_M, r_M) that satisfies the following, and print such (l_1, r_1), (l_2, r_2), \ldots, (l_M, r_M).

• L = l_1 < r_1 = l_2 < r_2 = \cdots = l_M < r_M = R
• S(l_1, r_1), S(l_2, r_2), \ldots, S(l_M, r_M) are good sequences.

It can be shown that there is only one division that minimizes M.

Constraints

• 0 \leq L < R \leq 2^{60}
• All input values are integers.

Sample Input 1

3 19

Sample Output 1

5
3 4
4 8
8 16
16 18
18 19

S(3,19)=(3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18) can be divided into the following five good sequences, which is the minimum possible number:

• S(3,4)=S(2^0\cdot 3,2^0\cdot4)=(3)
• S(4,8)=S(2^2\cdot 1,2^2\cdot 2)=(4,5,6,7)
• S(8,16)=S(2^3\cdot 1,2^3\cdot 2)=(8,9,10,11,12,13,14,15)
• S(16,18)=S(2^1\cdot 8,2^1\cdot 9)=(16,17)
• S(18,19)=S(2^0\cdot 18,2^0\cdot 19)=(18)

Sample Input 2

0 1024

Sample Output 2

1
0 1024

Sample Input 3

3940649673945088 11549545024454656

Sample Output 3

8
3940649673945088 3940649673949184
3940649673949184 4503599627370496
4503599627370496 9007199254740992
9007199254740992 11258999068426240
11258999068426240 11540474045136896
11540474045136896 11549270138159104
11549270138159104 11549545016066048
11549545016066048 11549545024454656

Problem Statement

In a two-dimensional plane, there are N towns and M chests. Town i is at the coordinates (X_i,Y_i), and chest i is at the coordinates (P_i,Q_i).

Takahashi will go on a trip where he starts at the origin, visits all N towns, and then returns to the origin.
It is not mandatory to visit chests, but each chest contains an accelerator. Each time he picks up an accelerator, his moving speed gets multiplied by 2.

Takahashi's initial moving speed is 1. Find the shortest time needed to complete the trip.

Constraints

• 1 \leq N \leq 12
• 0 \leq M \leq 5
• -10^9 \leq X_i,Y_i,P_i,Q_i \leq 10^9
• (0,0), (X_i,Y_i), and (P_i,Q_i) are distinct.
• All values in the input are integers.

Sample Input 1

2 1
1 1
0 1
1 0

Sample Output 1

2.5000000000

Here is one optimal way to complete the trip.

• Go the distance 1 from the origin to chest 1 at a speed of 1, taking a time of 1.
• Go the distance 1 from chest 1 to town 1 at a speed of 2, taking a time of 0.5.
• Go the distance 1 from town 1 to town 2 at a speed of 2, taking a time of 0.5.
• Go the distance 1 from town 2 to the origin at a speed of 2, taking a time of 0.5.

Sample Input 2

2 1
1 1
0 1
100 0

Sample Output 2

3.4142135624

Here is one optimal way to complete the trip.

• Go the distance 1.41\ldots from the origin to town 1 at a speed of 1, taking a time of 1.41\ldots.
• Go the distance 1 from town 1 to town 2 at a speed of 1, taking a time of 1.
• Go the distance 1 from town 2 to the origin at a speed of 1, taking a time of 1.

Sample Input 3

1 2
4 4
1 0
0 1

Sample Output 3

4.3713203436

Here is one optimal way to complete the trip.

• Go the distance 1 from the origin to chest 1 at a speed of 1, taking a time of 1.
• Go the distance 1.41\ldots from chest 1 to chest 2 at a speed of 2, taking a time of 0.707\ldots.
• Go the distance 5 from chest 2 to town 1 at a speed of 4, taking a time of 1.25.
• Go the distance 5.65\ldots from town 1 to the origin at a speed of 4, taking a time of 1.41\ldots.

Problem Statement

There is a directed graph with N vertices and M edges. Each edge has two positive integer values: beauty and cost.

For i = 1, 2, \ldots, M, the i-th edge is directed from vertex u_i to vertex v_i, with beauty b_i and cost c_i. Here, the constraints guarantee that u_i \lt v_i.

Find the maximum value of the following for a path P from vertex 1 to vertex N.

• The total beauty of all edges on P divided by the total cost of all edges on P.

Here, the constraints guarantee that the given graph has at least one path from vertex 1 to vertex N.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 2 \times 10^5
• 1 \leq u_i \lt v_i \leq N
• 1 \leq b_i, c_i \leq 10^4
• There is a path from vertex 1 to vertex N.
• All input values are integers.

Sample Input 1

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

Sample Output 1

0.7500000000000000

For the path P that passes through the 2-nd, 6-th, and 7-th edges in this order and visits vertices 1 \rightarrow 3 \rightarrow 4 \rightarrow 5, the total beauty of all edges on P divided by the total cost of all edges on P is (b_2 + b_6 + b_7) / (c_2 + c_6 + c_7) = (9 + 4 + 2) / (5 + 8 + 7) = 15 / 20 = 0.75, and this is the maximum possible value.

Sample Input 2

3 3
1 3 1 1
1 3 2 1
1 3 3 1

Sample Output 2

3.0000000000000000

Sample Input 3

10 20
3 4 1 2
7 9 4 5
2 4 4 5
4 5 1 4
6 9 4 1
9 10 3 2
6 10 5 5
5 6 1 2
5 6 5 2
2 3 2 3
6 10 4 4
4 6 3 4
4 8 4 1
3 5 3 2
2 4 3 2
3 5 4 2
1 5 3 4
1 2 4 2
3 7 2 2
7 8 1 3

Sample Output 3

1.8333333333333333