Problem Statement

For integers l, r, let [l, r] denote the set of all integers from l through r. That is, [l, r] = \lbrace l, l+1, l+2, \ldots, r-1, r\rbrace.

You are given N pairs of integers (L_1, R_1), (L_2, R_2), \ldots, (L_N, R_N). Based on these pairs, consider an undirected graph G defined as follows:

• It has N vertices numbered 1, 2, \ldots, N.
• For all i, j \in [1, N], there is an undirected edge between vertices i and j if and only if the intersection of [L_i, R_i] and [L_j, R_j] is empty.

In addition, for each i = 1, 2, \ldots, N, define the weight of vertex i to be W_i.

You are given Q queries about G. Process these queries in the order they are given. For each i = 1, 2, \ldots, Q, the i-th query is the following:

You are given integers s_i and t_i (both between 1 and N, inclusive) such that s_i \neq t_i. Determine whether there exists a path from vertex s_i to vertex t_i in G. If it exists, print the minimum possible weight of such a path.

Here, the weight of a path from vertex s to vertex t is defined as the sum of the weights of the vertices on that path (including both endpoints s and t).

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq Q \leq 2 \times 10^5
• 1 \leq W_i \leq 10^9
• 1 \leq L_i \leq R_i \leq 2N
• 1 \leq s_i, t_i \leq N
• s_i \neq t_i
• All input values are integers.

Sample Input 1

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

Sample Output 1

11
6
-1

G is a graph with four undirected edges: \lbrace 1, 3\rbrace, \lbrace 2, 3\rbrace, \lbrace 2, 4\rbrace, \lbrace 3, 4\rbrace.

• For the first query, there is a path from vertex 1 to vertex 4 given by 1 \to 3 \to 4. The weight of this path is W_1 + W_3 + W_4 = 5 + 4 + 2 = 11, and this is the minimum possible.
• For the second query, there is a path from vertex 4 to vertex 3 given by 4 \to 3. The weight of this path is W_4 + W_3 = 2 + 4 = 6, and this is the minimum possible.
• For the third query, there is no path from vertex 5 to vertex 2. Hence, print -1.

Sample Input 2

8
44 75 49 4 78 79 12 32
5 13
10 16
6 8
6 15
12 15
5 7
1 15
1 2
5
5 6
3 2
7 5
4 5
5 4

Sample Output 2

157
124
-1
114
114

Problem Statement

You are given a positive integer N and a length-N string s_0s_1\ldots s_{N-1} consisting only of 0 and 1.

Consider a simple undirected graph G with (N+1) vertices numbered 0, 1, 2, \ldots, N, and the following edges:

• For each i = 0, 1, \ldots, N-1, there is an undirected edge between vertices i and (i+1)\bmod N.
• For each i = 0, 1, \ldots, N-1, there is an undirected edge between vertices i and N if and only if s_i = 1.
• There are no other edges.

Furthermore, create a directed graph G' by assigning a direction to each edge of G. That is, for each undirected edge \lbrace u, v \rbrace in G, replace it with either a directed edge (u, v) from u to v or a directed edge (v, u) from v to u.

For each i = 0, 1, \ldots, N, let d_i be the in-degree of vertex i in G'. Print the number, modulo 998244353, of distinct sequences (d_0, d_1, \ldots, d_N) that can be obtained.

Constraints

• 3 \leq N \leq 10^6
• N is an integer.
• Each s_i is 0 or 1.

Sample Input 1

3
010

Sample Output 1

14

G has four undirected edges: \lbrace 0, 1 \rbrace, \lbrace 0, 2 \rbrace, \lbrace 1, 2 \rbrace, \lbrace 1, 3 \rbrace. For example, if we assign directions to each edge as 0 \to 1, 2 \to 0, 2 \to 1, 1 \to 3, then (d_0, d_1, d_2, d_3) = (1, 2, 0, 1) is obtained.

