Problem Statement

You are given integers L and R.

Find how many integers are between L and R, inclusive.

Constraints

• 1\le L\le R\le 100
• All input values are integers.

Sample Input 1

3 5

Sample Output 1

3

The integers between 3 and 5, inclusive, are 3,4,5, which is three integers. Thus, output 3.

Sample Input 2

1 7

Sample Output 2

7

Sample Input 3

14 79

Sample Output 3

66

Problem Statement

There are N people numbered 1 through N.
There are M types of clothes numbered 1 through M. Person i is wearing clothes F_i.
Answer the following two questions with Yes or No.

• Question 1: Are all N people wearing different types of clothes?
• Question 2: For every one of the M types of clothes, is there at least one person wearing that type?

Constraints

• 1 \leq N \leq 100
• 1 \leq M \leq 100
• 1 \leq F_i \leq M
• All input values are integers.

Sample Input 1

3 4
1 2 4

Sample Output 1

Yes
No

Everyone is wearing a different type of clothes, so the answer to question 1 is Yes.
There is no person wearing clothes 3, so the answer to question 2 is No.

Sample Input 2

4 2
1 2 1 2

Sample Output 2

No
Yes

Sample Input 3

4 4
1 3 2 1

Sample Output 3

No
No

Sample Input 4

5 5
1 3 4 2 5

Sample Output 4

Yes
Yes

Problem Statement

There are N types of items item 1 through item N. Initially, Takahashi has only item 1.

He has M friends. If he gives item A_i to the i-th friend (1\le i\le M), he will receive item B_i.

Find how many types of items he can obtain, including item 1.

Constraints

• 2\le N\le 3\times 10^5
• 1\le M\le 3\times 10^5
• 1\le A_i,B_i\le N
• A_i \neq B_i
• All input values are integers.

Sample Input 1

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

Sample Output 1

4

For example, Takahashi can obtain item 4 by acting as follows:

• Give item 1 to the first friend. Receive item 2.
• Give item 2 to the fourth friend. Receive item 4.

He can obtain four types of items: items 1,2,3,4. Thus, output 4.

Sample Input 2

3 2
2 1
3 2

Sample Output 2

1

He can obtain one type of item: item 1.

Sample Input 3

7 8
2 6
2 5
3 6
1 6
1 2
5 6
2 3
3 7

Sample Output 3

6

Problem Statement

You are given a string A consisting of (, x, ).
You can perform the following two types of operations on A any number of times in any order.

• Choose one occurrence of the substring (xx) in A and replace it with xx.
• Choose one occurrence of the substring xx in A and replace it with (xx).

You are given a string B consisting of (, x, ). Determine whether you can make A equal to B.

You are given T test cases; solve each of them.

Constraints

• 1 \leq T \leq 3 \times 10^5
• A and B are strings of length between 1 and 2\times 10^6, inclusive, consisting of (, x, ).
• The sum of |A| + |B| over all test cases is at most 2 \times 10^6 (where |A| denotes the length of A).

Sample Input 1

