Problem Statement

You are given a sequence P that is a permutation of (1,2,…,N), and an integer X. The i-th term of P has a value of P_i. Print k such that P_k = X.

Constraints

• 1 \leq N \leq 100
• 1 \leq X \leq N
• P is a permutation of (1,2,…,N).
• All values in the input are integers.

Sample Input 1

4 3
2 3 1 4

Sample Output 1

2

We have P = (2,3,1,4), so P_2 = 3. Thus, you should print 2.

Sample Input 2

5 2
3 5 1 4 2

Sample Output 2

5

Sample Input 3

6 6
1 2 3 4 5 6

Sample Output 3

6

Problem Statement

You are given N strings, each of length 2, consisting of uppercase English letters and digits. The i-th string is S_i.
Determine whether the following three conditions are all satisfied.
・For every string, the first character is one of H, D, C, and S.
・For every string, the second character is one of A, 2, 3, 4, 5, 6, 7, 8, 9, T, J, Q, K.
・All strings are pairwise different. That is, if i \neq j, then S_i \neq S_j.

Constraints

• 1 \leq N \leq 52
• S_i is a string of length 2 consisting of uppercase English letters and digits.

Sample Input 1

4
H3
DA
D3
SK

Sample Output 1

Yes

One can verify that the three conditions are all satisfied.

Sample Input 2

5
H3
DA
CK
H3
S7

Sample Output 2

No

Both S_1 and S_4 are H3, violating the third condition.

Sample Input 3

4
3H
AD
3D
KS

Sample Output 3

No

Sample Input 4

5
00
AA
XX
YY
ZZ

Sample Output 4

No

Problem Statement

There is a 10^9-story building with N ladders.
Takahashi, who is on the 1-st (lowest) floor, wants to reach the highest floor possible by using ladders (possibly none).
The ladders are numbered from 1 to N, and ladder i connects the A_i-th and B_i-th floors. One can use ladder i in either direction to move from the A_i-th floor to the B_i-th floor or vice versa, but not between other floors.
Takahashi can freely move within the same floor, but cannot move between floors without using ladders.
What is the highest floor Takahashi can reach?

Constraints

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

Sample Input 1

4
1 4
4 3
4 10
8 3

Sample Output 1

10

He can reach the 10-th floor by using ladder 1 to get to the 4-th floor and then ladder 3 to get to the 10-th floor.

Sample Input 2

6
1 3
1 5
1 12
3 5
3 12
5 12

Sample Output 2

12

Sample Input 3

3
500000000 600000000
600000000 700000000
700000000 800000000

Sample Output 3

1

He may be unable to move between floors.

Problem Statement

Takahashi has N cards in his hand. For i = 1, 2, \ldots, N, the i-th card has an non-negative integer A_i written on it.

First, Takahashi will freely choose a card from his hand and put it on a table. Then, he will repeat the following operation as many times as he wants (possibly zero).

• Let X be the integer written on the last card put on the table. If his hand contains cards with the integer X or the integer (X+1)\bmod M written on them, freely choose one of those cards and put it on the table. Here, (X+1)\bmod M denotes the remainder when (X+1) is divided by M.

Print the smallest possible sum of the integers written on the cards that end up remaining in his hand.

Constraints

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

Sample Input 1

9 7
3 0 2 5 5 3 0 6 3

Sample Output 1

11

Assume that he first puts the fourth card (5 is written) on the table and then performs the following.

• Put the fifth card (5 is written) on the table.
• Put the eighth card (6 is written) on the table.
• Put the second card (0 is written) on the table.
• Put the seventh card (0 is written) on the table.

Then, the first, third, sixth, and ninth cards will end up remaining in his hand, and the sum of the integers on those cards is 3 + 2 + 3 +3 = 11. This is the minimum possible sum of the integers written on the cards that end up remaining in his hand.

Sample Input 2

1 10
4

Sample Output 2

0

Sample Input 3

20 20
18 16 15 9 8 8 17 1 3 17 11 9 12 11 7 3 2 14 3 12

Sample Output 3

99

Problem Statement

You are given an undirected graph consisting of N vertices and M edges.
For i = 1, 2, \ldots, M, the i-th edge is an undirected edge connecting vertex u_i and v_i that is initially passable if a_i = 1 and initially impassable if a_i = 0. Additionally, there are switches on K of the vertices: vertex s_1, vertex s_2, \ldots, vertex s_K.

