Problem Statement

A sport event is held in June of every year whose remainder when divided by 4 is 2.
Suppose that it is now January of the year Y. In what year will this sport event be held next time?

Constraints

• 2000 \leq Y \leq 3000
• Y is an integer.

Sample Input 1

2022

Sample Output 1

2022

The remainder when 2022 is divided by 4 is 2, so if it is now January of 2022, the next games will be held in June of the same year.

Sample Input 2

2023

Sample Output 2

2026

Sample Input 3

3000

Sample Output 3

3002

Problem Statement

You are given a simple undirected graph with N vertices and M edges. The vertices are numbered 1, \dots, N, and the i-th (1 \leq i \leq M) edge connects Vertex U_i and Vertex V_i.

Find the number of tuples of integers a, b, c that satisfy all of the following conditions:

• 1 \leq a \lt b \lt c \leq N
• There is an edge connecting Vertex a and Vertex b.
• There is an edge connecting Vertex b and Vertex c.
• There is an edge connecting Vertex c and Vertex a.

Constraints

• 3 \leq N \leq 100
• 1 \leq M \leq \frac{N(N - 1)}{2}
• 1 \leq U_i \lt V_i \leq N \, (1 \leq i \leq M)
• (U_i, V_i) \neq (U_j, V_j) \, (i \neq j)
• All values in input are integers.

Sample Input 1

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

Sample Output 1

2

(a, b, c) = (1, 4, 5), (2, 3, 5) satisfy the conditions.

Sample Input 2

3 1
1 2

Sample Output 2

0

Sample Input 3

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

Sample Output 3

4

Problem Statement

You are given a sequence a = (a_1, \dots, a_N) of length N consisting of integers between 1 and N.

Find the number of pairs of integers i, j that satisfy all of the following conditions:

• 1 \leq i \lt j \leq N
• \min(a_i, a_j) = i
• \max(a_i, a_j) = j

Constraints

• 2 \leq N \leq 5 \times 10^5
• 1 \leq a_i \leq N \, (1 \leq i \leq N)
• All values in input are integers.

Sample Input 1

4
1 3 2 4

Sample Output 1

2

(i, j) = (1, 4), (2, 3) satisfy the conditions.

Sample Input 2

10
5 8 2 2 1 6 7 2 9 10

Sample Output 2

8

Problem Statement

You are given a sequence of positive integers A=(a_1,\ldots,a_N) of length N.
There are (2^N-1) ways to choose one or more terms of A. How many of them have an integer-valued average? Find the count modulo 998244353.

Constraints

• 1 \leq N \leq 100
• 1 \leq a_i \leq 10^9
• All values in input are integers.

Sample Input 1

3
2 6 2

Sample Output 1

6

For each way to choose terms of A, the average is obtained as follows:

• If just a_1 is chosen, the average is \frac{a_1}{1}=\frac{2}{1} = 2, which is an integer.

• If just a_2 is chosen, the average is \frac{a_2}{1}=\frac{6}{1} = 6, which is an integer.

• If just a_3 is chosen, the average is \frac{a_3}{1}=\frac{2}{1} = 2, which is an integer.

• If a_1 and a_2 are chosen, the average is \frac{a_1+a_2}{2}=\frac{2+6}{2} = 4, which is an integer.

• If a_1 and a_3 are chosen, the average is \frac{a_1+a_3}{2}=\frac{2+2}{2} = 2, which is an integer.

• If a_2 and a_3 are chosen, the average is \frac{a_2+a_3}{2}=\frac{6+2}{2} = 4, which is an integer.

• If a_1, a_2, and a_3 are chosen, the average is \frac{a_1+a_2+a_3}{3}=\frac{2+6+2}{3} = \frac{10}{3}, which is not an integer.

Therefore, 6 ways satisfy the condition.

Sample Input 2

5
5 5 5 5 5

Sample Output 2

31

Regardless of the choice of one or more terms of A, the average equals 5.

Problem Statement

You are given a simple undirected graph with N vertices and M edges. The vertices are numbered 1, \dots, N, and the i-th (1 \leq i \leq M) edge connects Vertices U_i and V_i.

There are 2^N ways to paint each vertex red or blue. Find the number, modulo 998244353, of such ways that satisfy all of the following conditions:

• There are exactly K vertices painted red.
• There is an even number of edges connecting vertices painted in different colors.

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 \lt V_i \leq N \, (1 \leq i \leq M)
• (U_i, V_i) \neq (U_j, V_j) \, (i \neq j)
• All values in input are integers.