6
(xx)x
x(xx)
(x)x
(xx)
)x()x(
)x()x(
x
(x)
(((((xx)))))x
x((((((((((xx))))))))))
((xx)xx)xx
(x((xx))x)(xx)

Sample Output 1

Yes
No
Yes
No
Yes
Yes

For example, in the first test case, you can make A equal to B by the following procedure:

• Replace the (xx) from the 1st through 4th characters of A with xx. After this operation, A is xxx.
• Replace the xx from the 2nd through 3rd characters of A with (xx). After this operation, A is x(xx).

Problem Statement

You are given positive integers N,A,B. It is guaranteed that both A and B are between 1 and N, inclusive.

There is an N\times N grid. The cell at the i-th row from the top and j-th column from the left is denoted as cell (i,j). Initially, a piece is placed at cell (1,1).

By repeating N^2-2 moves, each of which moves the piece to an adjacent cell (up, down, left, or right), you want to move the piece to cell (N,N) while visiting every cell except cell (A,B). You must not visit the same cell more than once (you must not visit cells (1,1) and (N,N) in the middle, either).

Determine whether such a sequence of moves is possible, and if so, output one such sequence.

You are given T test cases; solve each of them.

Constraints

• 1\le T \le 5000
• 2\le N\le 10^3
• 1\le A,B\le N
• (A,B)\neq (1,1),(N,N)
• The sum of N^2 over all test cases is at most 10^6.
• All input values are integers.

Sample Input 1

3
2 1 2
3 2 2
4 3 2

Sample Output 1

Yes
DR
No
Yes
RRRDLLLDDRRURD

Consider the first test case.

Starting with the piece at cell (1,1), move it twice as follows:

• Move the piece downward. The piece moves to cell (2,1).
• Move the piece rightward. The piece moves to cell (2,2).

This sequence of moves satisfies the conditions.

Problem Statement

You are given a positive integer N, a positive integer M, and an integer sequence A=(A_1,A_2,\ldots,A_N) of length N. It is guaranteed that each element of A is between 0 and M-1, inclusive.

You can perform the following operation on the integer sequence A any number of times, possibly zero:

• Choose a pair of integers (l,r) satisfying 1\le l\le r\le N, and replace A_i with (A_i+1) \bmod M for each i=l,l+1,\ldots,r.

Find the minimum number of operations required to make A a palindrome.

Here, A is a palindrome if A_i=A_{N+1-i} holds for i=1,2,\ldots,N.

You are given T test cases; solve each of them.

Constraints

• 1\le T
• 1\le N\le 2\times 10^5
• 1\le M\le 10^9
• 0\le A_i < M
• The sum of N over all test cases is at most 2\times 10^5.
• All input values are integers.

Sample Input 1

3
4 5
0 3 1 2
1 20260418
454
7 12
3 1 4 1 5 9 2

Sample Output 1

3
0
5

Consider the first test case.

You can make A a palindrome in three operations as follows:

• Choose (l,r)=(2,4). A becomes (0,4,2,3).
• Choose (l,r)=(3,4). A becomes (0,4,3,4).
• Choose (l,r)=(3,4). A becomes (0,4,4,0).

It is impossible to make A a palindrome in fewer than three operations, so output 3.

Problem Statement

You are given a rooted tree with N vertices numbered 1 through N. Vertex 1 is the root, and the parent of vertex i is vertex p_i (p_i \lt i).
Each vertex is colored: vertex i is colored with color c_i (1 \leq c_i \leq N).
For each v = 1, 2, \dots, N, solve the following problem:

Let f_i be the number of vertices colored with color i among the vertices in the subtree rooted at vertex v.

Find:

• the maximum value m among the values in the sequence (f_1, f_2, \dots, f_N), and
• the number k of positive integers i not greater than N such that f_i = m.

Input/Output Format

The input and output for this problem follow a special format.

Input Format

From Standard Input, you are given the integer N along with integers \mathrm{seed}, M, F and q_2, q_3, \dots, q_M, d_1, d_2, \dots, d_M. Reconstruct p_2, p_3, \dots, p_N and c_1, c_2, \dots, c_N using the computation described by the following pseudocode. (Here, 2^31 means 2^{31}=2147483648. Note that \mathrm{state} is a variable, and that a 64-bit integer type is required for computing \mathrm{state}.)

state = seed

for i=2 to N:
  if i <= M:
    p[i] = q[i]
  else:
    p[i] = (state mod (i-1)) + 1
    state = (state * 1103515245 + 12345) mod 2^31

for i=1 to N:
  if i <= M:
    c[i] = d[i]
  else:
    c[i] = (state mod F) + 1
    state = (state * 1103515245 + 12345) mod 2^31

Output Format

Let m_i and k_i denote m and k when v=i, respectively. Output this value:

Here, \oplus denotes bitwise XOR. Beware of overflow during computation.

Constraints

• 2 \leq N \leq 2.5 \times 10^6
• 1 \leq p_i \lt i
• 1 \leq c_i \leq N
• 1 \leq \mathrm{seed} \lt 2^{31}
• 2 \leq M \leq \min(N, 10^5)
• 1 \leq F \leq N
• 1 \leq q_i \lt i
• 1 \leq d_i \leq N
• All input values are integers.

Sample Input 1

4 454 4 2
1 2 2
1 2 2 3

Sample Output 1

29

• i=1 : m_1=2,k_1=1, (m_1 \oplus 1) \times (k_1 \oplus 1) = 0
• i=2 : m_2=2,k_2=1, (m_2 \oplus 2) \times (k_2 \oplus 2) = 0
• i=3 : m_3=1,k_3=1, (m_3 \oplus 3) \times (k_3 \oplus 3) = 4
• i=4 : m_4=1,k_4=1, (m_4 \oplus 4) \times (k_4 \oplus 4) = 25

Thus, output 0+0+4+25=29.

Sample Input 2

6 123 2 2
1
1 2

Sample Output 2

101

The values of p_i, c_i in this test case are as follows:

• p = (1, 2, 1, 2, 3)
• c = (1, 2, 2, 1, 2, 1)

Sample Input 3

15 1 4 5
1 2 3
5 3 1 3

Sample Output 3

1199

The values of p_i, c_i in this test case are as follows:

• p = (1, 2, 3, 2, 1, 4, 7, 6, 5, 10, 1, 10, 2, 8)
• c = (5, 3, 1, 3, 4, 2, 2, 2, 4, 2, 2, 5, 3, 5, 3)