Problem Statement

There is a grid with N rows and N columns. Let (r,c) denote the cell at the r-th row from the top and c-th column from the left. Each cell is colored black or white. Cell (r,c) is colored black when S_{r,c} is #, and white when S_{r,c} is ..

You are given Q questions about this grid, so answer each of them. In the i-th question (1\le i\le Q), integers U_i,D_i,L_i,R_i are given, so find the answer to the following question.

• After coloring all cells that do not satisfy U_i \le r \le D_i and L_i \le c \le R_i black, find the maximum number of times you can perform the following operation.
  • Choose a pair of integers (r,c) such that cells (r,c),(r,c+1),(r+1,c),(r+1,c+1) are all colored white, and color one of these four cells black.

Solve each question independently. In other words, the color of each cell is reset to the initial state for each question.

Constraints

• 2\le N\le 500
• 1\le Q\le 2\times 10^5
• S_{r,c} is . or #.
• 1\le U_i < D_i \le N
• 1\le L_i < R_i \le N
• N,Q,U_i,D_i,L_i,R_i are all integers.

Sample Input 1

5 4
..#.#
.....
#....
...#.
.#...
1 3 1 3
3 5 3 5
2 3 1 4
1 5 1 5

Sample Output 1

2
0
2
5

Consider the first question.

After coloring all cells that do not satisfy 1\le r\le 3 and 1\le c\le 3 black, the grid becomes as follows.

..###
...##
#..##
#####
#####

You can perform the operation twice on this grid as follows.

• Choose (r,c)=(1,1). Among cells (1,1),(1,2),(2,1),(2,2), choose cell (1,2) and color it black.
• Choose (r,c)=(2,2). Among cells (2,2),(2,3),(3,2),(3,3), choose cell (2,2) and color it black.

You cannot perform the operation more than twice, so output 2 on the first line.

Sample Input 2

7 6
#.#....
.....#.
.......
.#..#.#
#....#.
.......
....##.
1 3 2 7
4 6 1 6
6 7 2 7
3 5 4 6
1 6 2 4
1 7 1 7

Sample Output 2

4
4
2
0
6
13

Problem Statement

There is a complete graph with N vertices numbered 1 to N. Each edge is colored black or white. For i=1,2,\ldots,M, the edge connecting vertices U_i and V_i is colored black, and all other edges are colored white.

You can perform the following operation zero or more times.

• Choose a triple of integers (a,b,c) satisfying 1\le a < b < c \le N, and repaint each of the following three edges: white to black, black to white.
  • The edge connecting vertices a and b
  • The edge connecting vertices b and c
  • The edge connecting vertices a and c

Find the maximum number of edges that can be colored black when you perform operations appropriately.

Constraints

• 3\le N\le 2\times 10^5
• \displaystyle 0\le M\le 2\times 10^5
• 1\le U_i < V_i \le N
• (U_i , V_i) \neq (U_j , V_j) (i \neq j)
• All input values are integers.

Sample Input 1

4 1
1 2

Sample Output 1

5

By performing two operations as follows, you can make the number of black edges 5.

• Choose (a,b,c)=(1,3,4). Then, we have the following four black edges.
  • The edge connecting vertices 1 and 2
  • The edge connecting vertices 1 and 3
  • The edge connecting vertices 1 and 4
  • The edge connecting vertices 3 and 4
• Choose (a,b,c)=(2,3,4). Then, we have the following five black edges.
  • The edge connecting vertices 1 and 2
  • The edge connecting vertices 1 and 3
  • The edge connecting vertices 1 and 4
  • The edge connecting vertices 2 and 3
  • The edge connecting vertices 2 and 4

You cannot make the number of black edges more than 5, so output 5.

Sample Input 2

7 3
1 2
2 3
3 6

Sample Output 2

20

Sample Input 3

123123 0

Sample Output 3

7579575003

Be careful about overflow.

Problem Statement

There are N people on a number line.

Person i (1\le i\le N) is initially at coordinate S_i, and wants to eventually move to coordinate T_i. It is guaranteed that S_1,S_2,\ldots,S_N,T_1,T_2,\ldots,T_N are all distinct.

You fix one permutation P=(P_1,P_2,\ldots,P_N) of (1,2,\ldots,N) and perform N operations in order. In the i-th operation (1\le i\le N), you move person P_i from coordinate S_{P_i} to coordinate T_{P_i} along the shortest path on the number line. However, if there is another person on the movement path, a fight occurs.