Takahashi is initially on vertex 1, and will repeat performing one of the two actions below, Move or Hit Switch, which he may choose each time, as many times as he wants.

• Move: Choose a vertex adjacent to the vertex he is currently on via an edge, and move to that vertex.
• Hit Switch: If there is a switch on the vertex he is currently on, hit it. This will invert the passability of every edge in the graph. That is, a passable edge will become impassable, and vice versa.

Determine whether Takahashi can reach vertex N, and if he can, print the minimum possible number of times he performs Move before reaching vertex N.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 2 \times 10^5
• 0 \leq K \leq N
• 1 \leq u_i, v_i \leq N
• u_i \neq v_i
• a_i \in \lbrace 0, 1\rbrace
• 1 \leq s_1 \lt s_2 \lt \cdots \lt s_K \leq N
• All values in the input are integers.

Sample Input 1

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

Sample Output 1

5

Takahashi can reach vertex N as follows.

• Move from vertex 1 to vertex 2.
• Move from vertex 2 to vertex 3.
• Hit the switch on vertex 3. This inverts the passability of every edge in the graph.
• Move from vertex 3 to vertex 1.
• Move from vertex 1 to vertex 4.
• Hit the switch on vertex 4. This again inverts the passability of every edge in the graph.
• Move from vertex 4 to vertex 5.

Here, Move is performed five times, which is the minimum possible number.

Sample Input 2

4 4 2
4 3 0
1 2 1
1 2 0
2 1 1
2 4

Sample Output 2

-1

The given graph may be disconnected or contain multi-edges. In this sample input, there is no way for Takahashi to reach vertex N, so you should print -1.

Problem Statement

You are given a matrix A whose elements are non-negative integers. For a pair of integers (i, j) such that 1 \leq i \leq H and 1 \leq j \leq W, let A_{i, j} denote the element at the i-th row and j-th column of A.

Let us perform the following procedure on A.

• First, replace each element of A that is 0 with an arbitrary positive integer (if multiple elements are 0, they may be replaced with different positive integers).

• Then, repeat performing one of the two operations below, which may be chosen each time, as many times as desired (possibly zero).

  • Choose a pair of integers (i, j) such that 1 \leq i \lt j \leq H and swap the i-th and j-th rows of A.
  • Choose a pair of integers (i, j) such that 1 \leq i \lt j \leq W and swap the i-th and j-th columns of A.

Determine whether A can be made to satisfy the following condition.

• A_{1, 1} \leq A_{1, 2} \leq \cdots \leq A_{1, W} \leq A_{2, 1} \leq A_{2, 2} \leq \cdots \leq A_{2, W} \leq A_{3, 1} \leq \cdots \leq A_{H, 1} \leq A_{H, 2} \leq \cdots \leq A_{H, W}.

• In other words, for every two pairs of integers (i, j) and (i', j') such that 1 \leq i, i' \leq H and 1 \leq j, j' \leq W, both of the following conditions are satisfied.

  • If i \lt i', then A_{i, j} \leq A_{i', j'}.
  • If i = i' and j \lt j', then A_{i, j} \leq A_{i', j'}.

Constraints

• 2 \leq H, W
• H \times W \leq 10^6
• 0 \leq A_{i, j} \leq H \times W
• All values in the input are integers.

Sample Input 1

3 3
9 6 0
0 4 0
3 0 3

Sample Output 1

Yes

One can perform the operations as follows to make A satisfy the condition in the problem statement, so you should print Yes.

• First, replace the elements of A that are 0, as shown below:

9 6 8
5 4 4
3 1 3

• Swap the second and third columns. Then, A becomes:

9 8 6
5 4 4
3 3 1

• Swap the first and third rows. Then, A becomes:

3 3 1
5 4 4
9 8 6

• Swap the first and third columns. Then, A becomes the following and satisfies the condition in the problem statement.

1 3 3
4 4 5
6 8 9

Sample Input 2

2 2
2 1
1 2

Sample Output 2

No

There is no way to perform the operations to make A satisfy the condition in the problem statement, so you should print No.

Problem Statement

You are given a connected simple undirected graph consisting of N vertices and M edges.
For i = 1, 2, \ldots, M, the i-th edge connects vertex u_i and vertex v_i.

Takahashi starts at Level 0 on vertex 1, and will perform the following action exactly K times.

