Problem Statement

A function f(x) defined for non-negative integer x satisfies the following conditions:

• f(0) = 1;
• f(k) = k \times f(k-1) for all positive integers k.

Find f(N).

Constraints

• N is an integer such that 0 \le N \le 10.

Sample Input 1

2

Sample Output 1

2

We have f(2) = 2 \times f(1) = 2 \times 1 \times f(0) = 2 \times 1 \times 1 = 2.

Sample Input 2

3

Sample Output 2

6

We have f(3) = 3 \times f(2) = 3 \times 2 = 6.

Sample Input 3

0

Sample Output 3

1

Sample Input 4

10

Sample Output 4

3628800

Problem Statement

AtCoder Inc. sells merchandise through its online shop.

Takahashi has decided to purchase N types of products from there.
For each integer i from 1 to N, the i-th type of product has a price of P_i yen each, and he will buy Q_i of this.

Additionally, he must pay a shipping fee.
The shipping fee is 0 yen if the total price of the products purchased is S yen or above, and K yen otherwise.

He will pay the total price of the products purchased plus the shipping fee.
Calculate the amount he will pay.

Constraints

• 1\leq N\leq 100
• 1\leq S\leq 10000
• 1\leq K\leq 10000
• 1\leq P_i\leq 10000
• 1\leq Q_i\leq 100
• All input values are integers.

Sample Input 1

2 2000 500
1000 1
100 6

Sample Output 1

2100

Takahashi buys one product for 1000 yen and six products for 100 yen each.
Thus, the total price of the products is 1000\times 1+100\times 6=1600 yen.
Since the total amount for the products is less than 2000 yen, the shipping fee will be 500 yen.
Therefore, the amount Takahashi will pay is 1600+500=2100 yen.

Sample Input 2

3 2000 500
1000 1
100 6
5000 1

Sample Output 2

6600

The total price of the products is 1000\times 1+100\times 6+5000\times 1=6600 yen.
Since the total amount for the products is not less than 2000 yen, the shipping fee will be 0 yen.
Therefore, the amount Takahashi will pay is 6600+0=6600 yen.

Sample Input 3

2 2000 500
1000 1
1000 1

Sample Output 3

2000

There may be multiple products with the same price per item.

Problem Statement

An integer sequence A=(A_1,A_2,\ldots,A_N) of length N is given.

Output the numbers contained in A in ascending order, removing duplicates.

Constraints

• 1\le N\le 100
• 1\le A_i\le 100
• All input values are integers.

Sample Input 1

4
3 1 4 1

Sample Output 1

3
1 3 4

The numbers contained in A=(3,1,4,1) are 1,3,4 in ascending order, totalling 3 distinct numbers. Therefore, output as shown above.

Sample Input 2

3
7 7 7

Sample Output 2

1
7

Sample Input 3

8
19 5 5 19 5 19 4 19

Sample Output 3

3
4 5 19

Problem Statement

There is a grid with H horizontal rows and W vertical columns. Each cell has a lowercase English letter written on it. We denote by (i, j) the cell at the i-th row from the top and j-th column from the left.

The letters written on the grid are represented by H strings S_1,S_2,\ldots, S_H, each of length W. The j-th letter of S_i represents the letter written on (i, j).

There is a unique set of contiguous cells (going vertically, horizontally, or diagonally) in the grid with s, n, u, k, and e written on them in this order.
Find the positions of such cells and print them in the format specified in the Output section.

A tuple of five cells (A_1,A_2,A_3,A_4,A_5) is said to form a set of contiguous cells (going vertically, horizontally, or diagonally) with s, n, u, k, and e written on them in this order if and only if all of the following conditions are satisfied.

• A_1,A_2,A_3,A_4 and A_5 have letters s, n, u, k, and e written on them, respectively.
• For all 1\leq i\leq 4, cells A_i and A_{i+1} share a corner or a side.
• The centers of A_1,A_2,A_3,A_4, and A_5 are on a common line at regular intervals.

Constraints

• 5\leq H\leq 100
• 5\leq W\leq 100
• H and W are integers.
• S_i is a string of length W consisting of lowercase English letters.
• The given grid has a unique conforming set of cells.

