Problem Statement

You are given positive integers A and B.

If at least one of the following values is equal to 9, output Nine; otherwise, output Nein.

• A + B
• A - B
• A \times B
• A \div B

Constraints

• 1 \leq A \leq 100
• 1 \leq B \leq 100
• All input values are integers.

Sample Input 1

16 7

Sample Output 1

Nine

Since 16 - 7 = 9, output Nine.

Sample Input 2

66 7

Sample Output 2

Nein

None of the following values is equal to 9, so output Nein.

• 66 + 7 = 73
• 66 - 7 = 59
• 66 \times 7 = 462
• 66 \div 7 = \frac{66}{7}

Sample Input 3

9 1

Sample Output 3

Nine

Sample Input 4

9 9

Sample Output 4

Nein

Problem Statement

Takahashi is tallying the results of a survey.

N people answered the survey, and the i-th person's answer is a string S_i consisting of English letters.

Find the maximum number of people who gave the same answer in this survey.
Here, the case of the letters in the answers is not distinguished.
For example, AtCoder, ATCODER, and atcoder are all considered the same answer.

Constraints

• 1 \leq N \leq 100
• S_i is a string of length between 1 and 10 (inclusive) consisting of uppercase and lowercase English letters.
• N is an integer.

Sample Input 1

7
ARC
abc
ahc
ABC
beginner
AbC
ahc

Sample Output 1

3

There are three answers that are the same as ABC, and this number is the maximum.

Sample Input 2

10
x
x
x
x
x
x
x
x
x
x

Sample Output 2

10

Problem Statement

There are cookies at N positions on a number line. The coordinate of the i-th cookie is A_i.

Takahashi is initially at coordinate 0 on the number line, and repeats the following action until he has picked up all N cookies.

• Action: Move to the coordinate of the nearest cookie from his current position (if there are multiple such cookies, the one with the smallest coordinate), and pick up that cookie.

Find the total distance Takahashi travels until he picks up all the cookies.

Constraints

• 1 \leq N \leq 3\times 10^5
• -10^9 \leq A_i \leq 10^9
• A_i\neq 0
• The A_i are distinct.
• All input values are integers.

Sample Input 1

4
-1 -4 2 -11

Sample Output 1

23

Takahashi acts as follows.

• He moves from coordinate 0 to coordinate -1 and picks up the cookie. The distance traveled is 1.
• He moves from coordinate -1 to coordinate -4 and picks up the cookie. The distance traveled is 3.
• He moves from coordinate -4 to coordinate 2 and picks up the cookie. The distance traveled is 6.
• He moves from coordinate 2 to coordinate -11 and picks up the cookie. The distance traveled is 13.

Thus, the total distance traveled is 1+3+6+13=23.

In the second action, the distances to the cookie at coordinate -4 and the cookie at coordinate 2 are both 3, and Takahashi moves to -4, the smaller coordinate.

Sample Input 2

10
1 2 3 4 5 -1 -2 -3 -4 -6

Sample Output 2

17

Problem Statement

There is a charger with an unlimited number of charging slots. At time 0, all slots are empty.

The maximum capacity of a battery is V. While a battery is plugged into a slot, it is charged at a rate of 1 until its charge level reaches the maximum capacity (that is, the charge level increases by 1 for every 1 unit of time that passes).

Process Q queries in order. The q-th query is given in one of the following formats. Here, it is guaranteed that t_1 < \dots < t_Q.

• Type 1 (1\ t_q\ w_q): At time t_q, plug one battery with charge level w_q into a slot.
• Type 2 (2\ t_q): At time t_q, unplug one battery with the highest charge level from its slot, and output that battery's charge level. If there is no battery plugged into any slot, output -1 instead.

Constraints

• 1 \leq Q \leq 3 \times 10^5
• 1 \leq V \leq 10^9
• For type 1 queries, 1 \leq t_q \leq 10^9.
• For type 1 queries, 0 \leq w_q \leq V.
• For type 2 queries, 1 \leq t_q \leq 10^9.
• t_1 < \dots < t_Q
• The input values are all integers.

Sample Input 1

7 100
1 15 60
1 25 80
2 30
1 45 0
2 60
2 70
2 80

Sample Output 1

85
100
25
-1

The seven queries are processed in the following order.

• At time 15, a battery with charge level 60 is plugged in. At this point, the charger has a battery with charge level 60.
• At time 25, a battery with charge level 80 is plugged in. At this point, the charger has batteries with charge levels 70, 80.
• At time 30, the charger has batteries with charge levels 75, 85. Of these, the battery with charge level 85 is unplugged.
• At time 45, a battery with charge level 0 is plugged in. At this point, the charger has batteries with charge levels 0, 90.
• At time 60, the charger has batteries with charge levels 15, 100. Of these, the battery with charge level 100 is unplugged.
• At time 70, the charger has a battery with charge level 25. This battery, with charge level 25, is unplugged.
• At time 80, no battery is plugged into the charger. Thus, no battery is unplugged.

Sample Input 2

20 380736236
1 21873985 256702097
2 86369729
1 114301317 288304981
1 147244640 305840435
2 150951976
1 331581391 50335458
1 352989552 47577202
1 400130024 345362760
2 458793150
2 509082216
1 591375600 197371572
1 617022014 101276068
1 679649471 310249627
1 796351653 268586022
1 825648347 129608152
2 908069704
2 921770319
1 949684819 372272469
1 971850999 335461408
2 986253026

Sample Output 2

321197841
324955640
380736236
380736236
380736236
380736236
380736236

Problem Statement

There are N balls numbered 1 to N. Ball i has an integer A_i written on it.

For a way of choosing some balls from the N balls, define the score of that choice as the square of the sum of the numbers written on the chosen balls.