• First, choose one of the vertices adjacent to the vertex he is currently on, uniformly at random, and move to the chosen vertex.
• Then, the following happens according to the vertex v he has moved to.
  • If C_v = 0: Takahashi's Level increases by 1.
  • If C_v = 1: Takahashi receives a money of X^2 yen, where X is his current Level.

Print the expected value of the total amount of money Takahashi receives during the K actions above, modulo 998244353 (see Notes).

Notes

It can be proved that the sought expected value is always a rational number. Additionally, under the Constraints of this problem, when that value is represented as \frac{P}{Q} using two coprime integers P and Q, it can also be proved that there is a unique integer R such that R \times Q \equiv P\pmod{998244353} and 0 \leq R \lt 998244353. Find this R.

Constraints

• 2 \leq N \leq 3000
• N-1 \leq M \leq \min\lbrace N(N-1)/2, 3000\rbrace
• 1 \leq K \leq 3000
• 1 \leq u_i, v_i \leq N
• u_i \neq v_i
• i \neq j \implies \lbrace u_i, v_i\rbrace \neq \lbrace u_j, v_j \rbrace
• The given graph is connected.
• C_i \in \lbrace 0, 1\rbrace
• All values in the input are integers.

Sample Input 1

5 4 8
4 5
2 3
2 4
1 2
0 0 1 1 0

Sample Output 1

89349064

Among the multiple paths that Takahashi may traverse, let us take a case where Takahashi starts on vertex 1 and goes along the path 1 \rightarrow 2 \rightarrow 4 \rightarrow 5 \rightarrow 4 \rightarrow 2 \rightarrow 1 \rightarrow 2 \rightarrow 3, and compute the total amount of money he receives.

1. In the first action, he moves from vertex 1 to an adjacent vertex, vertex 2. Then, since C_2 = 0, his Level increases to 1.
2. In the second action, he moves from vertex 2 to an adjacent vertex, vertex 4. Then, since C_4 = 1, he receives 1^2 = 1 yen.
3. In the third action, he moves from vertex 4 to an adjacent vertex, vertex 5. Then, since C_5 = 0, his Level increases to 2.
4. In the fourth action, he moves from vertex 5 to an adjacent vertex, vertex 4. Then, since C_4 = 1, he receives 2^2 = 4 yen.
5. In the fifth action, he moves from vertex 4 to an adjacent vertex, vertex 2. Then, since C_2 = 0, his Level increases to 3.
6. In the sixth action, he moves from vertex 2 to an adjacent vertex, vertex 1. Then, since C_1 = 0, his Level increases to 4.
7. In the seventh action, he moves from vertex 1 to an adjacent vertex, vertex 2. Then, since C_2 = 0, his Level increases to 5.
8. In the eighth action, he moves from vertex 2 to an adjacent vertex, vertex 3. Then, since C_3 = 1, he receives 5^2 = 25 yen.

Thus, he receives a total of 1 + 4 + 25 = 30 yen.

Sample Input 2

8 12 20
7 6
2 6
6 4
2 1
8 5
7 2
7 5
3 7
3 5
1 8
6 3
1 4
0 0 1 1 0 0 0 0

Sample Output 2

139119094

Problem Statement

Determine whether there is a sequence of N integers X = (X_1, X_2, \ldots ,X_N) that satisfies all of the following conditions, and construct one such sequence if it exists.

• 0 \leq X_i \leq M for every 1 \leq i \leq N.
  
• L_i \leq X_{A_i} + X_{B_i} \leq R_i for every 1 \leq i \leq Q.

Constraints

• 1 \leq N \leq 10000
• 1 \leq M \leq 100
• 1 \leq Q \leq 10000
• 1 \leq A_i, B_i \leq N
• 0 \leq L_i \leq R_i \leq 2 \times M
• All values in the input are integers.

Sample Input 1

4 5 3
1 3 5 7
1 4 1 2
2 2 3 8

Sample Output 1

2 4 3 0

For X = (2,4,3,0), we have X_1 + X_3 = 5, X_1 + X_4 = 2, and X_2 + X_2 = 8, so all conditions are satisfied. There are other sequences, such as X = (0,2,5,2) and X = (1,3,4,1), that satisfy all conditions, and those will also be accepted.

Sample Input 2

3 7 3
1 2 3 4
3 1 9 12
2 3 2 4

Sample Output 2

-1

No sequence X satisfies all conditions.