Problem Statement

You keep N monsters numbered 1 to N.

A hero has come to slay your monsters. He will take M turns to attack the monsters. In the i-th turn, he performs one of the following actions.

• Consume 1 MP to attack monster X_i. This action can only be performed when monster X_i is still alive and the hero has at least 1 MP.

• Do nothing.

If the hero attacks, you will respond by performing one of the following actions.

• Consume 1 MP to defend monster X_i. This action can only be performed when you have at least 1 MP.

• Do nothing. The monster will die.

Before the first turn begins, the hero has A MP, and you have B MP. Both you and the hero know all values of N, M, A, B, and X_i. Find the greatest integer k that satisfies the following condition.

• By using an appropriate strategy, you can keep at least k monsters alive no matter how the hero acts.

Constraints

• 1 \leq N,M \leq 250000
• 1 \leq B \leq A \leq M
• 1 \leq X_i \leq N
• All input values are integers.

Sample Input 1

2 3 2 1
1 2 1

Sample Output 1

1

You can always keep at least one monster alive.

Here is one possible progression.

• The first turn: The hero attacks monster 1.
  • You do nothing, and monster 1 dies.
• The second turn: The hero attacks monster 2.
  • You defend monster 2.
• The third turn: The hero does nothing.

Sample Input 2

2 6 3 2
1 1 1 2 2 2

Sample Output 2

1

Sample Input 3

100 1 1 1
100

Sample Output 3

100

Sample Input 4

6 20 16 5
5 6 1 3 2 1 4 3 2 4 1 4 4 6 3 3 5 2 2 2

Sample Output 4

2

Problem Statement

You are given a permutation P=(P_1,P_2,\cdots,P_N) of (1,2,\cdots,N).

Find one sequence of integer pairs ((l_1,r_1),(l_2,r_2),\cdots,(l_k,r_k)) that satisfies all of the following conditions.

• The length k of the sequence satisfies 0 \leq k \leq N-1.
• 1 \leq l_i \leq r_i \leq N (1 \leq i \leq k).
• For each 1 \leq i \leq k-1, it holds that r_{i+1} \leq l_i or r_i \leq l_{i+1}.
• Performing the following k operations sorts P in ascending order.
  • The i-th operation: swap the values of P_{l_i} and P_{r_i}. If l_i=r_i, do nothing.

It can be proved that such a sequence always exists under the constraints of this problem.

Process T test cases for each input file.

Constraints

• 1 \leq T \leq 250000
• 1 \leq N \leq 250000
• P=(P_1,P_2,\cdots,P_N) is a permutation of (1,2,\cdots,N).
• The sum of N for each input file is at most 250000.
• All input values are integers.

Sample Input 1

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

Sample Output 1

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

Let us explain the first test case.

The sample output satisfies all of the conditions. For example, the fourth condition can be verified as follows: P=(2,3,1)\to(swap P_2,P_3)\to(2,1,3)\to(swap P_1,P_2)\to(1,2,3)．

The following output, on the other hand, is not correct:

2
1 2
1 3

This is because the third condition is not satisfied.

Problem Statement

You are given a tree T with N vertices numbered 1 to N. The i-th edge connects vertices A_i and B_i.

You can perform the following operation any number of times, possibly zero.

• Choose two leaves u and v of T such that the distance between them is odd. Then, remove u and v from T (along with the incident edges).

Here, a vertex is said to be a leaf when its degree is exactly one at the time of the operation. The distance between two vertices is the number of edges in the path connecting those vertices.

Find the number, modulo 998244353, of sets that can be the vertex set of T after your operations.

Constraints

• 2 \leq N \leq 150
• 1 \leq A_i,B_i \leq N
• The input graph is a tree.
• All input values are integers.

Sample Input 1

4
1 2
2 3
3 4

Sample Output 1

3

Performing zero operations yields the vertex set \{1,2,3,4\}.

Erasing the leaves 1 and 4 from T yields the vertex set \{2,3\}.

From this state, erasing the leaves 2 and 3 yields the vertex set \{\}.

Sample Input 2

5
2 1
3 1
4 1
5 3

Sample Output 2

3

Sample Input 3

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

Sample Output 3

11

Sample Input 4

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

Sample Output 4

5359

Problem Statement

There are M competitive programmers (kyopro-ers) numbered 1 to M, who will visit Tokyo during the N days starting today. Kyopro-er i will stay in Tokyo from the L_i-th day through the R_i-th day (1 \leq L_i \leq R_i \leq N).

Maroon is planning dinner parties with them. If a dinner party is held on the x-th day (1 \leq x \leq N), he can make friends with all kyopro-ers i with L_i \leq x \leq R_i.

For each k=1,2,\cdots,N, solve the following problem.

• Find the maximum number of kyopro-ers Maroon can make friends with if he holds exactly k dinner parties.

Constraints

• 1 \leq N \leq 10^6
• 1 \leq M \leq 10^6
• 1 \leq L_i \leq R_i \leq N
• All input values are integers.

Sample Input 1

3 3
1 1
1 2
3 3

Sample Output 1

2
3
3

• k=1: If he holds a party on the 1-st day, he can make friends with kyopro-ers 1 and 2.
• k=2: If he holds a party on the 1-st and 3-rd days, he can make friends with kyopro-ers 1, 2, and 3.
• k=3: If he holds a party on the 1-st, 2-nd, and 3-rd days, he can make friends with kyopro-ers 1, 2, and 3.

Sample Input 2

4 4
1 1
2 2
3 3
4 4

Sample Output 2

1
2
3
4

Sample Input 3

3 6
1 1
1 2
1 2
2 3
2 3
3 3

Sample Output 3

4
6
6

Sample Input 4

20 15
15 19
1 8
6 11
3 11
11 17
6 6
16 20
7 11
11 14
2 19
1 3
7 7
6 19
14 15
15 15

Sample Output 4

7
11
12
13
14
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15

Problem Statement

You are given positive integers N and M. Here, N<M.

A sequence of N non-negative integers a=(a_1,a_2,\cdots,a_N) is said to be a good sequence when it satisfies the following condition:

• 0 \leq a_1 \leq a_2 \leq \cdots \leq a_N \leq M.

For a good sequence a, let f(a) be the sequence resulting from sorting (a_1-1,a_2-2,\cdots,a_N-N) in ascending order.

For each k=1,2,\cdots,N, solve the following problem.

• Assume that we have found the k-th element of f(a) for every possible good sequence a. Find the sum, modulo 998244353, of these values.

※ The answer should be between 0 and 998244352 even if the sum is negative.

Constraints

• 1 \leq N < M \leq 10^6
• All input values are integers.

Sample Input 1

2 3

Sample Output 1

998244349
4

Here are all possible a and the corresponding f(a).

• a=(0,0): f(a)=(-2,-1)
• a=(0,1): f(a)=(-1,-1)
• a=(0,2): f(a)=(-1,0)
• a=(0,3): f(a)=(-1,1)
• a=(1,1): f(a)=(-1,0)
• a=(1,2): f(a)=(0,0)
• a=(1,3): f(a)=(0,1)
• a=(2,2): f(a)=(0,1)
• a=(2,3): f(a)=(1,1)
• a=(3,3): f(a)=(1,2)

Thus, the sum of the first elements is -4, and the sum of the second elements is 4.

Sample Input 2

3 4

Sample Output 2

998244329
0
24

Sample Input 3

4 6

Sample Output 3

998244233
35
175
330

Sample Input 4

10 1000000

Sample Output 4

297189103
747015740
88545731
123651717
920498165
977169022
775771117
810877103
152407094
602233731