Problem Statement

There are N meetings numbered 1,2,\dots,N. Meeting i starts at time S_i and ends at time T_i.

Takahashi and Aoki are going to assign exactly one of themselves to each meeting as the person in charge. The same person cannot be in charge of two meetings that overlap for a positive length of time. More formally, the same person can be in charge of meetings i and j only if T_i \le S_j or T_j \le S_i.

Find the number, modulo 998244353, of ways to assign the people in charge that satisfy the conditions.

Constraints

• 1 \le N \le 3 \times 10^5
• 1 \le S_i < T_i \le 2N
• S_1,T_1,S_2,T_2,\dots,S_N,T_N are all different.
• All input values are integers.

Sample Input 1

3
1 3
2 4
5 6

Sample Output 1

4

The following four assignments satisfy the conditions:

• Takahashi is in charge of meetings 1,3, and Aoki is in charge of meeting 2.
• Takahashi is in charge of meeting 1, and Aoki is in charge of meetings 2,3.
• Takahashi is in charge of meetings 2,3, and Aoki is in charge of meeting 1.
• Takahashi is in charge of meeting 2, and Aoki is in charge of meetings 1,3.

Sample Input 2

3
1 4
2 5
3 6

Sample Output 2

0

Zero assignments satisfy the conditions.

Problem Statement

There are N bags numbered 1,2,\dots,N. Also, for each i=0,1,\dots,M-1, there are A_i packages of weight 2^i. There are A_0+A_1+\dots+A_{M-1} packages in total.

Every package is put into exactly one of the bags. Some bags may remain empty.

For each bag, the sum of the weights of all packages in that bag is called the weight of the bag.

Find the minimum possible value of the maximum of the weights of the N bags.

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

Constraints

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

Sample Input 1

4
2 3
3 2 1
1000000 1
0
1 40
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
188075 10
858153 791486 630853 157728 813993 50047 286602 459270 597406 907405

Sample Output 1

6
0
549755813888
3805

In the first test case, there are 3,2,1 packages of weight 1,2,4, respectively.

For example, let the weights of the packages put into bags 1,2 be (4,1,1),(2,2,1), respectively. Then, the weights of bags 1,2 are 6,5, respectively, and the maximum of these is 6.

It is impossible to make the maximum of the weights of the bags 5 or less.

Problem Statement

There is a grid with H rows and W columns. Let (i,j) denote the cell at the i-th row from the top and the j-th column from the left. Initially, all cells are white.

You may perform the following operation any number of times.

• Choose integers r,c,s satisfying all of the following conditions, and paint the cells (r,c),(r+s,c),(r,c+s),(r+s,c+s) black.

  • 1\le r<r+s\le H
  • 1\le c<c+s\le W
  • The cells (r,c),(r+s,c),(r,c+s),(r+s,c+s) are all white.

Find the maximum number of operations you can perform, and output one sequence of operations that achieves that maximum.

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

Constraints

• 1\le T\le 500
• 2\le H,W\le 500
• The sum of HW over all test cases is at most 250000.
• All input values are integers.

Sample Input 1

2
5 6
2 2

Sample Output 1

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

For the first test case, performing the six output operations paints the following cells black. The digit i represents a cell painted black by the i-th operation, and . represents a cell that is never painted.

135135
66....
664242
135135
..4242

There are other outputs that will be accepted.

Problem Statement

This is an interactive problem (in which your program interacts with the judge via input and output).

There are five queues numbered 1 through 5. Initially, all queues are empty.

The judge gives you the following two types of queries, Q times each, for a total of 2Q times.

• push query: The judge gives you an integer X, which is appended to the back of queue 1. The integers X given in the push queries are all distinct. Then, you may perform the following move operation zero or more times.
  • move operation: Choose integers i,j satisfying 1 \le i,j \le 5, remove the value at the front of queue i, and append it to the back of queue j. Here, you cannot choose an empty queue as i. It is not required that i\ne j.
• pop query: The judge gives this query only when at least one queue is non-empty. You choose an integer i satisfying 1 \le i \le 5. At this point, queue i must be non-empty, and the value at its front must be the minimum among all the values currently contained in the five queues. Then, the judge removes the value at the front of queue i.

You may perform the move operation at most 10^5 times in total. Create a program that correctly responds to all queries.

Constraints

• 1 \le Q \le 5000
• 1 \le X \le 10^9
• The values X appended in the push queries are all distinct.
• The push query and the pop query are each given Q times.
• At the time each pop query is given, at least one queue is non-empty.
• All input values are integers.

Interaction

This problem is interactive.

First, the judge gives a positive integer Q in the following format:

Q

Then, perform the following interaction 2Q times. In each round, the judge first gives a push query or a pop query.

A push query is given in the following format:

1 X

A pop query is given in the following format:

2

