Problem Statement

You are given strings A and B of length N consisting of 0 and 1. Let A_i denote the i-th character of A.

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

• Choose an integer i\ (2 \leq i \leq N-1) satisfying A_{i-1} = A_{i+1}, and flip A_i (change 1 to 0 or 0 to 1).

Determine whether you can make A equal to B by repeating the operation, and if so, find the minimum number of operations required.

You are given T test cases; solve each of them.

Constraints

• 1 \leq T \leq 2 \times 10^5
• 3 \leq N \leq 10^6
• A and B are strings of length N consisting of 0 and 1.
• T and N are integers.
• The sum of N over all test cases is at most 10^6.

Sample Input 1

4
4
0001
0111
6
101101
011100
5
10101
10101
10
0101000101
0011100111

Sample Output 1

2
-1
0
6

For the first test case, you can make A equal to B in two operations as follows.

1. Choose i = 2. A becomes 0101.
2. Choose i = 3. A becomes 0111.

For the second test case, it is impossible to make A equal to B no matter how you operate.

Problem Statement

You are given a positive integer N and a sequence of integers A = (A_1, A_2, \ldots, A_N). Each A_i satisfies -1 \leq A_i \leq N-1, and for 1 \leq i < j \leq N, if A_i \neq -1 and A_j \neq -1, then A_i \neq A_j.

Answer the following query Q times.

• You are given integers l, r\ (1 \leq l \leq r \leq N).
  Find the sum, modulo 998244353, of \mathrm{mex}(\lbrace P_l, P_{l+1}, \ldots, P_r \rbrace) over all permutations P = (P_1, P_2, \ldots, P_N) of (0, 1, \ldots, N-1) satisfying A_i \neq -1 \implies P_i = A_i.

Constraints

• 1 \leq N \leq 5000
• 1 \leq Q \leq 5 \times 10^5
• -1 \leq A_i \leq N-1
• For 1 \leq i < j \leq N, if A_i \neq -1 and A_j \neq -1, then A_i \neq A_j.
• For each query, 1 \leq l \leq r \leq N.
• All input values are integers.

Sample Input 1

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

Sample Output 1

2
0
3
6

The permutations P satisfying A_i \neq -1 \implies P_i = A_i are (0, 1, 2) and (0, 2, 1). Thus, the answer to each query is computed as follows.

• The answer to the first query is \mathrm{mex}(\lbrace 0 \rbrace) + \mathrm{mex}(\lbrace 0 \rbrace) = 1 + 1 = 2.
• The answer to the second query is \mathrm{mex}(\lbrace 1 \rbrace) + \mathrm{mex}(\lbrace 2 \rbrace) = 0 + 0 = 0.
• The answer to the third query is \mathrm{mex}(\lbrace 0, 1 \rbrace) + \mathrm{mex}(\lbrace 0, 2 \rbrace) = 2 + 1 = 3.
• The answer to the fourth query is \mathrm{mex}(\lbrace 0, 1, 2 \rbrace) + \mathrm{mex}(\lbrace 0, 2, 1 \rbrace) = 3 + 3 = 6.

Sample Input 2

5 3
-1 2 -1 -1 1
1 4
3 5
1 5

Sample Output 2

6
8
30

Sample Input 3

15 1
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
1 15

Sample Output 3

612227903

Problem Statement

You are given a sequence of non-negative integers A = (A_1, A_2, \ldots, A_N) of length N.

Find the number of pairs of integers (l, r)\ (1 \leq l \leq r \leq N) such that 2^{A_l} + 2^{A_{l+1}} + \dots + 2^{A_r} is a power of 2. Here, a power of 2 is a number expressible as 2^k for some non-negative integer k.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq A_i \leq 2 \times 10^5
• All input values are integers.

Sample Input 1

4
0 1 0 2

Sample Output 1

6

The pairs (l, r) satisfying the condition are (1,1), (1,3), (1,4), (2,2), (3,3), (4,4), totaling six pairs.

Sample Input 2

4
100 100 100 100

Sample Output 2

8

Sample Input 3

10
3 2 2 3 2 4 1 1 0 0

Sample Output 3

19

Problem Statement

You are given positive integers N, B, C, D.

For a non-negative integer k, define the integer a_k as the product of all terms of an arithmetic sequence with first term Bk + C, common difference D, and N terms; that is, a_k = (Bk+C)(Bk+C+D)(Bk+C+2D)\dots(Bk+C+(N-1)D).

Find the greatest common divisor, modulo 998244353, of a_0, a_1, a_2, \ldots, a_N.

You are given T test cases; solve each of them.

Constraints

• 1 \leq T \leq 10^5
• 1 \leq N, B, C, D \leq 10^6
• All input values are integers.

Sample Input 1

3
3 1 1 1
4 2 2 6
2026 3 22 216

Sample Output 1

6
128
114347907

For the first test case, (a_0, a_1, a_2, a_3) = (1 \times 2 \times 3, 2 \times 3 \times 4, 3 \times 4 \times 5, 4 \times 5 \times 6) = (6, 24, 60, 120), and their greatest common divisor is 6.

Problem Statement

You are given a permutation P = (P_1, P_2, \ldots, P_N) of (1, 2, \ldots, N) and a set of pairs of integers S = \lbrace (x_1, y_1), (x_2, y_2), \ldots, (x_M, y_M) \rbrace.

You can perform the following two types of operations any number of times in any order.

• Choose (l, r)\ (1 \leq l < r \leq N) such that (P_l, P_r) \in S or (P_r, P_l) \in S, and swap the l-th and r-th elements of P. That is, replace P with (P_1, \ldots, P_{l-1}, P_r, P_{l+1}, \ldots, P_{r-1}, P_l, P_{r+1}, \ldots, P_N).
• Choose (l, r)\ (1 \leq l < r \leq N) such that (P_l, P_r) \in S or (P_r, P_l) \in S, and reverse the elements from the l-th to the r-th of P. That is, replace P with (P_1, \ldots, P_{l-1}, P_r, P_{r-1}, \ldots, P_{l+1}, P_l, P_{r+1}, \ldots, P_N).

Find the lexicographically smallest permutation obtainable by the operations.

You are given T test cases; solve each of them.

Constraints

• 1 \leq T \leq 3 \times 10^4
• 2 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 2 \times 10^5
• P is a permutation of (1, 2, \ldots, N).
• 1 \leq x_i < y_i \leq N
• (x_i, y_i) \neq (x_j, y_j) if i \neq j.
• The sum of N over all test cases is at most 2 \times 10^5.
• The sum of M over all test cases is at most 2 \times 10^5.
• All input values are integers.

Sample Input 1

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

Sample Output 1

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

For the first test case, you can obtain P = (1, 2, 5, 3, 4, 6) by performing the operations as follows.

• Initially, P = (1, 3, 2, 5, 4, 6).
• Reverse the elements from the first to the fifth with (l, r) = (1, 5)\ ((P_l, P_r) = (1, 4) \in S). P becomes (4, 5, 2, 3, 1, 6).
• Swap the second and third elements with (l, r) = (2, 3)\ ((P_r, P_l) = (2, 5) \in S). P becomes (4, 2, 5, 3, 1, 6).
• Swap the first and fifth elements with (l, r) = (1, 5)\ ((P_r, P_l) = (1, 4) \in S). P becomes (1, 2, 5, 3, 4, 6).

This is the lexicographically smallest permutation obtainable by the operations.