Problem Statement

We have a sequence of length N: A=(a_1,\ldots,a_N). Additionally, you are given an integer K.

You can perform the following operation zero or more times.

• Choose an integer i such that 1 \leq i \leq N-K, then swap the values of a_i and a_{i+K}.

Determine whether it is possible to sort A in ascending order.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq K \leq N-1
• 1 \leq a_i \leq 10^9
• All values in input are integers.

Sample Input 1

5 2
3 4 1 3 4

Sample Output 1

Yes

The following sequence of operations sorts A in ascending order.

• Choose i=1 to swap the values of a_1 and a_3. A is now (1,4,3,3,4).
• Choose i=2 to swap the values of a_2 and a_4. A is now (1,3,3,4,4).

Sample Input 2

5 3
3 4 1 3 4

Sample Output 2

No

Sample Input 3

7 5
1 2 3 4 5 5 10

Sample Output 3

Yes

No operations may be needed.

Problem Statement

We have N cups of ice cream.
The flavor and deliciousness of the i-th cup are F_i and S_i, respectively (S_i is an even number).

You will choose and eat two of the N cups.
Your satisfaction here is defined as follows.

• Let s and t (s \ge t) be the deliciousness of the eaten cups.
  • If the two cups have different flavors, your satisfaction is \displaystyle s+t.
  • Otherwise, your satisfaction is \displaystyle s + \frac{t}{2}.

Find the maximum achievable satisfaction.

Constraints

• All input values are integers.
• 2 \le N \le 3 \times 10^5
• 1 \le F_i \le N
• 2 \le S_i \le 10^9
• S_i is even.

Sample Input 1

4
1 4
2 10
2 8
3 6

Sample Output 1

16

Consider eating the second and fourth cups.

• The second cup has a flavor of 2 and deliciousness of 10.
• The fourth cup has a flavor of 3 and deliciousness of 6.
• Since they have different flavors, your satisfaction is 10+6=16.

Thus, you can achieve the satisfaction of 16.
You cannot achieve a satisfaction greater than 16.

Sample Input 2

4
4 10
3 2
2 4
4 12

Sample Output 2

17

Consider eating the first and fourth cups.

• The first cup has a flavor of 4 and deliciousness of 10.
• The fourth cup has a flavor of 4 and deliciousness of 12.
• Since they have the same flavor, your satisfaction is 12+\frac{10}{2}=17.

Thus, you can achieve the satisfaction of 17.
You cannot achieve a satisfaction greater than 17.

Problem Statement

We have an undirected graph with (N_1+N_2) vertices and M edges. For i=1,2,\ldots,M, the i-th edge connects vertex a_i and vertex b_i.
The following properties are guaranteed:

• Vertex u and vertex v are connected, for all integers u and v with 1 \leq u,v \leq N_1.
• Vertex u and vertex v are connected, for all integers u and v with N_1+1 \leq u,v \leq N_1+N_2.
• Vertex 1 and vertex (N_1+N_2) are disconnected.

Consider performing the following operation exactly once:

• choose an integer u with 1 \leq u \leq N_1 and an integer v with N_1+1 \leq v \leq N_1+N_2, and add an edge connecting vertex u and vertex v.

We can show that vertex 1 and vertex (N_1+N_2) are always connected in the resulting graph; so let d be the minimum length (number of edges) of a path between vertex 1 and vertex (N_1+N_2).

Find the maximum possible d resulting from adding an appropriate edge to add.

Constraints

• 1 \leq N_1,N_2 \leq 1.5 \times 10^5
• 0 \leq M \leq 3 \times 10^5
• 1 \leq a_i \leq b_i \leq N_1+N_2
• (a_i,b_i) \neq (a_j,b_j) if i \neq j.
• Vertex u and vertex v are connected for all integers u and v such that 1 \leq u,v \leq N_1.
• Vertex u and vertex v are connected for all integers u and v such that N_1+1 \leq u,v \leq N_1+N_2.
• Vertex 1 and vertex (N_1+N_2) are disconnected.
• All input values are integers.

