Problem Statement

You are given a sequence A = (A_1, A_2, ..., A_N).
You may perform the following operation exactly once.

• Choose an integer M at least 2. Then, for every integer i (1 \leq i \leq N), replace A_i with the remainder when A_i is divided by M.

For instance, if M = 4 is chosen when A = (2, 7, 4), A becomes (2 \bmod 4, 7 \bmod 4, 4 \bmod 4) = (2, 3, 0).

Find the minimum possible number of different elements in A after the operation.

Constraints

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

Sample Input 1

3
1 4 8

Sample Output 1

2

If you choose M = 3, you will have A = (1 \bmod 3, 4 \bmod 3, 8 \bmod 3) = (1, 1, 2), where A contains two different elements.
The number of different elements in A cannot become 1, so the answer is 2.

Sample Input 2

4
5 10 15 20

Sample Output 2

1

If you choose M = 5, you will have A = (0, 0, 0, 0), which is optimal.

Sample Input 3

10
3785 5176 10740 7744 3999 3143 9028 2822 4748 6888

Sample Output 3

1

Problem Statement

For a string T of length L consisting of d and p, let f(T) be T rotated 180 degrees. More formally, let f(T) be the string that satisfies the following conditions.

• f(T) is a string of length L consisting of d and p.
• For every integer i such that 1 \leq i \leq L, the i-th character of f(T) differs from the (L + 1 - i)-th character of T.

For instance, if T = ddddd, f(T) = ppppp; if T = dpdppp, f(T)= dddpdp.

You are given a string S of length N consisting of d and p.
You may perform the following operation zero or one time.

• Choose a pair of integers (L, R) such that 1 \leq L \leq R \leq N, and let T be the substring formed by the L-th through R-th characters of S. Then, replace the L-th through R-th characters of S with f(T).

For instance, if S= dpdpp and (L,R)=(2,4), we have T= pdp and f(T)= dpd, so S becomes ddpdp.

Print the lexicographically smallest string that S can become.

Constraints

• 1 \leq N \leq 5000
• S is a string of length N consisting of d and p.
• N is an integer.

Sample Input 1

6
dpdppd

Sample Output 1

dddpdd

Let (L, R) = (2, 5). Then, we have T = pdpp and f(T) = ddpd, so S becomes dddpdd.
This is the lexicographically smallest string that can be obtained, so print it.

Sample Input 2

3
ddd

Sample Output 2

ddd

It may be optimal to skip the operation.

Sample Input 3

11
ddpdpdppddp

Sample Output 3

ddddpdpdddp

Problem Statement

We have a rooted tree with N vertices numbered 1 to N. Vertex 1 is the root, and the parent of vertex i is vertex P_i.
There are N coins with heads and tails, one on each vertex.
Additionally, there are N buttons numbered 1 to N. Pressing button n flips all coins on the vertices in the subtree rooted at vertex n.

Process Q queries described below.

In the i-th query, you are given a vertex set of size M_i: S_i = \lbrace v_{i,1}, v_{i,2},\dots, v_{i,M_i} \rbrace.
Now, the coins on the vertices in S_i are facing heads-up, and the others are facing tails-up. In order to make all N coins face tails-up by repeatedly choosing a button and pressing it, at least how many button presses are needed? Print the answer, or -1 if there is no way to make all the coins face tails-up.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq P_i \lt i
• 1 \leq Q \leq 2 \times 10^5
• 1 \leq M_i
• \displaystyle \sum_{i=1}^Q M_i \leq 2 \times 10^5
• 1 \leq v_{i,j} \leq N
• v_{i,1}, v_{i,2},\dots,v_{i,M_i} are pairwise different.
• All values in the input are integers.

Sample Input 1

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

Sample Output 1

1
2
1
3
2
3

For the first query, you can satisfy the requirement in one button press, which is the minimum needed, as follows.

• Press button 1, flipping the coins on vertices 1,2,3,4,5,6.

For the second query, you can satisfy the requirement in two button presses, which is the minimum needed, as follows.

• Press button 4, flipping the coin on vertex 4.
• Press button 2, flipping the coins on vertex 2,4,5,6.

Problem Statement

There are 2N integers A_1, A_2, ..., A_{2N} written on a blackboard, and an integer M at least 2.
Alice and Bob will play a game. They will alternately perform the following operation, with Alice going first, until there is no number on the blackboard.

• Choose a number and delete it from the blackboard.

At the end of the game, if the sum of numbers deleted by Alice modulo M equals the sum of numbers deleted by Bob modulo M, Bob wins; otherwise, Alice wins.
Which player will win if both plays optimally?

Constraints

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

Sample Input 1

2 9
1 4 8 5

Sample Output 1

Alice

The game may proceed as follows.

• Alice deletes 1.
• Bob deletes 4.
• Alice deletes 5.
• Bob deletes 8.

In this case, the sum of numbers deleted by Alice modulo M is (1 + 5) \bmod 9 = 6, and the sum of numbers deleted by Bob modulo M is (4 + 8) \bmod 9 = 3. Since 6 \neq 3, Alice wins.

Sample Input 2

3 998244353
1 2 3 1 2 3

Sample Output 2

Bob

Problem Statement

You are given a sequence of length N, A = (A_1, ..., A_N), and an integer K.
How many permutations of A are there such that no two adjacent elements sum to less than K? Find the count modulo 998244353.

Constraints

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

Sample Input 1

4 5
1 2 3 4

Sample Output 1

4

The following four permutations satisfy the condition:

• (1, 4, 2, 3)
• (1, 4, 3, 2)
• (2, 3, 4, 1)
• (3, 2, 4, 1)

Sample Input 2

4 3
1 2 3 3

Sample Output 2

12

There are 12 permutations of A, all of which satisfy the condition.

Sample Input 3

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

Sample Output 3

108

Problem Statement

This problem is output-only.

We have a programming language equipped with the following operations of unsigned 64-bit integers: addition, multiplication, and a modulo operation where the divisor is 998244353.
Write a program that performs multiplication modulo 1000000007 in this language.

More formally, write a program that receives integers a and b between 0 and 1000000006 and computes a \times b \bmod{1000000007} under the following Specification and Format.

Specification

The program can handle 26 variables represented by uppercase English letters: A, B, \dots, Z.
Each variable can hold an integer value between 0 and 2^{64}-1 (inclusive). Below, such a value is called unsigned 64-bit integer.
At the start of the execution of the program, A is assigned an integer a, B is assigned an integer b, and the other variables are assigned 0.
At the end of the execution, C must hold a \times b \bmod{1000000007}.

Format

The 1-st line of the program contains an integer N (1 \leq N \leq 100) representing the number of instructions in the program.
The 2-nd through (N + 1)-th lines contain N instructions. The instructions are executed one by one from top to bottom.
Each instruction is in one of the following three forms.

• add x y z
  • Assign (y + z) \bmod{2^{64}} to x, where x is a variable, and each of y and z is a variable or an unsigned 64-bit integer.
• mul x y z
  • Assign (y \times z) \bmod{2^{64}} to x, where x is a variable, and each of y and z is a variable or an unsigned 64-bit integer.
• rem x y
  • Assign y \bmod{998244353} to x, where x is a variable, and y is a variable or an unsigned 64-bit integer.