Problem Statement

You are given 3 binary strings S_1, S_2, S_3, each containing exactly N 0's and N 1's.

Find a binary string of length 2N+1, which is a subsequence of all of the strings S_1 + S_1, S_2 + S_2, S_3 + S_3 (s+t denotes the concatenation of strings s and t in order). It's guaranteed that under the constraints above such a string always exists.

Here a string B is a subsequence of a string A if B can be obtained by removing zero or more characters from A and concatenating the remaining characters without changing the order.

You will be given T test cases. Solve each of them.

Constraints

• 1 \le T \le 10^5
• 1\le N \le 10^5
• S_i is a binary string of length 2N consisting of N 0's and N 1's.
• The sum of N over all test cases doesn't exceed 10^5.

Sample Input 1

2
1
01
01
10
2
0101
0011
1100

Sample Output 1

010
11011

In the first case, 010 is a subsequence of 0101, 0101, and 1010.

In the second case, 11011 is a subsequence of 01010101, 00110011, and 11001100.

Problem Statement

You are given a tree with N vertices, where N is odd. The vertices are numbered from 1 through N and edges from 1 through N-1. The edge i connects vertices u_i and v_i and its initial weight is w^1_i.

You can perform the following operation any number of times:

• Choose an edge (u, v) of the tree, and suppose that its weight now is w. For every edge, which is incident to exactly one of u and v, we XOR the weight of that edge with w (if it was w_1, replace it with w_1 \oplus w).

Your goal is to reach the state where each edge i has weight w^2_i. Determine if you can get to the goal by performing the operation above any number of times.

Constraints

• 1 \le N \le 10^5
• N is odd.
• 1\le u_i, v_i \le N
• u_i \neq v_i
• 0\le w^1_i, w^2_i < 2^{30}
• All values in input are integers.
• The input represents a valid tree.

Sample Input 1

3
1 2 1 1
2 3 8 9

Sample Output 1

YES

If you perform the operation on the edge 1, the weight of the edge 2 becomes 8 \oplus 1=9.

Sample Input 2

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

Sample Output 2

NO

Problem Statement

You are given a prime number P, which you don't like.

Let's call an array of integers A_1, A_2, \dots, A_N good, if it is possible to reorder the elements in such a way that no prefix sum is divisible by P (that is, there is no i with 1 \le i \le N and A_1 + A_2 + \dots + A_i \equiv 0 \bmod P after the reordering).

Consider all (P-1)^N arrays of length N with elements from 1 to P-1. How many of them are good?

As this number can be very big, output it modulo 998244353.

Constraints

• 1 \le N \le 5000
• 2 \le P \le 10^8
• P is a prime.

Sample Input 1

2 5

Sample Output 1

12

There are 12 good arrays: [1, 1], [1, 2], [1, 3], [2, 1], [2, 2], [2, 4], [3, 1], [3, 3], [3, 4], [4, 2], [4, 3], [4, 4].

Sample Input 2

4 3

Sample Output 2

8

There are 8 good arrays: [1, 1, 1, 2], [1, 1, 2, 1], [1, 2, 1, 1], [2, 1, 1, 1], [2, 2, 2, 1], [2, 2, 1, 2], [2, 1, 2, 2], [1, 2, 2, 2].

Sample Input 3

5000 99999989

Sample Output 3

51699346

Sample Input 4

2021 307

Sample Output 4

644635349

Problem Statement

You are given a permutation P_1, P_2, \dots, P_N of integers from 1 to N. Is it possible to split it into 2 subsequences, which have equal length of the Longest Increasing Subsequence?

Formally speaking, your goal is to get two integer sequences a and b such that:

• Both a and b are subsequences of P.
• Each integer i=1,2,\cdots,N appears in exactly one of a and b.
• (The length of a longest increasing subsequence of a) = (The length of a longest increasing subsequence of b)

Determine if the objective is achievable.

You will be given T test cases. Solve each of them.

Constraints

• 1 \le T \le 2 \cdot 10^5
• 1 \le N \le 2 \cdot 10^5
• P_1, P_2, \dots, P_N is a permutation of integers from 1 to N.
• The sum of N over all test cases doesn't exceed 2 \cdot 10^5.

Sample Input 1

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

Sample Output 1

NO
YES
NO
YES
NO

[1, 3, 5, 2, 4] can be split into [1, 5] and [3, 2, 4], both have LIS of length 2.

It can be shown that there is no way to split [2, 3, 4, 5, 6, 1] into 2 subsequences with an equal length of LIS.

Problem Statement

A string, consisting of letters A, B, and C, is called good, if every two consecutive letters are different. For example, strings ABABAB and ABC are good, while ABBA and AABBCC aren't.

You are given two good strings S and T of length N. In one operation, you can choose any letter of S, and change it to another letter among A, B, and C, so that S remains good.

What's the smallest number of operations needed to transform S into T? We can prove that it can always be done in a finite number of operations.

Constraints

• 1\le N \le 5\cdot 10^5
• S is a good string of length N consisting of A, B, and C
• T is a good string of length N consisting of A, B, and C

Sample Input 1

4
CABC
CBAC

Sample Output 1

6

Here is one possible sequence of operations of length 6:

CABC \to BABC \to BCBC \to BCAC \to ACAC \to ABAC \to CBAC

It can be shown that 6 operations are necessary for this case.

Sample Input 2

10
ABABABABAB
BABABABABA

Sample Output 2

15

Problem Statement

You are given a tree with N vertices. The vertices are numbered from 1 to N, and the i-th edge connects vertices u_i and v_i.

Initially, on each vertex of the tree is written number 1.

In one operation, you can do the following:

• Choose any vertex v of the tree. Let X be the XOR of the values written in the neighbors of v. Then, if the number written on v is a_v, replace it by (a_v\ \mathrm{XOR}\ X).

You can perform this operation any finite (maybe zero) number of times. How many configurations can you achieve? As this number can be large, output it modulo 998244353.

Two configurations are called different if there exists a vertex v, such that the numbers written in v in these configurations are different.

Constraints

• 3 \le N \le 2\cdot 10^5
• 1\le u_i, v_i \le N
• u_i \neq v_i
• The input represents a valid tree.

Sample Input 1

4
1 2
2 3
3 4

Sample Output 1

10

We can get the following configurations (abcd means vertices 1,2,3,4 have a,b,c,d written on them): 1111, 1110, 1100, 1000, 0111, 0110, 0100, 0011, 0010, 0001.

Sample Input 2

5
1 2
1 3
1 4
1 5

Sample Output 2

24

Sample Input 3

6
1 3
2 3
3 4
4 5
4 6

Sample Output 3

40

Sample Input 4

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

Sample Output 4

255