(If your response to the previous query was invalid, -1 will be given from Standard Input instead of a query. In this case, immediately terminate your program normally. However, if your first invalid output is your response to the 2Q-th query, no further input will be given after that.)

If a push query is given, let k be the number of move operations you perform, and let i_r,j_r be the queue numbers chosen in the r-th move operation; output k+1 lines in the following format. Be sure to add a newline at the end of the output.

k
i_1 j_1
i_2 j_2
\vdots
i_k j_k

If a pop query is given, output the number i of the queue from which to remove the front value, in the following format. Be sure to add a newline at the end of the output.

i

Notes

• Each time you output a response to a query, flush Standard Output after adding a newline at the end. Otherwise, the judge result may be TLE.
• If you receive -1 as input from the judge, immediately terminate your program normally. If you do so, the judge result will be WA; otherwise, the judge result is indeterminate.
• Extra newlines are regarded as malformed output, so do not output them.
• After you finish responding to the 2Q queries, immediately terminate your program. Otherwise, the judge result will be indeterminate.
• The judge for this problem is not adaptive. Before the interaction begins, the judge determines the types and order of the queries, and the integer X given in each push query.

Sample Interaction

Below is a case where Q=2, and the judge appends the values 5,3 in this order.

2

1 5

0

1 3

3
1 2
1 2
2 2

2

2

2

2

Problem Statement

Snuke wants to design a cellular automaton that conveys a binary sequence, written into a certain cell over N turns, to a distant cell.

1. Grid

There is an infinitely large grid. Each cell has a state of 0 or 1.

Let some row of the grid be row 0 and some column be column 0, with row numbers increasing by 1 downward and column numbers increasing by 1 to the right. Let (r,c) denote the coordinates of the cell at row r and column c. The coordinates of the cells are as shown in the figure below.

The cells adjacent to a given cell refer to the eight cells sharing an edge or a vertex with it.

You may choose a rectangular region satisfying the following conditions, and freely set the initial states of the cells within the region.

• Both the height H and the width W are between 1 and 150, inclusive.
• The coordinates of the top-left cell are (0,0).

The initial states of all cells outside the region are 0.

2. Update Operation

Decide on a value F_{i,j}, either 0 or 1, for each i=0,1 and j=0,1,\ldots,8; let these values be the update rule. However, F_{0,0}=0 must hold.

In the update operation, the states of all cells are updated simultaneously. For a given cell, let i be its state before the update and j be the sum of the states of the eight adjacent cells; then its state after the update is F_{i,j}.

3. Designing the Automaton

You need to decide on and output the following values.

• The update rule F_{i,j} (i=0,1) (0 \le j \le 8)
  • F_{0,0}=0 must hold.
• The height H and width W of the rectangular region for which the initial state is set
  • Both H and W must be between 1 and 150, inclusive.
• The initial states A_{r,c} (0 \le r \lt H) (0 \le c \lt W) within the rectangular region
• The coordinates (R_s,C_s) of the sending cell and (R_t,C_t) of the receiving cell
  • 0 \le R_s,R_t \lt H and 0 \le C_s,C_t \lt W must hold.
  • 50 \le |C_s-C_t| \le 100 must hold.
• The delay D from sending to receiving
  • It must be possible to read, at the receiving cell on turn k+D-1, the value that was written to the sending cell on turn k.
  • 50 \le D \le 100 must hold.

4. Judging Method

Judging is performed as follows.

1. Decide on a positive integer N and a sequence S=(S_1,S_2, \ldots ,S_N) of length N consisting of 0s and 1s. These are fixed for each test case.

2. Receive the design of the automaton that you output.

3. Prepare an empty sequence T, and simulate N+D-1 turns starting from the initial state. Specifically, for each k=1,2,\ldots,N+D-1, perform the following steps in order on turn k.

   1. If k \le N, change the state of the sending cell (R_s,C_s) to S_k.
   2. Perform one update operation on the grid.
   3. If D \le k < D+N, append the state of the receiving cell (R_t,C_t) to the end of T.

4. After the simulation ends, if S=T, your output is judged correct; otherwise, it is judged incorrect.

It is guaranteed that there exists a design of the automaton that is judged correct regardless of N and S, but due to implementation details of the judge for this problem, N and S are fixed for each test case file, and only cases with N \le 300 are used.

Constraints

• The N used by the judge is between 1 and 300, inclusive.

Sample Output

000100000
001100000
4 54
100000000000000000000000000000000000000000000000000000
000010000000000000000000000000000000000000000000000000
100010000000000000000000000000000000000000000000000000
011110000000000000000000000000000000000000000000000000
0 3 0 53 100

This sample output is provided to illustrate the output format. For N=1, it is correct for all S, but for 2 \le N, there exist some S for which it is incorrect.

Visualizer

You can check the behavior of your automaton using the visualizer.