The possible sequences (d_0, d_1, d_2, d_3) are (0, 1, 2, 1), (0, 2, 1, 1), (0, 2, 2, 0), (0, 3, 1, 0), (1, 0, 2, 1), (1, 1, 1, 1), (1, 1, 2, 0), (1, 2, 0, 1), (1, 2, 1, 0), (1, 3, 0, 0), (2, 0, 1, 1), (2, 1, 0, 1), (2, 1, 1, 0), (2, 2, 0, 0), for a total of 14.

Sample Input 2

20
00001100111010100101

Sample Output 2

261339902

Problem Statement

There is a grid of H rows and W columns. Initially, all cells are uncolored.

You can repeat the following procedure any number of times:

• Choose an integer i between 1 and C, inclusive, and choose exactly one cell in the grid.
• Then, color that chosen cell, as well as all cells in the same row as the chosen cell and all cells in the same column as the chosen cell (a total of (H+W-1) cells), with color i. (If any cell is already colored, its color is overwritten with color i.)

Print the number, modulo 998244353, of different grids in which every cell is colored that can be obtained by repeating the procedure above.

Constraints

• 1 \leq H, W \leq 400
• 1 \leq C \leq 10^9
• All input values are integers.

Sample Input 1

2 3 2

Sample Output 1

26

Below, let (i, j) denote the cell at the i-th row from the top and the j-th column from the left. Also, let ., 1, 2 denote an uncolored cell, a cell colored with color 1, a cell colored with color 2, respectively.

From the initial grid in Sample Input 1, if you first choose color 2 and cell (2, 2), the grid becomes:

.2.
222

Then, if you choose color 1 and cell (1, 1), the grid becomes:

111
122

All cells are colored in this grid, so it satisfies the condition in the problem statement. Furthermore, if you then choose color 1 and cell (1, 3), the grid becomes:

111
121

All cells are again colored in this grid, satisfying the condition in the problem statement.

Sample Input 2

3 2 1

Sample Output 2

1

Sample Input 3

229 327 763027379

Sample Output 3

547014653

Problem Statement

You are given two length-N strings A = A_1A_2 \ldots A_N and B = B_1B_2 \ldots B_N, each consisting of 0 and 1.

There are N squares aligned in a row from left to right. For i = 1, 2, \ldots, N, the i-th square from the left is called square i. Initially, square i contains a piece if A_i = 1, and no piece if A_i = 0.

You may repeat the following operation any number of times (possibly zero):

• Choose an integer i between 1 and N, inclusive.
• Move all pieces simultaneously one square closer to square i. That is, for each piece, let square j be its current position and square j' be its new position, and the following holds:
  • if i < j, then j' = j-1;
  • if i > j, then j' = j+1;
  • if i = j, then j' = j.

Determine whether it is possible to reach a configuration satisfying the following condition, and if it is possible, find the minimum number of operations needed to do so:

For every i = 1, 2, \ldots, N, there is at least one piece in square i if and only if B_i = 1.

You are given T independent test cases. Print the answer for each of them.

Constraints

• 1 \leq T \leq 2 \times 10^5
• 1 \leq N \leq 10^6
• T and N are integers.
• A and B are strings of length N, each consisting of 0 and 1.
• There exists i such that A_i = 1.
• There exists i such that B_i = 1.
• The sum of N over all test cases is at most 10^6.

Sample Input 1

3
8
01001101
00001011
3
010
111
20
10100011011110101011
00010001111101100000

Sample Output 1

3
-1
5

The input has three independent test cases.

In the first test case, initially, the sequence of the numbers of pieces in the squares is (0, 1, 0, 0, 1, 1, 0, 1). By performing the operation three times as follows, you can satisfy the condition:

• Choose i = 5. After the operation, the configuration is (0, 0, 1, 0, 2, 0, 1, 0).
• Choose i = 8. After the operation, the configuration is (0, 0, 0, 1, 0, 2, 0, 1).
• Choose i = 8. After the operation, the configuration is (0, 0, 0, 0, 1, 0, 2, 1).

It is impossible to satisfy the condition in fewer than three operations, so the answer is 3.

In the second test case, no matter how you perform the operations, you cannot satisfy the condition, so the answer is -1.