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

Takahashi has N foods in his house. The i-th food has the tastiness of A_i.
He dislikes K of these foods: for each i=1,2,\ldots,K, he dislikes the B_i-th food.

Out of the foods with the greatest tastiness among the N foods, Takahashi will randomly choose one and eat it.
If he has a chance to eat something he dislikes, print Yes; otherwise, print No.

Constraints

• 1\leq K\leq N\leq 100
• 1\leq A_i\leq 100
• 1\leq B_i\leq N
• All B_i are distinct.
• All values in input are integers.

Sample Input 1

5 3
6 8 10 7 10
2 3 4

Sample Output 1

Yes

Among the five foods, the ones with the greatest tastiness are Food 3 and 5, of which he eats one.
He dislikes Food 2, 3, and 4, one of which he has a chance to eat: Food 3.
Therefore, the answer is Yes.

Sample Input 2

5 2
100 100 100 1 1
5 4

Sample Output 2

No

The foods with the greatest tastiness are Food 1, 2, and 3, none of which he has a chance to eat.

Sample Input 3

2 1
100 1
2

Sample Output 3

No

The food with the greatest tastiness is Food 1, which he has no chance to eat.

Problem Statement

There is a slot machine with N reels.
The placement of symbols on the i-th reel is represented by a string S_i of length 10 containing each of 0, 1, \ldots, 9 exactly once.

Each reel has a corresponding button. For each non-negative integer t, Takahashi can press one of the buttons of his choice (or do nothing) t seconds after the reels start spinning.
If the button for the i-th reel is pressed t seconds after the start of the spin, the i-th reel will stop to display the ((t\bmod{10})+1)-th character of S_i.
Here, t\bmod{10} denotes the remainder when t is divided by 10.

Takahashi wants to stop all reels to make them display the same character.
Find the minimum number of seconds needed to achieve his objective after the start of the spin.

Constraints

• 2\leq N\leq 100
• N is an integer.
• S_i is a string of length 10 containing each of 0, 1, \ldots, 9 exactly once.

Sample Input 1

3
1937458062
8124690357
2385760149

Sample Output 1

6

Takahashi can make all reels display 8 in 6 seconds after the start of the spin by stopping them as follows.

• 0 seconds after the start of the spin, press the button for the 2-nd reel, making it stop to display the ((0\bmod{10})+1=1)-st character of S_2, 8.
• 2 seconds after the start of the spin, press the button for the 3-rd reel, making it stop to display the ((2\bmod{10})+1=3)-rd character of S_3, 8.
• 6 seconds after the start of the spin, press the button for the 1-st reel, making it stop to display the ((6\bmod{10})+1=7)-th character of S_1, 8.

There is no way to make all reels display the same character in five seconds or less, so the answer is 6.

Sample Input 2

5
0123456789
0123456789
0123456789
0123456789
0123456789

Sample Output 2

40

Note that he must stop all reels to make them display the same character.

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

The Kingdom of AtCoder has N cities called City 1,2,\ldots,N and M roads called Road 1,2,\ldots,M.
Road i connects Cities A_i and B_i bidirectionally and has a length of C_i.
One can travel between any two cities using some roads.

Under financial difficulties, the kingdom has decided to maintain only N-1 roads so that one can still travel between any two cities using those roads and abandon the rest.

Let d_i be the total length of the roads one must use when going from City 1 to City i using only maintained roads. Print a choice of roads to maintain that minimizes d_2+d_3+\ldots+d_N.

Constraints

• 2 \leq N \leq 2\times 10^5
• N-1 \leq M \leq 2\times 10^5
• 1 \leq A_i < B_i \leq N
• (A_i,B_i)\neq(A_j,B_j) if i\neq j.
• 1\leq C_i \leq 10^9
• One can travel between any two cities using some roads.
• All values in input are integers.

Sample Input 1

3 3
1 2 1
2 3 2
1 3 10

Sample Output 1

1 2

Here are the possible choices of roads to maintain and the corresponding values of d_i.

• Maintain Road 1 and 2: d_2=1, d_3=3.
• Maintain Road 1 and 3: d_2=1, d_3=10.
• Maintain Road 2 and 3: d_2=12, d_3=10.

Thus, maintaining Road 1 and 2 minimizes d_2+d_3.

Sample Input 2

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

Sample Output 2

3 1 2

Problem Statement

We have a loaf of bread of length L, which we will cut and distribute to N children.
The i-th child (1\leq i\leq N) wants a loaf of length A_i.

Now, Takahashi will repeat the operation below to cut the loaf into lengths A_1, A_2, \ldots, A_N for the children.

