Problem Statement

There are four balls, and the color of the i-th ball is A_i.

Find the maximum number of times you can perform this operation: choose two balls of the same color and discard both.

Constraints

• Each of A_1, A_2, A_3, A_4 is an integer between 1 and 4, inclusive.

Sample Input 1

2 1 2 1

Sample Output 1

2

The first and third balls both have color 2, so you can perform the operation to discard the first and third balls together.

Next, the second and fourth balls both have color 1, so you can perform the operation to discard the second and fourth balls together.

Hence, you can perform a total of two operations.

Sample Input 2

4 4 4 1

Sample Output 2

1

Sample Input 3

1 2 3 4

Sample Output 3

0

There are cases where you cannot perform the operation even once.

Problem Statement

In AtCoder City, N types of garbage are collected regularly. The i-th type of garbage (i=1,2,\dots,N) is collected on days when the date modulo q_i equals r_i.

Answer Q queries. In the j-th query (j=1,2,\dots,Q), given that the t_j-th type of garbage is put out on day d_j, answer the next day on which it will be collected.

Here, if the i-th type of garbage is put out on a day when that type of garbage is collected, then the garbage will be collected on the same day.

Constraints

• 1 \leq N \leq 100
• 0 \leq r_i < q_i \leq 10^9
• 1 \leq Q \leq 100
• 1 \leq t_j \leq N
• 1 \leq d_j \leq 10^9
• All input values are integers.

Sample Input 1

2
7 3
4 2
5
1 1
1 3
1 4
1 15
2 7

Sample Output 1

3
3
10
17
10

• 1st query: The 1st type of garbage is collected on day 3 for the first time after day 1.
• 2nd query: The 1st type of garbage is collected on day 3 for the first time after day 3.
• 3rd query: The 1st type of garbage is collected on day 10 for the first time after day 4.

Problem Statement

You are given a sequence of N positive numbers, A = (A_1, A_2, \dots, A_N). Find the sequence B = (B_1, B_2, \dots, B_N) of length N defined as follows.

• For i = 1, 2, \dots, N, define B_i as follows:
  • Let B_i be the most recent position before i where an element equal to A_i appeared. If such a position does not exist, let B_i = -1.
    More precisely, if there exists a positive integer j such that A_i = A_j and j < i, let B_i be the largest such j. If no such j exists, let B_i = -1.

Constraints

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

Sample Input 1

5
1 2 1 1 3

Sample Output 1

-1 -1 1 3 -1

• i = 1: There is no 1 before A_1 = 1, so B_1 = -1.
• i = 2: There is no 2 before A_2 = 2, so B_2 = -1.
• i = 3: The most recent occurrence of 1 before A_3 = 1 is A_1, so B_3 = 1.
• i = 4: The most recent occurrence of 1 before A_4 = 1 is A_3, so B_4 = 3.
• i = 5: There is no 3 before A_5 = 3, so B_5 = -1.

Sample Input 2

4
1 1000000000 1000000000 1

Sample Output 2

-1 -1 2 1

Problem Statement

There is a grid of H \times W cells. Let (i, j) denote the cell at the i-th row from the top and the j-th column from the left.

Cell (i, j) is empty if S_{i,j} is ., and blocked if it is #.

Count the number of ways to start from an empty cell and make K moves to adjacent cells (up, down, left, or right), without passing through blocked squares and not visiting the same cell more than once.

Specifically, count the number of sequences of length K+1, ((i_0, j_0), (i_1, j_1), \dots, (i_K, j_K)), satisfying the following.

• 1 \leq i_k \leq H, 1 \leq j_k \leq W, and S_{i_k, j_k} is ., for each 0 \leq k \leq K.
• |i_{k+1} - i_k| + |j_{k+1} - j_k| = 1 for each 0 \leq k \leq K-1.
• (i_k, j_k) \neq (i_l, j_l) for each 0 \leq k < l \leq K.

Constraints

• 1 \leq H, W \leq 10
• 1 \leq K \leq 11
• H, W, and K are integers.
• Each S_{i,j} is . or #.
• There is at least one empty cell.

