Problem Statement

You are given a matrix A with H_1 rows and W_1 columns, and a matrix B with H_2 rows and W_2 columns.

• For all integer pairs (i, j) such that 1 \leq i \leq H_1 and 1 \leq j \leq W_1, the element at the i-th row and j-th column of matrix A is A_{i, j}.
• For all integer pairs (i, j) such that 1 \leq i \leq H_2 and 1 \leq j \leq W_2, the element at the i-th row and j-th column of matrix B is B_{i, j}.

You may perform the following operations on the matrix A any number of (possibly 0) times in any order:

• Choose an arbitrary row of A and remove it.
• Choose an arbitrary column of A and remove it.

Determine if it is possible to make the matrix A equal the matrix B.

Constraints

• 1 \leq H_2 \leq H_1 \leq 10
• 1 \leq W_2 \leq W_1 \leq 10
• 1 \leq A_{i, j} \leq 10^9
• 1 \leq B_{i, j} \leq 10^9
• All values in input are integers.

Sample Input 1

4 5
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
2 3
6 8 9
16 18 19

Sample Output 1

Yes

Removing the 2-nd column from the initial A results in:

1 3 4 5
6 8 9 10
11 13 14 15
16 18 19 20

Then, removing the 3-rd row from A results in:

1 3 4 5
6 8 9 10
16 18 19 20

Then, removing the 1-st row from A results in:

6 8 9 10
16 18 19 20

Then, removing the 4-th column from A results in:

6 8 9
16 18 19

Now the matrix equals the matrix B.
Thus, we can make the matrix A equal the matrix B by repeating the operations, so Yes should be printed.

Sample Input 2

3 3
1 1 1
1 1 1
1 1 1
1 1
2

Sample Output 2

No

Regardless of how we perform the operations, we cannot make the matrix A equal the matrix B, so No should be printed.

Problem Statement

Print all strictly increasing integer sequences of length N where all elements are between 1 and M (inclusive), in lexicographically ascending order.

Notes

For two integer sequences of the same length A_1,A_2,\dots,A_N and B_1,B_2,\dots,B_N, A is said to be lexicographically earlier than B if and only if:

• there is an integer i (1 \le i \le N) such that A_j=B_j for all integers j satisfying 1 \le j < i, and A_i < B_i.

An integer sequence A_1,A_2,\dots,A_N is said to be strictly increasing if and only if:

• A_i < A_{i+1} for all integers i (1 \le i \le N-1).

Constraints

• 1 \le N \le M \le 10
• All values in input are integers.

Sample Input 1

2 3

Sample Output 1

1 2 
1 3 
2 3 

The sought sequences are (1,2),(1,3),(2,3), which should be printed in lexicographically ascending order.

Sample Input 2

3 5

Sample Output 2

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

Problem Statement

Takahashi keeps a sleep log. The log is represented as an odd-length sequence A=(A _ 1(=0), A _ 2,\ldots,A _ N), where odd-numbered elements represent times he got up, and even-numbered elements represent times he went to bed. More formally, he had the following sleep sessions after starting the sleep log.

• For every integer i such that 1\leq i\leq\dfrac{N-1}2, he fell asleep exactly A _ {2i} minutes after starting the sleep log and woke up exactly A _ {2i+1} minutes after starting the sleep log.
• He did not fall asleep or wake up at any other time.

Answer the following Q questions. For the i-th question, you are given a pair of integers (l _ i,r _ i) such that 0\leq l _ i\leq r _ i\leq A _ N.

• What is the total number of minutes for which Takahashi was asleep during the r _ i-l _ i minutes from exactly l _ i minutes to r _ i minutes after starting the sleep log?

Constraints

• 3\leq N\lt2\times10^5
• N is odd.
• 0=A _ 1\lt A _ 2\lt\cdots\lt A _ N\leq10^9
• 1\leq Q\leq2\times10^5
• 0\leq l _ i\leq r _ i\leq A _ N\ (1\leq i\leq Q)
• All input values are integers.

Sample Input 1

7
0 240 720 1320 1440 1800 2160
3
480 1920
720 1200
0 2160

Sample Output 1

480
0
960

Takahashi slept as shown in the following figure.

The answers to each question are as follows.

• Between 480 minutes and 1920 minutes after starting the sleep log, Takahashi slept from 480 minutes to 720 minutes, from 1320 minutes to 1440 minutes, and from 1800 minutes to 1920 minutes in 3 sleep sessions. The total sleep time is 240+120+120=480 minutes.
• Between 720 minutes and 1200 minutes after starting the sleep log, Takahashi did not sleep. The total sleep time is 0 minutes.
• Between 0 minutes and 2160 minutes after starting the sleep log, Takahashi slept from 240 minutes to 720 minutes, from 1320 minutes to 1440 minutes, and from 1800 minutes to 2160 minutes in 3 sleep sessions. The total sleep time is 480+120+360=960 minutes.

Therefore, the three lines of the output should contain 480, 0, and 960.

Sample Input 2

21
0 20 62 192 284 310 323 324 352 374 409 452 486 512 523 594 677 814 838 946 1000
10
77 721
255 541
478 970
369 466
343 541
42 165
16 618
222 592
730 983
338 747

Sample Output 2

296
150
150
49
89
20
279
183
61
177

Problem Statement

You are given a simple connected undirected graph with N vertices and M edges (a simple graph contains no self-loop and no multi-edges).
For i = 1, 2, \ldots, M, the i-th edge connects vertex u_i and vertex v_i bidirectionally.

Determine whether there is a way to paint each vertex black or white to satisfy both of the following conditions, and show one such way if it exists.

• At least one vertex is painted black.
• For every i = 1, 2, \ldots, K, the following holds:
  • the minimum distance between vertex p_i and a vertex painted black is exactly d_i.

Here, the distance between vertex u and vertex v is the minimum number of edges in a path connecting u and v.

Constraints

• 1 \leq N \leq 2000
• N-1 \leq M \leq \min\lbrace N(N-1)/2, 2000 \rbrace
• 1 \leq u_i, v_i \leq N
• 0 \leq K \leq N
• 1 \leq p_1 \lt p_2 \lt \cdots \lt p_K \leq N
• 0 \leq d_i \leq N
• The given graph is simple and connected.
• All values in the input are integers.

Sample Input 1

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

Sample Output 1

Yes
10100

One way to satisfy the conditions is to paint vertices 1, 3 black and vertices 2, 4, 5 white.
Indeed, for each i = 1, 2, 3, 4, 5, let A_i denote the minimum distance between vertex i and a vertex painted black, and we have (A_1, A_2, A_3, A_4, A_5) = (0, 1, 0, 1, 2), where A_1 = 0, A_5 = 2.

Sample Input 2

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

Sample Output 2

No

There is no way to satisfy the conditions by painting each vertex black or white, so you should print No.

Sample Input 3

1 0
0

Sample Output 3

Yes
1

Problem Statement

Given is a string S. How many different strings can be obtained as a permutation of a non-empty, not necessarily contiguous subsequence of S?

Since the count can be enormous, print it modulo 998244353.

Constraints

• S is a string of length 1 and 5000 (inclusive) consisting of lowercase English letters.

Sample Input 1

aab

Sample Output 1

8

There are 8 different strings that can be obtained as a permutation of a subsequence of S: a, b, aa, ab, ba, aab, aba, baa.

Sample Input 2

aaa

Sample Output 2

3

Sample Input 3

abcdefghijklmnopqrstuvwxyz

Sample Output 3

149621752

Be sure to print the count modulo 998244353.