Problem Statement

N teams are participating in a team shogi tournament. Each team consists of M players. This tournament is a round-robin format, with a total of \frac{N(N-1)}{2} matches played. In each match, the M players from each team are randomly matched against each other, and one player always wins while the other loses. After all matches are played, each player will have played exactly N-1 games, and players who won all their games will be awarded the perfect record prize. Find the maximum possible number of players who can be awarded the perfect record prize.

Solve T test cases for each input file.

Constraints

• 1 \leq T \leq 2 \times 10^5
• 2 \leq N \leq 10^9
• 1 \leq M \leq 10^9
• All input values are integers.

Sample Input 1

2
3 3
5 1

Sample Output 1

4
1

For the first test case, suppose the following 3 teams participate in the tournament:
Team T: players T_1,T_2,T_3
Team W: players W_1,W_2,W_3
Team R: players R_1,R_2,R_3
and suppose the following results occur:

• Match between Team T and Team W
  • Game between T_1 and W_1: W_1 wins
  • Game between T_2 and W_2: W_2 wins
  • Game between T_3 and W_3: T_3 wins

• Match between Team T and Team R
  • Game between T_1 and R_3: T_1 wins
  • Game between T_2 and R_1: R_1 wins
  • Game between T_3 and R_2: T_3 wins

• Match between Team W and Team R
  • Game between W_1 and R_3: R_3 wins
  • Game between W_2 and R_2: R_2 wins
  • Game between W_3 and R_1: W_3 wins

Then, only player T_3 from Team T is awarded the perfect record prize.
In this case, the maximum possible number of players who can be awarded the perfect record prize is 4.

Problem Statement

You are given length-N integer sequences A=(A_1,A_2,\dots,A_N) and B=(B_1,B_2,\dots,B_N), each consisting of 0 and 1. Let A[i,j] denote the consecutive subsequence of A from the i-th through the j-th element. If i>j, then A[i,j] is a length-0 sequence. You can perform the following operation on A any number of times:

• Choose four integers a,b,c,d that satisfy the following two conditions:
  • 1 \leq a \leq b < c \leq d \leq N
  • \sum_{i=a}^{b}{A_i}=\sum_{i=c}^{d}{A_i}
• Swap A[a,b] and A[c,d]. More precisely, replace A with the sequence formed by concatenating A[1,a-1], A[c,d], A[b+1,c-1], A[a,b], A[d+1,N] in this order.

Determine whether A can be made to match B.

Solve T test cases for each input file.

Constraints

• 1 \leq T \leq 10^5
• 2 \leq N \leq 2 \times 10^5
• 0 \leq A_i \leq 1
• 0 \leq B_i \leq 1
• The sum of N over all test cases is at most 2\times 10^5.
• All input values are integers.

Sample Input 1

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

Sample Output 1

Yes
No
Yes

In the first test case, A is initially (1,1,1,0,0,1).
By choosing (a,b,c,d)=(1,2,3,6) and performing the operation, A becomes (1,0,0,1,1,1).
Next, by choosing (a,b,c,d)=(1,2,3,4) and performing the operation, A becomes (0,1,1,0,1,1), which matches B.
In the second test case, A cannot be made to match B.
In the third test case, A already matches B from the beginning.

Problem Statement

Rooms are arranged in a grid with H rows and W columns. There are walls between adjacent rooms that share an edge.
When you are in room A and room B is adjacent to room A in one of the four directions (up, down, left, right), and the wall between room A and room B has been demolished, you can move from room A to room B.

Find the total number, modulo 998244353, of ways to choose K walls such that the following condition is satisfied.

• When all chosen walls are demolished, it is possible to move from the top-left room to the bottom-right room by passing through some rooms.

Solve T test cases for each input file.

Constraints

• 1 \leq T \leq 2 \times 10^5
• 2 \leq H \leq 2 \times 10^5
• 2 \leq W \leq 2 \times 10^5
• \boldsymbol{0 \leq K \leq H+W}
• All input values are integers.

Sample Input 1

6
2 2 1
2 2 3
2 2 2
2 2 4
200000 200000 400000
2 203 203

Sample Output 1

0
4
2
1
387815582
203

In the first case, demolishing any single wall does not allow movement from the top-left room to the bottom-right room.
In the second case, choosing and demolishing any three walls out of the four available walls allows movement from the top-left room to the bottom-right room.

Problem Statement

There is an integer sequence A=(A_1,A_2,\dots,A_N) of length N consisting of 0 and 1. You are given Q queries. The q-th query is as follows:

• An integer i_q between 1 and N is given. Change A_{i_q} to 1 if it is 0, and to 0 if it is 1.

After processing each query, find the answer to the following problem:

Consider sequences B=(B_1,B_2,\dots,B_{|B|}) consisting of 0 and 1 that satisfy the following condition:

• By performing the following operation any number of times on B, it can be made to match sequence A:
  • Choose an integer i between 1 and |B|-1, inclusive.
  • Insert B_i\oplus B_{i+1} between B_i and B_{i+1}.

It can be proved that there always exists a B that satisfies the condition. Find the minimum possible value of |B|.

Constraints

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

Sample Input 1

3
0 0 0
2
1
2

Sample Output 1

3
2

When A=(1,0,0), |B| is minimized by B=(1,0,0). When A=(1,1,0), |B| is minimized by B=(1,0).

Sample Input 2

8
0 1 0 0 1 1 1 0
3
1
4
1

Sample Output 2

5
2
3

Problem Statement

There is a grid with H rows and W columns, where the cell at the i-th row from the top and j-th column from the left is denoted as (i,j). The grid has a hole only in cell (r,c). We will tile all cells without a hole using several tiles. You are given non-negative integers N and M such that H \times W=L \times (N+M)+1. A tile of 1 row and L columns is called a horizontal tile, and a tile of L rows and 1 column is called a vertical tile. Determine whether there exists a way to tile using exactly N horizontal tiles and M vertical tiles without rotation, and also show one such way if it exists. For details on the output format and more precise conditions, check the output section.

Solve T test cases for each input file.

Constraints

• 1 \leq T \leq 5
• 1 \leq H \leq 1000
• 1 \leq W \leq 1000
• 2 \leq H \times W
• 2 \leq L \leq 1000
• 0 \leq N
• 0 \leq M
• 1 \leq r \leq H
• 1 \leq c \leq W
• H \times W=L \times (N+M)+1
• The sum of N+M over all test cases is at most 6\times 10^5.
• All input values are integers.

Sample Input 1

3
1 3 2 1 0 1 1
1 3 2 1 0 1 2
3 3 2 1 3 1 1

Sample Output 1

Yes
1 2
No
Yes
3 2
2 1
1 2
1 3

In the third test case, there is a hole in the top-left cell. It can be tiled as follows:

  ┌─┬─┐
┌─┤ │ │
│ ├─┴─┤
└─┴───┘