Problem Statement

You are given N integers A_1,A_2,\dots, and A_N.

Find the sum of the N integers.

Constraints

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

Sample Input 1

3
2 7 2

Sample Output 1

11

You are given three integers: 2, 7, and 2.

The answer is 2 + 7 + 2 = 11.

Sample Input 2

1
3

Sample Output 2

3

Problem Statement

There are N people numbered 1,2,\ldots,N.

M parties were held. k_i people attended the i-th (1\leq i \leq M) party, and they were People x_{i,1},x_{i,2},\ldots,x_{i,k_i}.

Determine if every two people attended the same party at least once.

Constraints

• 2\leq N \leq 100
• 1\leq M \leq 100
• 2\leq k_i \leq N
• 1\leq x_{i,1}<x_{i,2}<\ldots < x_{i,k_i}\leq N
• All values in the input are integers.

Sample Input 1

3 3
2 1 2
2 2 3
2 1 3

Sample Output 1

Yes

Both Person 1 and Person 2 attended the 1-st party.

Both Person 2 and Person 3 attended the 2-nd party.

Both Person 1 and Person 3 attended the 3-rd party.

Therefore, every two people attended the same party at least once, so the answer is Yes.

Sample Input 2

4 2
3 1 2 4
3 2 3 4

Sample Output 2

No

Person 1 and Person 3 did not attend the same party, so the answer is 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

There is a grid with N \times N squares. We denote by (i, j) the square at the i-th row from the top and j-th column from the left.

Initially, a piece is placed on (1, 1). You may repeat the following operation any number of times:

• Let (i, j) be the square the piece is currently on. Move the piece to the square whose distance from (i, j) is exactly \sqrt{M}.

Here, we define the distance between square (i, j) and square (k, l) as \sqrt{(i-k)^2+(j-l)^2}.

For all squares (i, j), determine if the piece can reach (i, j). If it can, find the minimum number of operations required to do so.

Constraints

• 1 \le N \le 400
• 1 \le M \le 10^6
• All values in the input are integers.

Sample Input 1

3 1

Sample Output 1

0 1 2
1 2 3
2 3 4

You can move the piece to four adjacent squares.

For example, we can move the piece to (2,2) with two operations as follows.

• The piece is now on (1,1). The distance between (1,1) and (1,2) is exactly \sqrt{1}, so move the piece to (1,2).
• The piece is now on (1,2). The distance between (1,2) and (2,2) is exactly \sqrt{1}, so move the piece to (2,2).

Sample Input 2

10 5

Sample Output 2

0 3 2 3 2 3 4 5 4 5
3 4 1 2 3 4 3 4 5 6
2 1 4 3 2 3 4 5 4 5
3 2 3 2 3 4 3 4 5 6
2 3 2 3 4 3 4 5 4 5
3 4 3 4 3 4 5 4 5 6
4 3 4 3 4 5 4 5 6 5
5 4 5 4 5 4 5 6 5 6
4 5 4 5 4 5 6 5 6 7
5 6 5 6 5 6 5 6 7 6

Problem Statement

You are given an integer sequence A=(A_1,A_2,\ldots,A_N) of length N.

Perform the following operation M times:

• For each i\ (1\leq i \leq N), add i to A_i. Then, find the minimum non-negative integer not contained in A.

Constraints

• 1\leq N,M \leq 2\times 10^5
• -10^9\leq A_i\leq 10^9
• All values in the input are integers.

Sample Input 1

3 3
-1 -1 -6

Sample Output 1

2
2
0

The 1-st operation makes the sequence A

(-1 + 1, -1 +2 ,-6+3) = (0,1,-3).

The minimum non-negative integer not contained in A is 2.

The 2-nd operation makes the sequence A

(0 + 1, 1 +2 ,-3+3) = (1,3,0).

The minimum non-negative integer not contained in A is 2.

The 3-rd operation makes the sequence A