Sample Input 1

6 6
vgxgpu
amkxks
zhkbpp
hykink
esnuke
zplvfj

Sample Output 1

5 2
5 3
5 4
5 5
5 6

Tuple (A_1,A_2,A_3,A_4,A_5)=((5,2),(5,3),(5,4),(5,5),(5,6)) satisfies the conditions.
Indeed, the letters written on them are s, n, u, k, and e;
for all 1\leq i\leq 4, cells A_i and A_{i+1} share a side;
and the centers of the cells are on a common line.

Sample Input 2

5 5
ezzzz
zkzzz
ezuzs
zzznz
zzzzs

Sample Output 2

5 5
4 4
3 3
2 2
1 1

Tuple (A_1,A_2,A_3,A_4,A_5)=((5,5),(4,4),(3,3),(2,2),(1,1)) satisfies the conditions.
However, for example, (A_1,A_2,A_3,A_4,A_5)=((3,5),(4,4),(3,3),(2,2),(3,1)) violates the third condition because the centers of the cells are not on a common line, although it satisfies the first and second conditions.

Sample Input 3

10 10
kseeusenuk
usesenesnn
kskekeeses
nesnusnkkn
snenuuenke
kukknkeuss
neunnennue
sknuessuku
nksneekknk
neeeuknenk

Sample Output 3

9 3
8 3
7 3
6 3
5 3

Problem Statement

There is a length-N integer sequence A=(A_1,A_2,\ldots,A_N). Initially, all elements of A are 0.

You will be given Q queries, which should be processed in order. There are two types of queries, each given in one of the following formats:

• 1 x: Increase the value of A_x by 1.
• 2: For each i=1,2,\ldots,N, if A_i \geq 1, decrease the value of A_i by 1.

Find the bitwise \mathrm{XOR} of A_1,A_2,\ldots,A_N immediately after processing each query.

Constraints

• 1\le N\le 5\times 10^5
• 1\le Q\le 5\times 10^5
• 1\le x\le N
• All input values are integers.

Sample Input 1

2 5
1 2
1 2
1 1
2
2

Sample Output 1

1
2
3
1
0

After processing the first query, A=(0,1). The bitwise \mathrm{XOR} of 0,1 is 1, so output 1 on the first line.

After processing the second query, A=(0,2). The bitwise \mathrm{XOR} of 0,2 is 2, so output 2 on the second line.

After processing the third query, A=(1,2). The bitwise \mathrm{XOR} of 1,2 is 3, so output 3 on the third line.

After processing the fourth query, A=(0,1). The bitwise \mathrm{XOR} of 0,1 is 1, so output 1 on the fourth line.

After processing the fifth query, A=(0,0). The bitwise \mathrm{XOR} of 0,0 is 0, so output 0 on the fifth line.

Sample Input 2

3 8
1 2
1 3
1 1
1 2
1 1
2
1 3
1 1

Sample Output 2

1
0
1
2
1
0
1
2

Problem Statement

We have an empty box.
Takahashi can cast the following two spells any number of times in any order.

• Spell A: puts one new ball into the box.
• Spell B: doubles the number of balls in the box.

Tell us a way to have exactly N balls in the box with at most \mathbf{120} casts of spells.
It can be proved that there always exists such a way under the Constraints given.

There is no way other than spells to alter the number of balls in the box.

Constraints

• 1 \leq N \leq 10^{18}
• All values in input are integers.

Sample Input 1

5

Sample Output 1

AABA

This changes the number of balls as follows: 0 \xrightarrow{A} 1\xrightarrow{A} 2 \xrightarrow{B}4\xrightarrow{A} 5.
There are also other acceptable outputs, such as AAAAA.

Sample Input 2

14

Sample Output 2

BBABBAAAB

This changes the number of balls as follows: 0 \xrightarrow{B} 0 \xrightarrow{B} 0 \xrightarrow{A}1 \xrightarrow{B} 2 \xrightarrow{B} 4 \xrightarrow{A}5 \xrightarrow{A}6 \xrightarrow{A} 7 \xrightarrow{B}14.
It is not required to minimize the length of S.

