Problem Statement

Find the X-th character from the beginning of the string that is obtained by concatenating these characters: N copies of A's, N copies of B's, …, and N copies of Z's, in this order.

Constraints

• 1 \leq N \leq 100
• 1 \leq X \leq N\times 26
• All values in input are integers.

Sample Input 1

1 3

Sample Output 1

C

We obtain the string ABCDEFGHIJKLMNOPQRSTUVWXYZ, whose 3-rd character from the beginning is C.

Sample Input 2

2 12

Sample Output 2

F

We obtain the string AABBCCDDEEFFGGHHIIJJKKLLMMNNOOPPQQRRSSTTUUVVWWXXYYZZ, whose 12-th character from the beginning is F.

Problem Statement

There are N squares, indexed Square 1, Square 2, …, Square N, arranged in a row from left to right.
Also, there are K pieces. The i-th piece from the left is initially placed on Square A_i.
Now, we will perform Q operations against them. The i-th operation is as follows:

• If the L_i-th piece from the left is on its rightmost square, do nothing.
• Otherwise, move the L_i-th piece from the left one square right if there is no piece on the next square on the right; if there is, do nothing.

Print the index of the square on which the i-th piece from the left is after the Q operations have ended, for each i=1,2,\ldots,K.

Constraints

• 1\leq K\leq N\leq 200
• 1\leq A_1<A_2<\cdots<A_K\leq N
• 1\leq Q\leq 1000
• 1\leq L_i\leq K
• All values in input are integers.

Sample Input 1

5 3 5
1 3 4
3 3 1 1 2

Sample Output 1

2 4 5

At first, the pieces are on Squares 1, 3, and 4. The operations are performed against them as follows:

• The 3-rd piece from the left is on Square 4. This is not the rightmost square, and the next square on the right does not contain a piece, so move the 3-rd piece from the left to Square 5. Now, the pieces are on Squares 1, 3, and 5.
• The 3-rd piece from the left is on Square 5. This is the rightmost square, so do nothing. The pieces are still on Squares 1, 3, and 5.
• The 1-st piece from the left is on Square 1. This is not the rightmost square, and the next square on the right does not contain a piece, so move the 1-st piece from the left to Square 2. Now, the pieces are on Squares 2, 3, and 5.
• The 1-st piece from the left is on Square 2. This is not the rightmost square, but the next square on the right (Square 3) contains a piece, so do nothing. The pieces are still on Squares 2, 3, and 5.
• The 2-nd piece from the left is on Square 3. This is not the rightmost square, and the next square on the right does not contain a piece, so move the 2-nd piece from the left to Square 4; Now, the pieces are still on Squares 2, 4, and 5.

Thus, after the Q operations have ended, the pieces are on Squares 2, 4, and 5, so 2, 4, and 5 should be printed in this order, with spaces in between.

Sample Input 2

2 2 2
1 2
1 2

Sample Output 2

1 2

Sample Input 3

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

Sample Output 3

2 5 6 7 9 10

Problem Statement

There are N people, each of whom is either a child or an adult. The i-th person has a weight of W_i.
Whether each person is a child or an adult is specified by a string S of length N consisting of 0 and 1.
If the i-th character of S is 0, then the i-th person is a child; if it is 1, then the i-th person is an adult.

When Takahashi the robot is given a real number X, Takahashi judges a person with a weight less than X to be a child and a person with a weight more than or equal to X to be an adult.
For a real value X, let f(X) be the number of people whom Takahashi correctly judges whether they are children or adults.

Find the maximum value of f(X) for all real values of X.

Constraints

• 1\leq N\leq 2\times 10^5
• S is a string of length N consisting of 0 and 1.
• 1\leq W_i\leq 10^9
• N and W_i are integers.

Sample Input 1

5
10101
60 45 30 40 80

Sample Output 1

4