Find the sum, modulo 998244353, of the scores of all \binom{N}{K} ways of choosing K balls from the N balls.

Constraints

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

Sample Input 1

3 2
1 10 100

Sample Output 1

22422

There are three ways of choosing two balls from three balls: choosing balls 1,2 gives a score of (1+10)^2=121, choosing balls 1,3 gives a score of (1+100)^2=10201, and choosing balls 2,3 gives a score of (10+100)^2=12100.

The answer is the sum of these, 121+10201+12100=22422.

Sample Input 2

5 2
10 10 20 20 20

Sample Output 2

10600

Multiple balls may have the same number written on them.

Sample Input 3

2 1
998244353 998244353

Sample Output 3

0

Find the sum modulo 998244353.

Problem Statement

You are given N strings S_1,\ldots,S_N consisting of digits.

Find the maximum possible value, when interpreted as a decimal integer (after removing extra leading zeros), of a string obtained by choosing exactly K of these strings and concatenating them in any order of your choice.

Here, the value obtained by interpreting a string consisting entirely of the character 0 as a decimal integer after removing extra leading zeros is defined to be 0.

Constraints

• 1 \leq K \leq N \leq 10^5
• S_i is a string of length between 1 and 10 (inclusive) consisting of digits.
• N and K are integers.

Sample Input 1

3 2
123
45
6

Sample Output 1

45123

There are six strings obtained by choosing two of 123, 45, 6 and concatenating them: 12345, 1236, 45123, 456, 6123, 645.

Among these, the maximum value when interpreted as a decimal integer is 45123.

Sample Input 2

5 3
00000
00
1
0000
000

Sample Output 2

1000000000

Sample Input 3

9 9
0000000001
000000002
00000003
0000004
000005
00006
0007
008
09

Sample Output 3

90080007000060000050000004000000030000000020000000001

The answer must be output without extra leading zeros.

Problem Statement

There are K kinds of symbols numbered 0 to K-1.

Each symbol is either a vowel or not a vowel. If V_j = 1, symbol j is a vowel; if V_j = 0, symbol j is not a vowel.

Define the number of syllables of a symbol string as the number of maximal contiguous substrings of that string consisting of vowels. Formally, the number of syllables of a length-N symbol string (a_1, \dots, a_N) is defined as the number of pairs of integers (l,r) satisfying 1 \leq l \leq r \leq N and all of the following:

• The symbols a_l, \dots, a_r are all vowels.
• If l > 1, symbol a_{l-1} is not a vowel.
• If r < N, symbol a_{r+1} is not a vowel.

You are given a length-N sequence A = (A_1, \dots, A_N). For each k = 0, \dots, K-1, answer the following question:

• Define a length-N symbol string A' = (A'_1, \dots, A'_N) by A'_i := (A_i + k) \bmod K. What is the number of syllables of A'?

Input Format

The input for this problem is given in a special format.

Instead of A_1, \dots, A_N, the integers \mathrm{seed}, M, b_1, \dots, b_M are given from Standard Input. Restore A_1, \dots, A_N using the computation represented by the following pseudocode.

Here, all variables in the pseudocode are unsigned 64-bit integers. s \oplus t denotes the bitwise XOR of s and t, s \gg t denotes \lfloor s / 2^t \rfloor (the right shift operation), and s \ll t denotes s \times 2^t (the left shift operation).

\mathrm{state} \leftarrow \mathrm{seed}

for i = 1, \dots, N:
    if i \leq M:
        A_i \leftarrow b_i
    else:
        x \leftarrow \left( ((\mathrm{state} \gg 18) \oplus \mathrm{state}) \gg 27 \right) \bmod 2^{32}
        r \leftarrow \mathrm{state} \gg 59
        y \leftarrow \left( (x \gg r) + (x \ll (32-r)) \right) \bmod 2^{32}
        A_i \leftarrow y \bmod K
        \mathrm{state} \leftarrow (\mathrm{state} \times 6364136223846793005 + 2026081520260815) \bmod 2^{64}

Constraints

• 1 \leq N \leq 7 \times 10^6
• 1 \leq K \leq 2300
• 0 \leq A_i \leq K-1 (1 \leq i \leq N)
• V_j \in \{0,1\} (0 \leq j \leq K-1)
• 0 \leq \mathrm{seed} \leq 2^{60} - 1
• 1 \leq M \leq \min(N, 10^5)
• 0 \leq b_i \leq K-1 (1 \leq i \leq M)
• All input values are integers.

Sample Input 1

4 6 12233445577788999 4
4 2 4 1
1 1 0 0 1 0

Sample Output 1

2
0
1
2
1
2

In this input, A = (4,2,4,1).

• For k = 0, A' = (4,2,4,1), and the number of syllables is 2.
• For k = 1, A' = (5,3,5,2), and the number of syllables is 0.
• For k = 2, A' = (0,4,0,3), and the number of syllables is 1.
• For k = 3, A' = (1,5,1,4), and the number of syllables is 2.
• For k = 4, A' = (2,0,2,5), and the number of syllables is 1.
• For k = 5, A' = (3,1,3,0), and the number of syllables is 2.

Sample Input 2

15 12 998154573227378904 2
5 6
0 0 1 1 0 1 0 0 1 1 0 1

Sample Output 2

4
4
3
3
3
4
4
4
3
3
3
4

In this input, A = (5, 6, 0, 6, 8, 8, 8, 3, 0, 2, 3, 7, 3, 2, 5).

Sample Input 3

7000000 15 409873722375451899 3
7 0 4
1 0 1 1 1 0 1 1 1 0 1 0 1 0 0

Sample Output 3

1680078
1681239
1679837
1680730
1680470
1679454
1679615
1679371
1681263
1679670
1680218
1680010
1680211
1680521
1681744