Choose a loaf of length k and an integer x between 1 and k-1 (inclusive). Cut the loaf into two loaves of length x and k-x.
This operation incurs a cost of k regardless of the value of x.

Each child i must receive a loaf of length exactly A_i, but it is allowed to leave some loaves undistributed.

Find the minimum cost needed to distribute loaves to all children.

Constraints

• 2 \leq N \leq 2\times 10^5
• 1\leq A_i\leq 10^9
• A_1+A_2+\cdots+A_N\leq L\leq 10^{15}
• All values in input are integers.

Sample Input 1

5 7
1 2 1 2 1

Sample Output 1

16

Takahashi can cut the loaf for the children as follows.

• Choose the loaf of length 7 and x=3, cutting it into loaves of length 3 and 4 for a cost of 7.
• Choose the loaf of length 3 and x=1, cutting it into loaves of length 1 and 2 for a cost of 3. Give the former to the 1-st child.
• Choose the loaf of length 2 and x=1, cutting it into two loaves of length 1 for a cost of 2. Give them to the 3-rd and 5-th children.
• Choose the loaf of length 4 and x=2, cutting it into two loaves of length 2 for a cost of 4. Give them to the 2-nd and 4-th children.

This incurs a cost of 7+3+2+4=16, which is the minimum possible. There will be no leftover loaves.

Sample Input 2

3 1000000000000000
1000000000 1000000000 1000000000

Sample Output 2

1000005000000000

Note that each child i must receive a loaf of length exactly A_i.

Problem Statement

There is a rooted tree with N vertices called Vertex 1, 2, \ldots, N, rooted at Vertex 1.

We performed a depth-first search starting at the root and obtained a preorder traversal of the tree: P_1, P_2, \ldots, P_N.
During the search, when the current vertex had multiple children, we chose the unvisited vertex with the smallest index.

Find the number of rooted trees consistent with the preorder traversal, modulo 998244353.
Two rooted trees (with N vertices and rooted at Vertex 1) are considered different when there is a non-root vertex whose parent is different in the two trees.

Constraints

• 2 \leq N \leq 500
• 1 \leq P_i\leq N
• P_1=1
• All P_i are distinct.
• All values in input are integers.

Sample Input 1

4
1 2 4 3

Sample Output 1

3

The rooted trees consistent with the preorder traversal are the three shown below, so the answer is 3.

Note that the tree below does not count. This is because, among the children of Vertex 2, we visit Vertex 3 before visiting Vertex 4, resulting in the preorder traversal 1,2,3,4.

Sample Input 2

8
1 2 3 5 6 7 8 4

Sample Output 2

202

Problem Statement

We have N gemstones. The color and beauty of the i-th gemstone are D_i and V_i, respectively.
Here, the color of each gemstone is one of 1, 2, \ldots, C, and there is at least one gemstone of each color.

Out of the N gemstones, we will choose C with distinct colors and use them to make a necklace. (The order does not matter.) The beautifulness of the necklace will be the bitwise \rm XOR of the chosen gemstones.

Among all possible ways to make a necklace, find the beautifulness of the necklace made in the way with the K-th greatest beautifulness. (If there are multiple ways with the same beautifulness, we count all of them.)

Constraints

• 1 \leq C \leq N \leq 70
• 1 \leq D_i \leq C
• 0 \leq V_i < 2^{60}
• 1 \leq K \leq 10^{18}
• There are at least K ways to make a necklace.
• All values in input are integers.

Sample Input 1

4 2 3
2 4
2 6
1 2
1 3

Sample Output 1

5

There are four ways to make a necklace, as follows.

• Choose the 1-st and 3-rd gemstones to make a necklace with the beautifulness of 4\ {\rm XOR}\ 2 =6.
• Choose the 1-st and 4-th gemstones to make a necklace with the beautifulness of 4\ {\rm XOR}\ 3 =7.
• Choose the 2-nd and 3-rd gemstones to make a necklace with the beautifulness of 6\ {\rm XOR}\ 2 =4.
• Choose the 2-nd and 4-th gemstones to make a necklace with the beautifulness of 6\ {\rm XOR}\ 3 =5.

Thus, the necklace with the 3-rd greatest beautifulness has the beautifulness of 5.

Sample Input 2

3 1 2
1 0
1 0
1 0

Sample Output 2

0

There are three ways to make a necklace, all of which result in the beautifulness of 0.

Sample Input 3

10 3 11
1 414213562373095048
1 732050807568877293
2 236067977499789696
2 449489742783178098
2 645751311064590590
2 828427124746190097
3 162277660168379331
3 316624790355399849
3 464101615137754587
3 605551275463989293

Sample Output 3

766842905529259824