When Takahashi is given X=50, it judges the 2-nd, 3-rd, and 4-th people to be children and the 1-st and 5-th to be adults.
In reality, the 2-nd and 4-th are children, and the 1-st, 3-rd, and 5-th are adults, so the 1-st, 2-nd, 4-th, and 5-th people are correctly judged. Thus, f(50)=4.

This is the maximum since there is no X that judges correctly for all 5 people. Thus, 4 should be printed.

Sample Input 2

3
000
1 2 3

Sample Output 2

3

For example, X=10 achieves the maximum value f(10)=3.
Note that the people may be all children or all adults.

Sample Input 3

5
10101
60 50 50 50 60

Sample Output 3

4

For example, X=55 achieves the maximum value f(55)=4.
Note that there may be multiple people with the same weight.

Problem Statement

There are N trampolines on a two-dimensional planar town where Takahashi lives. The i-th trampoline is located at the point (x_i, y_i) and has a power of P_i. Takahashi's jumping ability is denoted by S. Initially, S=0. Every time Takahashi trains, S increases by 1.

Takahashi can jump from the i-th to the j-th trampoline if and only if:

• P_iS\geq |x_i - x_j| +|y_i - y_j|.

Takahashi's objective is to become able to choose a starting trampoline such that he can reach any trampoline from the chosen one with some jumps.

At least how many times does he need to train to achieve his objective?

Constraints

• 2 \leq N \leq 200
• -10^9 \leq x_i,y_i \leq 10^9
• 1 \leq P_i \leq 10^9
• (x_i, y_i) \neq (x_j,y_j)\ (i\neq j)
• All values in input are integers.

Sample Input 1

4
-10 0 1
0 0 5
10 0 1
11 0 1

Sample Output 1

2

If he trains twice, S=2, in which case he can reach any trampoline from the 2-nd one.

For example, he can reach the 4-th trampoline as follows.

• Jump from the 2-nd to the 3-rd trampoline. (Since P_2 S = 10 and |x_2-x_3| + |y_2-y_3| = 10, it holds that P_2 S \geq |x_2-x_3| + |y_2-y_3|.)

• Jump from the 3-rd to the 4-th trampoline. (Since P_3 S = 2 and |x_3-x_4| + |y_3-y_4| = 1, it holds that P_3 S \geq |x_3-x_4| + |y_3-y_4|.)

Sample Input 2

7
20 31 1
13 4 3
-10 -15 2
34 26 5
-2 39 4
0 -50 1
5 -20 2

Sample Output 2

18

Problem Statement

Takahashi has an integer x. Initially, x=0.

Takahashi may do the following operation any number of times.

• Choose an integer i\ (1\leq i \leq 9). Pay C_i yen (the currency in Japan) to replace x with 10x + i.

Takahashi has a budget of N yen. Find the maximum possible value of the final x resulting from operations without exceeding the budget.

Constraints

• 1 \leq N \leq 10^6
• 1 \leq C_i \leq N
• All values in input are integers.

Sample Input 1

5
5 4 3 3 2 5 3 5 3

Sample Output 1

95

For example, the operations where i = 9 and i=5 in this order change x as:

0 \rightarrow 9 \rightarrow 95.

The amount of money required for these operations is C_9 + C_5 = 3 + 2 = 5 yen, which does not exceed the budget. Since we can prove that we cannot make an integer greater than or equal to 96 without exceeding the budget, the answer is 95.

Sample Input 2

20
1 1 1 1 1 1 1 1 1

Sample Output 2

99999999999999999999

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

Problem Statement

There are N towns numbered Town 1, Town 2, \ldots, Town N.
There are also M Teleporters, each of which connects two towns bidirectionally so that a person can travel from one to the other in one minute.

The i-th Teleporter connects Town U_i and Town V_i bidirectionally. However, for some of the Teleporters, one of the towns it connects is undetermined; U_i=0 means that one of the towns the i-th Teleporter connects is Town V_i, but the other end is undetermined.

For i=1,2,\ldots,N, answer the following question.

When the Teleporters with undetermined ends are all determined to be connected to Town i, how many minutes is required at minimum to travel from Town 1 to Town N? If it is impossible to travel from Towns 1 to N using Teleporters only, print -1 instead.