Determine if there exists a P such that no fight occurs, and if it exists, find one.

Constraints

• 1\le N\le 2\times 10^5
• 1\le S_i, T_i \le 10^9
• S_1,S_2,\ldots,S_N,T_1,T_2,\ldots,T_N are all distinct.
• All input values are integers.

Sample Input 1

4
1 3
2 4
7 5
8 10

Sample Output 1

Yes
3 2 1 4

If P=(3,2,1,4), then the N operations proceed as follows.

• 1st operation: Move person 3 from coordinate 7 to coordinate 5. The other three people are at coordinates 1,2,8, so no fight occurs.
• 2nd operation: Move person 2 from coordinate 2 to coordinate 4. The other three people are at coordinates 1,5,8, so no fight occurs.
• 3rd operation: Move person 1 from coordinate 1 to coordinate 3. The other three people are at coordinates 4,5,8, so no fight occurs.
• 4th operation: Move person 4 from coordinate 8 to coordinate 10. The other three people are at coordinates 3,4,5, so no fight occurs.

Therefore, outputting P=(3,2,1,4) will be accepted.

Other acceptable outputs include P=(4,3,2,1),(2,1,3,4).

Sample Input 2

2
1 3
4 2

Sample Output 2

No

There is no P such that no fight occurs. Therefore, output No.

Sample Input 3

5
19 17
1 10
9 14
3 11
8 13

Sample Output 3

Yes
3 5 1 4 2

Problem Statement

You are given a rooted tree with N vertices numbered from 1 to N. Vertex 1 is the root, and the parent of vertex i (2 \le i \le N) is vertex p_i (1\le p_i < i). Initially, all vertices are colored white.

You can perform the following sequence of operations zero or more times.

• Choose a pair of integers (u,v) that satisfies all of the following conditions.
  • 1\le u < v \le N
  • Both vertices u and v are colored white.
  • u is not an ancestor of v.
• Color vertices u and v black.

Here, "u is not an ancestor of v" means that you cannot reach vertex u from vertex v no matter how many times you perform the operation of moving to the parent of the current vertex.

Find the maximum number of operations you can perform when you perform operations in an appropriate order.

You are given T test cases, so find the answer for each of them.

Constraints

• 1\le T\le 5\times 10^4
• 2\le N\le 5\times 10^5
• 1\le p_i < i
• The sum of N over all test cases is at most 5\times 10^5.
• All input values are integers.

Sample Input 1

4
6
1 2 2 2 5
7
1 2 3 4 5 6
7
1 2 3 4 2 4
12
1 1 2 2 2 4 4 4 7 7 7

Sample Output 1

2
0
2
5

Consider the first test case.

You can perform two operations as follows.

• Choose (u,v)=(3,5). Color vertices 3 and 5 black.
• Choose (u,v)=(4,6). Color vertices 4 and 6 black.

You cannot perform more than two operations, so output 2 on the first line.

Problem Statement

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

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

• Find the product, modulo 998244353, of A_i for all integers i between 1 and k, inclusive, such that the bitwise \mathrm{OR} operation of A_i and A_k equals A_k.

Constraints

• 1\le N\le 4\times 10^5
• 0\le A_i < 2^{20}
• All input values are integers.

Sample Input 1

4
1 2 3 5

Sample Output 1

1
2
6
5

• When k=1: For i=1, the bitwise \mathrm{OR} operation of A_i and A_k is 1. Therefore, the answer for the case k=1 is A_1=1.
• When k=2: For i=1,2, the bitwise \mathrm{OR} operation of A_i and A_k is 3,2, respectively. Therefore, the answer for the case k=2 is A_2=2.
• When k=3: For i=1,2,3, the bitwise \mathrm{OR} operation of A_i and A_k is all 3. Therefore, the answer for the case k=3 is A_1\times A_2\times A_3=6.
• When k=4: For i=1,2,3,4, the bitwise \mathrm{OR} operation of A_i and A_k is 5,7,7,5, respectively. Therefore, the answer for the case k=4 is A_1\times A_4=5.

Sample Input 2

9
3 1 4 1 5 9 2 6 5

Sample Output 2

3
1
4
1
20
9
2
48
100

Sample Input 3

12
437926 528156 284664 1038330 692060 720863 602077 1027766 868190 532252 982711 876446

Sample Output 3

437926
528156
284664
94842632
158208162
985930968
548875758
875494466
345599613
605424119
111381243
768586512