Sample Input 1

4 4 2
1 2
1 3
2 3
3 4

Sample Output 1

2

The following two ways satisfy the conditions.

• Paint Vertices 1 and 2 red and Vertices 3 and 4 blue.
• Paint Vertices 3 and 4 red and Vertices 1 and 2 blue.

In either of the ways above, the 2-nd and 3-rd edges connect vertices painted in different colors.

Sample Input 2

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

Sample Output 2

64

Problem Statement

You are given a sequence P = (p_1,p_2,\ldots,p_N) that contains 1,2,\ldots,N exactly once each.
You may perform the following operations between 0 and K times in total in any order:

• Choose one term of P and remove it.
• Move the last term of P to the head.

Find the lexicographically smallest P that can be obtained as a result of the operations.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq K \leq N-1
• 1 \leq p_i \leq N
• (p_1,p_2,\ldots,p_N) contains 1,2,\ldots,N exactly once each.
• All values in input are integers.

Sample Input 1

5 3
4 5 2 3 1

Sample Output 1

1 2 3

The following operations make P equal (1,2,3).

• Removing the first term makes P equal (5,2,3,1).
• Moving the last term to the head makes P equal (1,5,2,3).
• Removing the second term makes P equal (1,2,3).

There is no way to obtain P lexicographically smaller than (1,2,3), so this is the answer.

Sample Input 2

3 0
3 2 1

Sample Output 2

3 2 1

You may be unable to perform operations.

Sample Input 3

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

Sample Output 3

1 3 4 7 2 8 11 9

Problem Statement

There is an empty sequence X and an empty stack S. Also, you are given an integer sequence A=(a_1,\ldots,a_N) of length N.
For each i=1,\ldots,N in this order, Takahashi will do one of the following operations:

• Move the integer a_i onto the top of S.
• Discard the integer a_i from A.

Additionally, Takahashi may do the following operation whenever S is not empty:

• Move the integer at the top of S to the tail of X.

The score of the final X is defined as follows.

• If X is non-decreasing, i.e. if x_i \leq x_{i+1} holds for all integer i(1 \leq i \lt |X|), where X=(x_1,\ldots,x_{|X|}), then the score is |X| (where |X| denotes the number of terms in X).
• If X is not non-decreasing, then the score is 0.

Find the maximum possible score.

Constraints

• 1 \leq N \leq 50
• 1 \leq a_i \leq 50
• All values in input are integers.

Sample Input 1

7
1 2 3 4 1 2 3

Sample Output 1

5

The following operations make the final X equal (1,1,2,3,4), for a score of 5.

• Move a_1=1 onto the top of S.
• Move 1 at the top of S to the tail of X.
• Move a_2=2 onto the top of S.
• Discard a_3=3.
• Move a_4=4 onto the top of S.
• Move a_5=1 onto the top of S.
• Move 1 at the top of S to the tail of X.
• Move a_6=2 onto the top of S.
• Move 2 at the top of S to the tail of X.
• Move a_7=3 onto the top of S.
• Move 3 at the top of S to the tail of X.
• Move 4 at the top of S to the tail of X.

We cannot make the score 6 or greater, so the maximum possible score is 5.

Sample Input 2

10
1 1 1 1 1 1 1 1 1 1

Sample Output 2

10

Problem Statement

Find the number, modulo 998244353, of integer sequences A = (A_1, \dots, A_N) of length N that satisfy all of the following conditions:

• 0 \leq A_i \leq M for all i such that 1 \leq i \leq N.
• The maximum value of A_{L_j}, \dots, A_{R_j} is X_j for all j such that 1 \leq j \leq Q.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq M \lt 998244353
• 1 \leq Q \leq 2 \times 10^5
• 1 \leq L_i \leq R_i \leq N \, (1 \leq i \leq Q)
• 1 \leq X_i \leq M \, (1 \leq i \leq Q)
• All values in input are integers.

Sample Input 1

3 3 2
1 2 2
2 3 3

Sample Output 1

5

A = (0, 2, 3), (1, 2, 3), (2, 0, 3), (2, 1, 3), (2, 2, 3) satisfy the conditions.

Sample Input 2

1 1 1
1 1 1

Sample Output 2

1

Sample Input 3

6 40000000 3
1 4 30000000
2 6 20000000
3 5 10000000

Sample Output 3

135282163