Problem Statement

Snuke is observing a snake and is curious about which parts are the head, body, and tail. He divided the snake into N blocks and evaluated the head-likeness, body-likeness, and tail-likeness of each block. Then, he decided to find the division that maximizes the sum of the likeness values.

You are given length-N integer sequences A = (A_1, A_2, \ldots, A_N), B = (B_1, B_2, \ldots, B_N), and C = (C_1, C_2, \ldots, C_N).

Find the maximum possible value of \displaystyle\sum_{i = 1}^{x} A_i + \sum_{i = x + 1}^{y} B_i + \sum_{i = y + 1}^{N} C_i for a pair of integers (x, y) satisfying 1 \leq x < y < N.

Constraints

• 3 \leq N \leq 3 \times 10^5
• 1 \leq A_i, B_i, C_i \leq 10^6
• All input values are integers.

Sample Input 1

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

Sample Output 1

16

With (x, y) = (2, 3), we have \displaystyle\sum_{i = 1}^{x} A_i + \sum_{i = x + 1}^{y} B_i + \sum_{i = y + 1}^{N} C_i = 1 + 4 + 4 + 4 + 3 = 16.

Sample Input 2

3
1 1 1
1 1 1
1 1 1

Sample Output 2

3

Sample Input 3

6
2 10 7 7 7 11
5 7 9 10 9 12
6 6 7 10 12 7

Sample Output 3

50

Problem Statement

Let us call a positive integer n that satisfies the following condition an arithmetic number.

• Let d_i be the i-th digit of n from the top (when n is written in base 10 without unnecessary leading zeros.) Then, (d_2-d_1)=(d_3-d_2)=\dots=(d_k-d_{k-1}) holds, where k is the number of digits in n.
  • This condition can be rephrased into the sequence (d_1,d_2,\dots,d_k) being arithmetic.
  • If n is a 1-digit integer, it is assumed to be an arithmetic number.

For example, 234,369,86420,17,95,8,11,777 are arithmetic numbers, while 751,919,2022,246810,2356 are not.

Find the smallest arithmetic number not less than X.

Constraints

• X is an integer between 1 and 10^{17} (inclusive).

Sample Input 1

152

Sample Output 1

159

The smallest arithmetic number not less than 152 is 159.

Sample Input 2

88

Sample Output 2

88

X itself may be an arithmetic number.

Sample Input 3

8989898989

Sample Output 3

9876543210

Problem Statement

Takahashi is participating in a lottery.

Each time he takes a draw, he gets one of the N prizes available. Prize i is awarded with probability \frac{W_i}{\sum_{j=1}^{N}W_j}. The results of the draws are independent of each other.

What is the probability that he gets exactly M different prizes from K draws? Find it modulo 998244353.

Note

To print a rational number, start by representing it as a fraction \frac{y}{x}. Here, x and y should be integers, and x should not be divisible by 998244353 (under the Constraints of this problem, such a representation is always possible). Then, print the only integer z between 0 and 998244352 (inclusive) such that xz\equiv y \pmod{998244353}.

Constraints

• 1 \leq K \leq 50
• 1 \leq M \leq N \leq 50
• 0 < W_i
• 0 < W_1 + \ldots + W_N < 998244353
• All values in input are integers.

Sample Input 1

2 1 2
2
1

Sample Output 1

221832079

Each draw awards Prize 1 with probability \frac{2}{3} and Prize 2 with probability \frac{1}{3}.

He gets Prize 1 at both of the two draws with probability \frac{4}{9}, and Prize 2 at both draws with probability \frac{1}{9}, so the sought probability is \frac{5}{9}.

The modulo 998244353 representation of this value, according to Note, is 221832079.

Sample Input 2

3 3 2
1
1
1

Sample Output 2

0

It is impossible to get three different prizes from two draws, so the sought probability is 0.

Sample Input 3

3 3 10
499122176
499122175
1

Sample Output 3

335346748

Sample Input 4

10 8 15
1
1
1
1
1
1
1
1
1
1

Sample Output 4

755239064