Sample Input 1

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

Sample Output 1

5

If we set u=2 and v=5, the operation yields d=5, which is the maximum possible.

Sample Input 2

7 5 20
10 11
4 5
10 12
1 2
1 5
5 6
2 4
3 5
9 10
2 5
1 4
11 12
9 12
8 9
5 7
3 7
3 6
3 4
8 12
9 11

Sample Output 2

4

Problem Statement

Takahashi has a playlist with N songs. Song i (1 \leq i \leq N) lasts T_i seconds.
Takahashi has started random play of the playlist at time 0.

Random play repeats the following: choose one song from the N songs with equal probability and play that song to the end. Here, songs are played continuously: once a song ends, the next chosen song starts immediately. The same song can be chosen consecutively.

Find the probability that song 1 is being played (X + 0.5) seconds after time 0, modulo 998244353.

Constraints

• 2 \leq N\leq 10^3
• 0 \leq X\leq 10^4
• 1 \leq T_i\leq 10^4
• All input values are integers.

Sample Input 1

3 6
3 5 6

Sample Output 1

369720131

Song 1 will be playing 6.5 seconds after time 0 if songs are played in one of the following orders.

• Song 1 \to Song 1 \to Song 1
• Song 2 \to Song 1
• Song 3 \to Song 1

The probability that one of these occurs is \frac{7}{27}.
We have 369720131\times 27\equiv 7 \pmod{998244353}, so you should print 369720131.

Sample Input 2

5 0
1 2 1 2 1

Sample Output 2

598946612

0.5 seconds after time 0, the first song to be played is still playing, so the sought probability is \frac{1}{5}.
Note that different songs may have the same length.

Sample Input 3

5 10000
1 2 3 4 5

Sample Output 3

586965467

Problem Statement

In the Kingdom of Takahashi, N citizens numbered 1 to N took an examination of competitive programming.
There were two tests, and Citizen i ranked P_i-th in the first test and Q_i-th in the second test.
There were no ties in either test. That is, each of the sequences P and Q is a permutation of (1, 2, ..., N).

Iroha, the president of the kingdom, is going to select K citizens for the national team at the coming world championship of competitive programming.
The members of the national team must be selected so that the following is satisfied.

• There should not be a pair of citizens (x, y) where Citizen x is selected and Citizen y is not selected such that P_x > P_y and Q_x > Q_y.
  • In other words, if Citizen y got a rank smaller than that of Citizen x in both tests, it is not allowed to select Citizen x while not selecting Citizen y.

To begin with, Iroha wants to know the number of ways to select citizens for the national team that satisfy the condition above. Find it to help her.
Since this number can be enormous, print it modulo 998244353.

Constraints

• All values in input are integers.
• 1 \le N \le 300
• 1 \le K \le N
• Each of P and Q is a permutation of (1,2,...,N).

Sample Input 1

4 2
2 4 3 1
2 1 4 3

Sample Output 1

3

• It is fine to select Citizen 1 and Citizen 2 for the team.
• If Citizen 1 and Citizen 3 are selected, Citizen 4 ranked higher than Citizen 3 did in both tests, so the pair (x,y)=(3,4) would violate the condition in the Problem Statement.
• It is fine to select Citizen 1 and Citizen 4.
• If Citizen 2 and Citizen 3 are selected, the pair (x,y)=(3,1) would violate the condition.
• It is fine to select Citizen 2 and Citizen 4.
• If Citizen 3 and Citizen 4 are selected, the pair (x,y)=(3,1) would violate the condition.

The final answer is 3.

Sample Input 2

33 16
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33
33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1

Sample Output 2

168558757

All \binom{33}{16} = 1166803110 ways of selecting 16 from the 33 citizens satisfy the requirement.
Therefore, we should print 1166803110 modulo 998244353, that is, 168558757.

Sample Input 3

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

Sample Output 3

23