Constraints

• 2 \leq N \leq 3\times 10^5
• 1\leq M\leq 3\times 10^5
• 0\leq U_i<V_i\leq N
• If i \neq j, then (U_i,V_i)\neq (U_j,V_j).
• All values in input are integers.

Sample Input 1

3 2
0 2
1 2

Sample Output 1

-1 -1 2

When the Teleporters with an undetermined end are all determined to be connected to Town 1,
the 1-st and the 2-nd Teleporters both connect Towns 1 and 2. Then, it is impossible to travel from Town 1 to Town 3.

When the Teleporters with an undetermined end are all determined to be connected to Town 2,
the 1-st Teleporter connects Town 2 and itself, and the 2-nd one connects Towns 1 and 2. Again, it is impossible to travel from Town 1 to Town 3.

When the Teleporters with an undetermined end are all determined to be connected to Town 3,
the 1-st Teleporter connects Town 3 and Town 2, and the 2-nd one connects Towns 1 and 2. In this case, we can travel from Town 1 to Town 3 in two minutes.

• Use the 2-nd Teleporter to travel from Town 1 to Town 2.
• Use the 1-st Teleporter to travel from Town 2 to Town 3.

Therefore, -1,-1, and 2 should be printed in this order.

Note that, depending on which town the Teleporters with an undetermined end are connected to, there may be a Teleporter that connects a town and itself, or multiple Teleporters that connect the same pair of towns.

Sample Input 2

5 5
1 2
1 3
3 4
4 5
0 2

Sample Output 2

3 3 3 3 2

Problem Statement

You are given two strings S and T consisting of lowercase English letters.

Find the minimum positive integer k such that you can choose (not necessarily distinct) k prefixes of S so that their concatenation coincides with T.

In other words, find the minimum positive integer k such that there exists a k-tuple (a_1,a_2,\ldots, a_k) of integers between 1 and |S| such that
T=S_{a_1}+S_{a_2}+\cdots +S_{a_k}, where S_i denotes the substring of S from the 1-st through the i-th characters and + denotes the concatenation of strings.

If it is impossible to make it coincide with T, print -1 instead.

Constraints

• 1 \leq |S| \leq 5\times 10^5
• 1 \leq |T| \leq 5\times 10^5
• S and T are strings consisting of lowercase English letters.

Sample Input 1

aba
ababaab

Sample Output 1

3

T= ababaab can be written as ab + aba + ab, of which ab and aba are prefixes of S= aba.
Since it is unable to express ababaab with two or less prefixes of aba, print 3.

Sample Input 2

atcoder
ac

Sample Output 2

-1

Since it is impossible to express T as a concatenation of prefixes of S, print -1.

Problem Statement

The six-sided dice speciality shop "Saikoroya" sells N dice. The i-th die (singular of dice) has A_{i,1},A_{i,2},\ldots,A_{i,6} written on its each side, and has a price of C_i.

Takahashi is going to choose exactly K of them and buy them.

Currently, "Saikoroya" is conducting a promotion: Takahashi may roll each of the purchased dice once and claim money whose amount is equal to the square of the sum of the numbers shown by the dice. Here, each die shows one of the six numbers uniformly at random and independently.

Maximize the expected value of (the amount of money he claims) - (the sum of money he pays for the purchased K dice) by properly choosing K dice to buy. Print the maximized expected value modulo 998244353.

Constraints

• 1 \leq N \leq 1000
• 1 \leq K \leq N
• 1 \leq C_i \leq 10^5
• 1 \leq A_{i,j} \leq 10^5
• All values in input are integers.

Sample Input 1

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

Sample Output 1

20

If he buys the 2-nd and 3-rd dice, the expected value of (the amount of money he claims) - (the sum of money he pays for the purchased K dice) equals (2 + 3)^2 - (2 + 3) = 20, which is the maximum expected value.

Sample Input 2

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

Sample Output 2

1014