Sample Input 1

2 2 2
.#
..

Sample Output 1

2

Here are the two possible paths:

• (1,1) \rightarrow (2,1) \rightarrow (2,2)
• (2,2) \rightarrow (2,1) \rightarrow (1,1)

Sample Input 2

2 3 1
.#.
#.#

Sample Output 2

0

Sample Input 3

10 10 11
....#..#..
.#.....##.
..#...##..
...#......
......##..
..#......#
#........#
..##......
.###....#.
...#.....#

Sample Output 3

218070

Problem Statement

You are given a sequence A = (A_1, A_2, \dots, A_N) of N non-negative integers, and a positive integer M.

Find the following value:

\[ \sum_{1 \leq l \leq r \leq N} \left( \left(\sum_{l \leq i \leq r} A_i\right) \mathbin{\mathrm{mod}} M \right). \]

Here, X \mathbin{\mathrm{mod}} M denotes the remainder when the non-negative integer X is divided by M.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 2 \times 10^5
• 0 \leq A_i \leq 10^9

Sample Input 1

3 4
2 5 0

Sample Output 1

10

• A_1 \mathbin{\mathrm{mod}} M = 2
• (A_1+A_2) \mathbin{\mathrm{mod}} M = 3
• (A_1+A_2+A_3) \mathbin{\mathrm{mod}} M = 3
• A_2 \mathbin{\mathrm{mod}} M = 1
• (A_2+A_3) \mathbin{\mathrm{mod}} M = 1
• A_3 \mathbin{\mathrm{mod}} M = 0

The answer is the sum of these values, 10. Note that the outer sum is not taken modulo M.

Sample Input 2

10 100
320 578 244 604 145 839 156 857 556 400

Sample Output 2

2736

Problem Statement

You are given a tree with N vertices. The i-th edge (1 \leq i \leq N-1) connects vertices u_i and v_i bidirectionally.

Adding one undirected edge to the given tree always yields a graph with exactly one cycle.

Among such graphs, how many satisfy all of the following conditions?

• The graph is simple.
• All vertices in the cycle have degree 3.

Constraints

• 3 \leq N \leq 2 \times 10^5
• 1 \leq u_i, v_i \leq N
• The given graph is a tree.
• All input values are integers.

Sample Input 1

6
1 2
2 3
3 4
4 5
3 6

Sample Output 1

1

Adding an edge connecting vertices 2 and 4 yields a simple graph where all vertices in the cycle have degree 3, so it satisfies the conditions.

Sample Input 2

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

Sample Output 2

0

There are cases where no graphs satisfy the conditions.

Sample Input 3

15
1 15
11 14
2 10
1 7
9 8
6 9
4 12
14 5
4 9
8 11
7 4
1 13
3 6
11 10

Sample Output 3

6

Problem Statement

You are given integers A, B, and M.

How many permutations P = (P_1, \dots, P_{AB-1}) of (1, 2, \ldots, AB - 1) satisfy all of the following conditions? Find the count modulo M.

• The length of a longest increasing subsequence of P is A.
• The length of a longest decreasing subsequence of P is B.
• There exists an integer n such that appending n + 0.5 to the end of P does not change either of the lengths of a longest increasing subsequence and a longest decreasing subsequence.

Constraints

• All input values are integers.
• 2 \leq A, B
• AB \leq 120
• 10^8 \leq M \leq 10^9
• M is a prime.

Sample Input 1

3 2 998244353

Sample Output 1

10

For example, P = (2, 4, 5, 1, 3) satisfies the conditions. This can be confirmed as follows:

• The length of a longest increasing subsequence of P is 3.
• The length of a longest decreasing subsequence of P is 2.
• For n = 4, the lengths of longest increasing and decreasing subsequences of (2, 4, 5, 1, 3, 4.5) are 3 and 2, respectively.

There are 10 permutations of (1, 2, 3, 4, 5) that satisfy the conditions.

Sample Input 2

10 12 924844033

Sample Output 2

623378361

Print the count modulo M.