(1 + 1, 3 +2 ,0+3) = (2,5,3).

The minimum non-negative integer not contained in A is 0.

Sample Input 2

5 6
-2 -2 -5 -7 -15

Sample Output 2

1
3
2
0
0
0

Problem Statement

You are given strings S and T of length N each, consisting of lowercase English letters.

For a string X and an integer i, let f(X,i) be the string obtained by performing on X the following operation i times:

• Remove the first character of X and append the same character to the end of X.

Find the number of integer pairs (i,j) satisfying 0 \le i,j \le N-1 such that f(S,i) is lexicographically smaller than or equal to f(T,j).

Constraints

• 1 \le N \le 2 \times 10^5
• S and T are strings of length N each, consisting of lowercase English letters.
• N is an integer.

Sample Input 1

3
adb
cab

Sample Output 1

4

There are 4 pairs of (i, j) satisfying the conditions: (0,0),(0,2),(2,0), and (2,2).

(i,j)=(1,2) does not satisfy the conditions because f(S,i)=dba and f(T,j)=bca.

Sample Input 2

10
wsiuhwijsl
pwqoketvun

Sample Output 2

56

Problem Statement

You are given a sequence A=(A_1,A_2,\dots,A_N) of length N consisting of positive integers, where the elements of A are distinct.

You will choose a positive integer M between 3 and 10^9 (inclusive) to perform the following operation once:

• For each integer i such that 1 \le i \le N, replace A_i with A_i \bmod M.

Can you choose an M so that A satisfies the following condition after the operation? If you can, find such an M.

• There exists an integer x such that x is the majority in A.

Here, an integer x is said to be the majority in A if the number of integers i such that A_i = x is greater than the number of integers i such that A_i \neq x.

Constraints

• 3 \le N \le 5000
• 1 \le A_i \le 10^9
• The elements of A are distinct.
• All values in the input are integers.

Sample Input 1

5
3 17 8 14 10

Sample Output 1

7

If you let M=7 to perform the operation, you will have A=(3,3,1,0,3), where 3 is the majority in A, so M=7 satisfies the condition.

Sample Input 2

10
822848257 553915718 220834133 692082894 567771297 176423255 25919724 849988238 85134228 235637759

Sample Output 2

37

Sample Input 3

10
1 2 3 4 5 6 7 8 9 10

Sample Output 3

-1

Problem Statement

N coins numbered 0,1,\ldots,N-1 are arranged in a row. Initially, all coins are face up. Also, you are given a sequence A of length N consisting of integers between 0 and N-1.

Snuke will choose a permutation p=(p_1,p_2,\ldots,p_N) of (1,\ldots,N) at equal probability and perform N operations. In the i-th (1\leq i \leq N) operation,

• he flips (A_{p_i}+1) coins: coin (i-1) \bmod N, coin (i-1+1 ) \bmod N, \ldots, and coin (i -1+ A_{p_i}) \bmod N.

After the N operations, Snuke receives k yen (the currency in Japan) from his mother, where k is the number of face-up coins.

Find the expected value, modulo 998244353, of the money Snuke will receive.

Constraints

• 1 \leq N\leq 2\times 10^5
• 0\leq A_i \leq N-1
• All values in the input are integers.

Sample Input 1

2
0 1

Sample Output 1

1

p can be either (1,2) or (2,1).

• If (1,2) is chosen as p:

In the first operation, coin 0 is flipped, and in the second operation, coin 1 and coin 0 are flipped. One coin, coin 0, results in being face up, so he receives 1 yen.

• If (2,1) is chosen as p:

In the first operation, coin 0 and coin 1 are flipped, and in the second operation, coin 1 is flipped. One coin, coin 1, results in being face up, so he receives 1 yen.

Therefore, the expected value of the money he receives is 1 yen.

Sample Input 2

4
3 1 1 2

Sample Output 2

665496237

Print the expected value modulo 998244353.