Problem Statement

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

The following operation may be performed between 0 and N times (inclusive).

• Choose an integer x (1 \leq x \leq 2N-1). Swap the values of P_x and P_{x+1}.

Present a sequence of operations that make P satisfy the following conditions.

• P_i<P_{i+1} for each i=1,3,5,\cdots,2N-1;
• P_i>P_{i+1} for each i=2,4,6,\cdots,2N-2.

It can be proved that such a sequence of operations always exists.

Constraints

• 1 \leq N \leq 10^5
• (P_1,P_2,\cdots,P_{2N}) is a permutation of (1,2,\cdots,{2N}).
• All values in input are integers.

Sample Input 1

2
4 3 2 1

Sample Output 1

2
1 3

These operations make P=(3,4,1,2), which satisfies the conditions.

Sample Input 2

1
1 2

Sample Output 2

0

Problem Statement

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

You may perform the following operation zero or more times.

• Choose an integer i (1 \leq i \leq N-1). Let v=\max(P_i,P_{i+1}) and replace the values of P_i and P_{i+1} with v.

How many sequences are there that P can be after your operations? Find the count modulo 998244353.

Constraints

• 2 \leq N \leq 5000
• (P_1,P_2,\cdots,P_N) is a permutation of (1,2,\cdots,N).
• All values in input are integers.

Sample Input 1

3
1 3 2

Sample Output 1

4

The four sequences that P can become are (1,3,2), (3,3,2), (1,3,3), and (3,3,3).

Sample Input 2

4
2 1 3 4

Sample Output 2

11

Sample Input 3

10
4 9 6 3 8 10 1 2 7 5

Sample Output 3

855

Problem Statement

There are N vertices on a circumference. The vertices are numbered 1 to N in clockwise order, and Vertex i has an integer A_i written on it, where A_i is 1, 2, 3, or 4. Here, A contains each of 1, 2, 3, and 4 at least once.

Consider making a tree by adding N-1 edges connecting these N vertices. Here, the following conditions must be satisfied.

• If Vertices x and y are directly connected by an edge, |A_x-A_y|=1.

• When the edges are drawn as segments, no two of them intersect except at an endpoint.

For instance, the figure below shows a tree that satisfies the conditions:

Determine whether it is possible to construct a tree that satisfies the conditions.

Solve T test cases for each input file.

Constraints

• 1 \leq T \leq 75000
• 4 \leq N \leq 300000
• 1 \leq A_i \leq 4
• A contains each of 1, 2, 3, and 4 at least once.
• The sum of N in one input file does not exceed 300000.
• All values in input are integers.

Sample Input 1

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

Sample Output 1

Yes
Yes
No

Sample Input 2

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

Sample Output 2

Yes
Yes
No

The first test case corresponds to the figure in the Problem Statement.

Problem Statement

You are given integers A, B, and C. How many strings S consisting of A, B, and C satisfy all of the following conditions? Find the count modulo 998244353.

• The number of occurrences of A, B, and C in S are A, B, and C, respectively.
• S contains none of ABC, BCA, and CAB as a (contiguous) substring.

Constraints

• 1 \leq A,B,C \leq 10^6
• All values in input are integers.

Sample Input 1

1 1 1

Sample Output 1

3

The three strings that satisfy the conditions are ACB, CBA, and BAC.

Sample Input 2

2 2 2

Sample Output 2

42

Sample Input 3

96 11 46

Sample Output 3

818015722

Sample Input 4

125132 102271 152064

Sample Output 4

128086069

Problem Statement

In this problem, a "permutation" always means a permutation of (1,2,\cdots,N).

For two permutations p and q, let us define the distance between them, d(p,q), as follows.

• Consider making p equal q by repeatedly swapping two adjacent terms in p. Let d(p,q) be the minimum number of swaps required here.

Additionally, for a permutation x, let us define another permutation f(x) as follows.

• Let y=(1,2,\cdots,N). Consider permutations z such that d(x,z) \leq d(y,z). Let f(x) be the lexicographically smallest of those permutations.

For example, when x=(2,3,1), the permutations z such that d(x,z) \leq d(y,z) are z=(2,1,3),(2,3,1),(3,1,2),(3,2,1). The lexicographically smallest of them is (2,1,3), so we have f(x)=(2,1,3).

You are given a permutation A=(A_1,A_2,\cdots,A_N). Determine whether there is a permutation x such that f(x)=A.

Solve T test cases for each input file.

Constraints

• 1 \leq T \leq 150000
• 2 \leq N \leq 300000
• (A_1,A_2,\cdots,A_N) is a permutation of (1,2,\cdots,N).
• The sum of N in one input file does not exceed 300000.
• All values in input are integers.

Sample Input 1

2
2
1 2
2
2 1

Sample Output 1

Yes
Yes

For instance, when A=(2,1), one can let x=(2,1) to satisfy f(x)=A.

Sample Input 2

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

Sample Output 2

Yes
Yes
Yes
Yes
No
No

For instance, when A=(2,3,1), one can let x=(3,2,1) to satisfy f(x)=A.

Sample Input 3

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

Sample Output 3

Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No

Problem Statement

For an undirected tree t, let us define a rational number f(t) as follows.

• Let n be the number of vertices in t.
• If n=1: Let f(t)=1.
• If n \geq 2:
  • For an edge e in t, we denote by t_x(e) and t_y(e) the two trees that result from deleting e from t (in arbitrary order).
  • Let f(t)=(\sum_{e \in t} f(t_x(e)) \times f(t_y(e)))/n.

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

Find the value f(T) \text{mod }{998244353}.

Constraints

• 2 \leq N \leq 5000
• 1 \leq A_i,B_i \leq N
• The given graph is a tree.

Sample Input 1

2
1 2

Sample Output 1

499122177

We have f(T)=1/2.

Sample Input 2

3
1 2
2 3

Sample Output 2

332748118

We have f(T)=1/3.

Sample Input 3

4
1 2
2 3
3 4

Sample Output 3

103983787

Sample Input 4

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

Sample Output 4

462781191