Problem Statement

Bitaro bought a long skewer of dumplings as a snack. This skewer can be represented by N positive integers A_1, A_2, \cdots, A_N as follows. For each integer i with 0 \leq i \leq N, let s_i = A_1 + A_2 + \cdots + A_i. In particular, we define s_0 = 0.

• The skewer consists of s_N dumplings arranged in a single column from top to bottom.
• Each dumpling is either sweet or spicy. The taste of each dumpling can be described as follows.
  • If i is an odd integer satisfying 1 \leq i \leq N, then the dumplings from the (s_{i-1} + 1)-th to the s_i-th from the top are sweet.
  • If i is an even integer satisfying 1 \leq i \leq N, then the dumplings from the (s_{i-1} + 1)-th to the s_i-th from the top are spicy.

When eating this skewer of dumplings, Bitaro made Q possible plans. The j-th plan (1 \leq j \leq Q) is represented by integers L_j and R_j satisfying 1 \leq L_j \leq R_j \leq N, and in this plan he eats the dumplings from the (s_{L_j-1}+1)-th from the top through the s_{R_j}-th from the top.

Also, when eating this skewer, Bitaro decided to divide it into several bites in the following manner. Here, K is a positive integer representing Bitaro's preference for sweetness.

• He eats the dumplings from top to bottom, and each dumpling is eaten exactly once.
• In one bite, he may eat any positive number of consecutive dumplings on the skewer. If, among the dumplings eaten in that bite, the number of sweet dumplings minus the number of spicy dumplings is at least K, then Bitaro is pleased.

Given the information about the skewer of dumplings and the plans, write a program that, for each plan, computes the maximum possible number of times Bitaro can be pleased.

Constraints

• 1 \leq N \leq 500\,000.
• 1 \leq Q \leq 500\,000.
• 1 \leq K \leq 10^{14}.
• 1 \leq A_i \leq 10^9 (1 \leq i \leq N).
• 1 \leq L_j \leq R_j \leq N (1 \leq j \leq Q).
• Given values are all integers.

Subtasks

1. (6 points) Q \leq 10.
2. (5 points) K \leq 2.
3. (18 points) K \leq 10.
4. (27 points) A_1 + A_2 + \cdots + A_N \leq 500\,000．
5. (17 points) N \leq 200\,000, Q \leq 200\,000．
6. (27 points) No additional constraints.

Sample Input 1

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

Sample Output 1

7
2

For the first plan, Bitaro eats the dumplings from the first through the 12th from the top. By repeatedly eating exactly one dumpling per bite from the top, Bitaro can be pleased 7 times. Since it is impossible to make him pleased 8 times or more, you should output 7.

For the second plan, Bitaro eats the dumplings from the third through the 9th from the top. By repeatedly eating exactly one dumpling per bite from the top, Bitaro can be pleased 2 times. Since it is impossible to make him pleased 3 times or more, you should output 2.

This sample input satisfies the constraints of all subtasks.

Sample Input 2

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

Sample Output 2

2
0

This differs from Sample Input 1 only in the value of K.

For the first plan, Bitaro can be pleased 2 times by eating the dumplings in the following four bites.

• In the first bite, he eats the first through the 5th dumplings from the top. Since the number of sweet dumplings is 4 and the number of spicy dumplings is 1, Bitaro is pleased.
• In the second bite, he eats only the 6th dumpling from the top. Since the number of sweet dumplings is 0 and the number of spicy dumplings is 1, Bitaro is not pleased.
• In the third bite, he eats the 7th through the 9th dumplings from the top. Since the number of sweet dumplings is 0 and the number of spicy dumplings is 3, Bitaro is not pleased.
• In the fourth bite, he eats the 10th through the 12th dumplings from the top. Since the number of sweet dumplings is 3 and the number of spicy dumplings is 0, Bitaro is pleased.

Since it is impossible to make him pleased 3 times or more, you should output 2.

For the second plan, it is impossible for Bitaro to eat the dumplings in such a way that he is pleased at least once, so you should output 0.

This sample input satisfies the constraints of subtasks 1, 3,4,5,6.

Sample Input 3

9 4 50
24 26 89 45 84 72 15 31 66
1 9
2 8
4 6
5 6

Sample Output 3

3
2
1
1

This sample input satisfies the constraints of subtasks 1,4,5,6.

Problem Statement

The JOI-Garden has a rectangular shape divided into a grid of H rows and W columns. The cell in the i-th row from the top and the j-th column from the left is called cell (i,j).

When rain falls on a cell, the moisture level of that cell increases. The moisture level of a cell never changes except when it rains. If the moisture level of a cell becomes at least X, the cell turns into mud, which is dangerous. Therefore, every morning, JOI-kun, the manager of the JOI-Garden, may designate at most one rectangular off-limits area that contains all cells whose moisture level is at least X. More precisely, JOI-kun chooses four integers u,d,l,r (1\leq u\leq d\leq H,1\leq l\leq r\leq W), and the rectangular region consisting of all cells (i,j) satisfying u\leq i\leq d and l\leq j\leq r becomes off-limits.

Initially, the moisture level of every cell in the JOI Garden is 0.

Starting today, it will rain once every evening for N days. On the evening of the (k - 1)-th day after (1\leq k\leq N), rain falls on every cell (i,j) satisfying U_k\leq i\leq D_k and L_k\leq j\leq R_k, and the moisture level of each such cell increases by C_k.

For each k=1,2,\ldots ,N, write a program that computes the minimum possible number of cells contained in the off-limits area that JOI-kun sets on the morning of the k-th day after.

Constraints

• 1 \leq H \leq 10^9.
• 1 \leq W \leq 10^9.
• 1 \leq N \leq 200\,000.
• 1 \leq X \leq 2\times 10^{14}.
• 1 \leq U_k \leq D_k \leq H (1 \leq k \leq N).
• 1 \leq L_k \leq R_k \leq W (1 \leq k \leq N).
• 1 \leq C_k \leq 10^9 (1 \leq k \leq N).
• Given values are all integers.

Subtasks

1. (3 points) X = 1.
2. (24 points) W = 1.
3. (15 points) N \leq 300.
4. (30 points) N \leq 5\,000.
5. (28 points) No additional constraints.

Sample Input 1

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

Sample Output 1

0
1
1
6
9

The following is one example of how the moisture levels increase each day and how the off-limits area can be chosen so that the number of contained cells is minimized.

• On the evening of day 0, the moisture level of cell (3,1) increases by 5. On the morning of day 1, there are no cells whose moisture level of at least 10, so no off-limits area is set.
• On the evening of day 1, the moisture level of cells (1,1), (1,2), (2,1), (2,2), (3,1), and (3,2) each increase by 7. On the morning of day 2, cell (3,1) has moisture level of at least 10. JOI-kun chooses u=d=3 and l=r=1, thereby setting a off-limits area that contains 1 cell.
• On the evening of day 2, the moisture level of cells (1,3), (2,3), and (3,3) each increase by 4. On the morning of day 3, cell (3,1) has moisture level of at least 10. JOI-kun chooses u=d=3 and l=r=1, thereby setting a off-limits area that contains 1 cell.
• On the evening of day 3, the moisture level of cells (1,1), and (1,2) each increase by 12. On the morning of day 4, cells (1,1),(1,2), and (3,1) has moisture level of at least 10. JOI-kun chooses u=1, d=3, l=1, r=2, thereby setting a off-limits area that contains 6 cells.
• On the evening of day 4, the moisture level of cell (3,3) increases by 6. On the morning of day 5, cells (1,1), (1,2), (3,1), and (3,3) has moisture level of at least 10. JOI-kun chooses u=1, d=3, l=1, r=3, thereby setting a off-limits area that contains 9 cells.

This sample input satisfies the constraints of Subtasks 3, 4, and 5.

Sample Input 2

9 1 5 1
3 3 1 1 4
5 8 1 1 1
3 5 1 1 3
8 8 1 1 4
8 9 1 1 5

Sample Output 2

1
6
6
6
7

This sample input satisfies the constraints of all the subtasks.

Sample Input 3

4596 9794 15 141929907
600 3070 2222 8763 472026497
47 2644 3276 6033 930213777
638 945 304 1100 992702990
370 2211 2178 2977 783902937
277 2601 1559 8989 842013671
566 3272 3124 8456 254633541
91 4241 2655 8035 303526265
1342 3662 3909 7175 685435928
1176 4012 2827 8429 614977118
255 2461 1482 5835 794902067
982 2314 941 3952 342731056
1603 2215 6730 7105 332440107
2301 4568 6898 9561 591652619
124 2097 3520 8882 168525684
1845 3599 5592 7145 555656973

Sample Output 3

16165282
19783008
25583040
25583040
26266464
28021036
36437770
36437770
36437770
36437770
36437770
36437770
41864676
41864676
41864676

This sample input satisfies the constraints of Subtasks 3, 4, and 5.

Problem Statement

President K has prepared a game for the contestants of the JOI Final Stage. President K secretly has an N \times N table A, each of whose cells contains a non-negative integer. Let A_{i,j} denote the integer written in the cell in the (i + 1)-st row from the top (0 \leq i \leq N - 1) and the (j + 1)-st column from the left (0 \leq j \leq N - 1). The table A satisfies the following conditions.

• For each i such that 0 \leq i \leq N - 1, we have A_{i,i} = 0.
• For each i, j such that 0 \leq i < j \leq N - 1, we have A_{i,j} = A_{j,i}.

Consider the weighted undirected graph with N vertices in which the edge between vertex i and vertex j (0 \leq i < j \leq N - 1) has weight A_{i,j}. Let X be the weight of a minimum spanning tree of this graph. In other words, X is the value obtained by the following procedure. The goal of the game is for all contestants to cooperate and determine the value of X.

1. Set x = 0.
2. Consider an undirected graph G with N vertices. The vertices of G are numbered 0, 1, \dots, N - 1. Initially, G has no edges.
3. Repeat the following operation N - 1 times. Let X be the value of x after these N - 1 operations.
   1. Call the vertices of G that are currently reachable from vertex 0 by using some edges the near vertices, and call the other vertices the far vertices. Choose a pair (i, j) consisting of a near vertex i and a far vertex j so that the value A_{i,j} \times N^2 + i \times N + j is minimized. It can be proved that there is at least one near vertex and at least one far vertex, and that (i, j) is uniquely determined.
   2. Add the edge connecting vertex i and vertex j to G.
   3. Update x \gets x + A_{i,j}.

Define R = \lfloor 5120 / N \rfloor (where \lfloor x \rfloor denotes the greatest integer not exceeding x). There are R \times N contestants in the JOI Final Stage, divided into R groups of N contestants each. The groups are numbered 0 through R-1, and the contestants in group r (0 \leq r \leq R-1) are numbered (r, 0), (r, 1), \dots, (r, N-1).

The game proceeds by repeating the following rounds, in the order round 0, 1, 2, \dots, at most R times. During the game, the contestants are not allowed to communicate with one another, but they may share a strategy in advance.

Round r (0 \leq r \leq R-1) proceeds as follows.

• For i = 0, 1, \dots, N-1 in this order, President K and contestant (r, i) perform the following interaction.
  1. President K gives contestant (r, i) the following information.
     • the contestant's number (r, i),
     • the information in the (i + 1)-st row of the table A, namely A_{i,0}, A_{i,1}, \dots, A_{i,N-1},
     • the integers B_{r,i,0}, B_{r,i,1}, \dots, B_{r,i,N-1}, each of which is an integer between 0 and 2^{64}-1, inclusive, sent to contestant (r, i) from the contestants in the previous round.
       • If r > 0, these integers are determined in interaction 3 described below.
       • If r = 0, then for convenience we define B_{r,i,0} = B_{r,i,1} = \dots = B_{r,i,N-1} = 0.
  2. If contestant (r, i) is able to determine the value of X, they answer President K with that value. If any contestant gives an answer, the game ends immediately.
  3. For each j = 0, 1, \dots, N-1, contestant (r, i) determines an integer B_{r+1,j,i}, which must be between 0 and 2^{64}-1, inclusive, to send to contestant (r+1, j), and tells it to President K. Even when r = R - 1, so that contestant (r+1, j) does not exist, contestant (r, i) must still determine B_{r+1,j,i} and tell it to President K.

If an answered value of X is incorrect, or if nobody answers the value of X by the end of round R - 1, the game fails. If the correct value of X is answered by the end of round R - 1, the game succeeds. A smaller number of rounds used yields a higher score (if an answer is given in round r, the number of rounds is counted as r + 1).

Implement a strategy for the contestants so that the game succeeds in as few rounds as possible.

Implementation Details

Your submission must include multi.h using a #include preprocessing directive, and must implement the following function.

• std::vector<unsigned long long> strategy(int N, int r, int i, std::vector<unsigned long long> A, std::vector<unsigned long long> B)
  • The argument N represents the number of rows and columns of the table A.
  • The arguments r and i represent the contestant number (r, i).
  • The argument A is a sequence of non-negative integers of length N, where A[j] (0 \leq j \leq N - 1) represents the integer A_{i,j} written in the cell in the (i + 1)-st row from the top and the (j + 1)-st column from the left of the table A.
  • The argument B is a sequence of non-negative integers of length N, where B[j] (0 \leq j \leq N - 1) represents the integer B_{r,i,j} sent from contestant (r-1, j) to contestant (r, i). If r = 0, then \texttt{B[j]} = 0.
  • This function must return a sequence of non-negative integers of length 1 or N, representing the action taken by contestant (r, i) given the information in the arguments A, B. If the returned sequence has length other than 1 or N, the submission is judged as Wrong Answer [1].
    • To answer that the value of X is x, this function must return a sequence of length 1, namely (x). If the answered value is incorrect, the submission is judged as Wrong Answer [2].
    • If no answer is given, this function must return a sequence B' of length N.
      • For each j = 0, 1, \dots, N-1, B'[j] represents the integer B_{r+1,j,i} sent by contestant (r, i) to contestant (r+1, j). It must be an integer between 0 and 2^{64}-1, inclusive. Note that even when r = R - 1 and contestant (r+1, j) does not exist, the length of B' must still be N.
    • By the end of round R - 1, at least one contestant must give an answer. If no contestant gives an answer, the submission is judged as Wrong Answer [3].
  • The return value of this function must be determined solely by its arguments. In particular, note that the return value must not depend on previous calls to strategy or on runtime randomness. If this function returns different values for the same arguments, the submission is judged as Wrong Answer [4].
  • It is guaranteed that the given arguments can actually occur when playing the game using some table A and the submitted function strategy. However, note that calls are not necessarily made in the order of rounds 0, 1, \dots, R - 1.
  • The grader will play one or more games in a single execution. In one execution, this function is called at most 10\,240 times.

Important Notes

• You may freely implement other functions or declare global variables for internal use.
• Your submitted program must not communicate in any way with standard input, standard output, or any other files. However, outputting debugging information and the like to standard error output is allowed.

Constraints

• 2 \leq N \leq 256.
• 0 \leq A_{i,j} < 2^{48} (0 \leq i \leq N - 1, 0 \leq j \leq N - 1).
• A_{i,i} = 0 (0 \leq i \leq N - 1).
• A_{i,j} = A_{j,i} (0 \leq i < j \leq N - 1).
• N and A_{i,j} (0 \leq i \leq N - 1, 0 \leq j \leq N - 1) are integers.

Subtasks

1. (5 points) N \leq 64, A_{i,j} \leq 1 (0 \leq i \leq N - 1, 0 \leq j \leq N - 1).
2. (10 points) A_{i,j} \leq 1 (0 \leq i \leq N - 1, 0 \leq j \leq N - 1).
3. (15 points) N \leq 64.
4. (40 points) A_{i,j} < 2^{20} (0 \leq i \leq N - 1, 0 \leq j \leq N - 1).
5. (15 points) A_{i,j} < 2^{40} (0 \leq i \leq N - 1, 0 \leq j \leq N - 1).
6. (15 points) There are no additional constraints.

Scoring

If, among the test cases of a subtask, there is even one that is judged as Wrong Answer [1]–[4], Time Limit Exceeded, Memory Limit Exceeded, or Runtime Error, then the score for that subtask is 0. Otherwise, let S be the maximum number of rounds used over all games in that subtask. Then the score for that subtask is determined as follows.

In the case of Subtask 3

• Regardless of the value of S, the score for that subtask is 100\% of the points for the subtask. If S > 6, the contest site may display "Output is partially correct", but this does not affect the score.

In the case of subtasks other than Subtask 3

• If S \leq 6, the score for that subtask is 100\% of the points for the subtask.
• If 7 \leq S \leq 9, the score for that subtask is (100 - 20 \cdot (S - 6))\% of the points for the subtask.
• If 10 \leq S \leq 19, the score for that subtask is (40 - S)\% of the points for the subtask.
• If 20 \leq S, the score for that subtask is 20\% of the points for the subtask.

Compilation and Test Run

A sample grader for testing your program is included in the archive downloadable from the contest site. This archive also contains a sample file that you must submit.

The sample grader consists of a single file. That file is grader.cpp. To test your program, place the files grader.cpp, multi.cpp, and multi.h in the same Presidenty, and execute the following command.

g++ -std=gnu++20 -O2 -o grader grader.cpp multi.cpp

Alternatively, you may execute the file compile.sh included in the archive. In that case, run the following command.

./compile.sh

If the compilation succeeds, an executable file named grader is generated.

Note that the actual grader used for evaluation differs from the sample grader. The sample grader runs as a single process. This program reads input from standard input and writes the results to standard output.

Input for the Sample Grader

The sample grader plays one or more games in a single execution.

First, the sample grader reads the number of games T from standard input. Then, for each of the T games, it reads the information of the table A in the following format.

N 
A_{0,1} A_{0,2} A_{0,3} \cdots A_{0,N-1} 
A_{1,2} A_{1,3} \cdots A_{1,N-1} 
\vdots 
A_{N-2,N-1} 

Output for the Sample Grader

The sample grader outputs T lines to standard output. On the t-th line (1 \leq t \leq T), it outputs the result of the t-th game in the following format (the quotation marks are not actually printed).

• If the game succeeds, the number of rounds used in that game is output as in Accepted: 22.
• If any of the Wrong Answer conditions applies, the type of Wrong Answer is output as in Wrong Answer [4].

If the program being executed satisfies more than one Wrong Answer condition, only one of them will be displayed.

Sample Communication

Below is an example of input read by the sample grader and the corresponding sequence of function calls.

Sample Input 1

1
3
1 2
3

In round 0, the following interactions take place.

• Contestant (0, 0) does not answer the value of X, and sends B_{1,0,0} = 0 to contestant (1, 0), B_{1,1,0} = 1 to contestant (1, 1), and B_{1,2,0} = 2 to contestant (1, 2).
• Contestant (0, 1) does not answer the value of X, and sends B_{1,0,1} = 3 to contestant (1, 0), B_{1,1,1} = 4 to contestant (1, 1), and B_{1,2,1} = 5 to contestant (1, 2).
• Contestant (0, 2) does not answer the value of X, and sends B_{1,0,2} = 6 to contestant (1, 0), B_{1,1,2} = 7 to contestant (1, 1), and B_{1,2,2} = 8 to contestant (1, 2).

Since no contestant answered the value of X, the game proceeds to the next round.

In round 1, the following interaction takes place.

• Contestant (1, 0) receives B_{1,0,0} = 0 from contestant (0, 0), B_{1,0,1} = 3 from contestant (0, 1), and B_{1,0,2} = 6 from contestant (0, 2), and answers that X = 3. Since the value of X has been answered, the game ends at this point.

Because the answered value of X is correct, the game succeeds. The number of rounds used in this game is 2.

This sample input satisfies the constraints of Subtasks 3, 4, 5, and 6.

Among the files downloadable from the contest site, sample-01-in.txt corresponds to Sample Input 1. The archive downloadable from the contest site also contains further sample inputs: sample-02-in.txt, sample-03-in.txt, and sample-04-in.txt. sample-02-in.txt satisfies the constraints of all subtasks, sample-03-in.txt satisfies the constraints of Subtasks 3, 4, 5, and 6, and sample-04-in.txt satisfies the constraints of Subtasks 4, 5, and 6.

Problem Statement

Azzurro and Bordeaux, a pair visiting a casino in Italy, decided to play a game proposed by the dealer Chiaro.

In this game, information is transmitted using an N \times N grid (N = 8)). The rows of the grid are numbered from 0 to N - 1 from top to bottom, and the columns of the grid are numbered from 0 to N - 1 from left to right. A cell with row number r and column number c is denoted by (r, c).

In this game, Azzurro and Bordeaux are isolated in separate rooms. They will play Q turns. The i-th turn (1 \leq i \leq Q) proceeds as follows.

1. Azzurro receives from Chiaro an integer N, an integer L_i (1 \leq L_i \leq 51), a card on which a string S_i of length L_i consisting of 'A' and 'B' is written, and an N \times N grid whose cells are all colored white.
2. Azzurro colors each of the N^2 cells either blue or red. He then hands the grid to Chiaro.
3. Chiaro performs the following operations out of sight of both Azzurro and Bordeaux.
   1. He selects one path from (0, 0) to (N - 1, N - 1) by repeatedly moving only to an adjacent cell either down or to the right.
   2. For every cell on the path, if the cell is colored blue, he repaints it red; if it is colored red, he repaints it blue.
4. Bordeaux receives from Chiaro a card with integers N and L_i written on it, along with the grid.
5. Bordeaux writes a string of length L_i consisting of A and B on a sheet of paper. If the written string matches S_i, Azzurro and Bordeaux win.

Write programs which implement the strategies of Azzurro and Bordeaux to win this game. For the grading of this task, see Grading.

Implementation Details

You need to submit two files.

The first file is Azzurro.cpp. It should implement Azzurro's strategy. It should implement the following functions. The program should include Azzurro.h using the preprocessing directive #include.

• std::vector<std::vector<int>> Azzurro(int N, int L, std::string S) This function is called Q times. The i-th call (1 \leq i \leq Q) corresponds to the procedures 1., 2.\ of the i-th turn of the game.
  • The parameter N is the integer N written on the card given to Azzurro in the procedure 1.\ of the i-th turn.
  • The parameter L is the integer L_i written on the card given to Azzurro in the procedure 1.\ of the i-th turn.
  • The parameter S is the string S_i written on the card given to Azzurro in the procedure 1.\ of the i-th turn.
  For each call to the function Azzurro, your program must return an N \times N two-dimensional array x, each of whose elements is either 0 or 1. If this condition is not satisfied, your program is judged as Wrong Answer [1].
  • If \texttt{x}[\texttt{r}][\texttt{c}] = 0 (0 \leq \texttt{r} \leq N - 1, 0 \leq \texttt{c} \leq N - 1), it indicates that the cell (\texttt{r}, \texttt{c}) is colored blue.
  • If \texttt{x}[\texttt{r}][\texttt{c}] = 1 (0 \leq \texttt{r} \leq N - 1, 0 \leq \texttt{c} \leq N - 1), it indicates that the cell (\texttt{r}, \texttt{c}) is colored red.

The second file is Bordeaux.cpp. It should implement Bordeaux's strategy. It should implement the following function. The program should include Bordeaux.h using the preprocessing directive #include.

• std::string Bordeaux(int N, int L, std::vector<std::vector<int>> T) This function is called every time when Azzurro finishes painting the grid. This function is called Q times in total. The i-th call (1 \leq i \leq Q) corresponds to the procedures 4., 5.\ of the i-th turn of the game.
  • The parameter N is the integer N written on the card given to Bordeaux in the procedure 4.\ of the i-th turn.
  • The parameter L is the integer L_i written on the card given to Bordeaux in the procedure 4.\ of the i-th turn.
  • The parameter T is the N \times N two-dimensional array corresponding to the grid of cells given to Bordeaux in the procedure 4.\ of the i-th turn. The color of the cell (\texttt{r}, \texttt{c}) (0 \leq \texttt{r} \leq N - 1，0 \leq \texttt{c} \leq N - 1) is blue if \texttt{T[a][b]} = 0, and red if \texttt{T[a][b]} = 1.
  For each call to the function Bordeaux, your program must return a string s of length L_i consisting of 'A' and 'B'. If this condition is not satisfied, your program is judged as Wrong Answer [2].

Important Notices

• Your program can implement other functions for internal use, or use global variables. Submitted files will be compiled with the grader, and become a single executable file. All global variables and internal functions should be declared in an unnamed namespace to avoid confliction with other files. When it is graded, it will be executed as two processes of Azzurro and Bordeaux. The process of Azzurro and the process of Bordeaux cannot share global variables.
• Your program must not use the standard input and the standard output. Your program must not communicate with other files by any methods. However, your program may output debugging information to the standard error.

Compilation and Test Run

You can download an archive file from the contest webpage which contains the sample grader to test your program. The archive file also contains a sample source file of your program.

The sample grader is the file grader.cpp. In order to test your program, put grader.cpp，Azzurro.cpp，Bordeaux.cpp，Azzurro.h，Bordeaux.h in the same directory, and run the following command to compile your programs.

g++ -std=gnu++20 -O2 -o grader grader.cpp Azzurro.cpp Bordeaux.cpp

Instead, you may run compile.sh contained in the archive file. In this case, run the following command to compile your programs.

./compile.sh

When the compilation succeeds, the executable file grader is generated.

Note that the actual grader is different from the sample grader. The sample grader will be executed as a single process, which will read input data from the standard input and write the results to the standard output.

In the actual judging grader, the path chosen by Chiaro is fixed in advance. That is, the path selected by Chiaro is determined before the functions Azzurro and Bordeaux in your submitted program are called.

Input for the Sample Grader

The sample grader reads the following data from the standard input.

Q N 
L_1 
S_1 
R_1 
L_2 
S_2 
R_2 
\vdots 
L_Q 
S_Q 
R_Q

Here, R_i (1 \leq i \leq Q) is a string of length 2(N - 1) consisting of exactly N - 1 occurrences of 'D' and N - 1 occurrences of 'R'. This string represents the path chosen by Chiaro in the i-th turn, which starts from (0, 0) and reaches (N - 1, N - 1) by repeatedly moving only to an adjacent cell either down or to the right. Specifically, starting from (0, 0), for each j = 1, 2, \cdots, 2(N - 1), if the j-th character of R_i is 'D', the move is to the adjacent cell below; if it is 'R', the move is to the adjacent cell to the right. Repeating this process results in reaching (N - 1, N - 1).

Output of the Sample Grader

The sample grader outputs the following information to the standard output (quotes for clarity).

• If your program is judged as correct, it writes the value of L^{*} as "Accepted: 26". For the value of L^{*}, see Grading.
• If your program is judged as any type of Wrong Answer, the sample grader writes its type as "Wrong Answer [1]".

If your program satisfies the conditions of several types of Wrong Answer, the sample grader reports only one of them. The sample grader may terminate the execution when one of the conditions for wrong answer is met.

Constraints

All the input data satisfy the following conditions.

• 1 \leq Q \leq 30\,000.
• N = 8.
• 1 \leq L_i \leq 51 (1 \leq i \leq Q).
• Q, L_i (1 \leq i \leq Q) are integers.
• S_i (1 \leq i \leq Q) is a string of length L_i consisting of 'A' and 'B'.
• R_i (1 \leq i \leq Q) is a string of length 2(N - 1) consisting of exactly N - 1 occurrences of 'D' and N - 1 occurrences of 'R'.

Grading

If your program is judged as any type of Wrong Answer [1] or Wrong Answer [2] (see Implementation Details), Time Limit Exceeded, Memory Limit Exceeded, or Runtime Error, in any testcase, your score is 0 points.

Otherwise, let L^{*} be the minimum of the following values for all test cases of this task. Your score is calculated as in the following table.

• The maximum value of L such that Azzurro and Bordeaux win all the turns satisfying L_i \leq L. However, if they win all the turns in the test case, we set L = 51.

Sample Communication

Here is a sample input for the sample grader and corresponding function calls.

Sample Input 1

2 2
1
B
RD
3
ABB
DR

This sample input consists of Q \ (= 2) turns, and in each turn an N \times N grid (N = 2) is used. In this example, the first turn proceeds as follows.

1. Azzurro colors (0, 1) and (1, 0) blue, and (0, 0) and (1, 1) red. He then hands the grid to Chiaro.
2. Chiaro performs the following operations out of sight of Azzurro and Bordeaux.
   1. He selects the path (0, 0) \rightarrow (0, 1) \rightarrow (1, 1) as a path from (0, 0) to (N - 1, N - 1) by repeatedly moving only to an adjacent cell either down or to the right.
   2. For the three cells (0, 0), (0, 1), (1, 1) on this path, he changes their colors. As a result, the colors of (0, 0), (0, 1), (1, 1) become blue, red, and blue, respectively.
3. Bordeaux can win this turn by writing "B" on the paper.

The second turn proceeds as follows.

1. Azzurro colors all cells blue. He then hands the grid to Chiaro.
2. Chiaro performs the following operations out of sight of Azzurro and Bordeaux.
   1. He selects the path (0, 0) \rightarrow (1, 0) \rightarrow (1, 1) as a path from (0, 0) to (N - 1, N - 1) by repeatedly moving only to an adjacent cell either down or to the right.
   2. For the three cells (0, 0), (1, 0), (1, 1) on this path, he changes their colors. As a result, the colors of (0, 0), (1, 0), (1, 1) all become red.
3. Bordeaux can win this turn by writing "ABB" on the paper.

Note that this sample input does not satisfy the constraints of the problem. The file sample-01-in.txt, which can be downloaded from the contest site, corresponds to Sample Input 1. The file sample-02-in.txt, which can be downloaded from the contest site, is a sample input that satisfies the constraints.

Problem Statement

There are N towns in the country of JOI, numbered from 1 to N. Also, there are N-1 roads in the country of JOI, numbered from 1 to N-1. Road j (1 \leq j \leq N-1) connects town U_j and town V_j in both directions. It is possible to travel from any town to any other town by using some number of roads.

There is one shop in each town in the country of JOI. In the shop in town i (1 \leq i \leq N), a souvenir is sold for price A_i.

This year, M tours are planned in the country of JOI. The k-th tour (1 \leq k \leq M) starts from town S_k and travels by roads to town T_k without visiting the same town twice. Note that the k-th tour visits both towns S_k and T_k. It is guaranteed that S_k \neq T_k. Note that, from the structure of the country of JOI, the sequence of towns visited by a tour is uniquely determined.

You are planning to participate in one of these tours and buy one souvenir in each of exactly two of the towns visited on the tour. Moreover, you want to use up exactly the entire budget prepared for souvenirs, so for each of Q candidate budgets, you decided to investigate in how many ways this can be done.

Given the roads in the country of JOI, the prices of the souvenirs, the information on the tours, and the candidate budgets B_1, B_2, \ldots, B_Q, write a program that computes the number of ways to choose a tour and the towns in which to buy souvenirs. More formally, for each q (1 \leq q \leq Q), write a program that computes the number of triples of integers (k,u,v) satisfying all of the following conditions.

• 1\leq k\leq M.
• 1\leq u < v \leq N.
• The k-th tour visits towns u and v.
• A_u+A_v=B_q.

Constraints

• 2 \leq N \leq 100\,000.
• 1\leq A_i\leq N (1 \leq i \leq N).
• 1\leq U_j\leq N (1 \leq j \leq N-1).
• 1\leq V_j\leq N (1 \leq j \leq N-1).
• It is possible to travel from any town to any other town by using some number of roads.
• 1\leq M \leq 200\,000.
• 1\leq S_k\leq N (1\leq k\leq M).
• 1\leq T_k\leq N (1\leq k\leq M).
• S_k\neq T_k (1\leq k\leq M).
• 1\leq Q\leq 2\,000.
• 1\leq B_1 < B_2 < \cdots < B_Q\leq 2N.
• All input values are integers.

Subtasks

1. (3 points) N\leq 100, M\leq 100, Q\leq 100.
2. (4 points) N\leq 5\,000, U_j=j (1\leq j\leq N-1), V_j=j+1 (1\leq j\leq N-1).
3. (5 points) N\leq 5\,000.
4. (6 points) Q= 1, U_j=j (1\leq j\leq N-1), V_j=j+1 (1\leq j\leq N-1).
5. (10 points) Q= 1.
6. (7 points) M\leq 1000, U_j=j (1\leq j\leq N-1), V_j=j+1 (1\leq j\leq N-1).
7. (12 points) M\leq 1000.
8. (10 points) N\leq 50\,000, M\leq 50\,000, U_j=j (1\leq j\leq N-1), V_j=j+1 (1\leq j\leq N-1).
9. (15 points) N\leq 50\,000, M\leq 50\,000.
10. (11 points) U_j=j (1\leq j\leq N-1), V_j=j+1 (1\leq j\leq N-1).
11. (17 points) No additional constraints.

Sample Input 1

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

Sample Output 1

0
0
4
2
4
1
0

First, the towns visited by each tour are as follows.

• The 1st tour visits towns 1, 2, 3, 4.
• The 2nd tour visits towns 1, 6.
• The 3rd tour visits towns 2, 5.
• The 4th tour visits towns 3, 7, 8.

Represent a method of participating in the k-th tour and buying souvenirs in towns u and v by (k,u,v). Then, for each candidate budget, the ways to use up the budget exactly are as follows.

• There are 0 ways to use up budget 1.
• There are 0 ways to use up budget 2.
• There are 4 ways to use up budget 3: (1,1,2), (1,1,4), (2,1,6), (3,2,5).
• There are 2 ways to use up budget 4: (1,1,3), (1,2,4).
• There are 4 ways to use up budget 5: (1,2,3), (1,3,4), (4,3,8), (4,7,8).
• There is 1 way to use up budget 6: (4,3,7).
• There are 0 ways to use up budget 16.

This input example satisfies the constraints of subtasks 1, 3, 7, 9, 11.

Sample Input 2

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

Sample Output 2

1
2
3
3
1

This input example satisfies the constraints of subtasks 1, 2, 3, 6, 7, 8, 9, 10, 11.

Problem Statement

There are N points on a straight path, numbered 1, 2, \ldots, N from left to right. The path is one-way from left to right.

There are also M teleporter devices numbered 1, 2, \ldots, M. By using device i (1 \leq i \leq M), one can warp from point S_i to point T_i (S_i < T_i).

Bitaro is currently at point 1 and wants to reach point N. When Bitaro is at point j (1 \leq j \leq N-1), he can take one of the following actions:

• Move on foot to point j+1.
• Choose an i (1 \leq i \leq M) satisfying S_i = j, use device i, and warp to point T_i.

It is known that warp travel places stress on the body. You are concerned about Bitaro's safety, so you decide to destroy zero or more teleporter devices so that, no matter which route Bitaro takes, the number of warp travels is at most K. Device i can be destroyed by paying cost C_i; if so, Bitaro can no longer use that device.

Find the minimum possible total cost you need to pay when destroying zero or more teleporter devices so that, regardless of Bitaro's route, the number of warp travels is at most K.

Constraints

• 2 \leq N \leq 100\,000.
• 1 \leq K \leq M \leq 100\,000.
• 1 \leq S_i < T_i \leq N (1 \leq i \leq M).
• 1 \leq C_i \leq 10^9 (1 \leq i \leq M).
• Given values are all integers.

Subtasks

1. (5 points) K=1.
2. (3 points) N \leq 20, M \leq 20.
3. (29 points) N \leq 500, M \leq 500.
4. (23 points) N \leq 4\,000, M \leq 4\,000.
5. (24 points) N \leq 40\,000, M \leq 40\,000.
6. (16 points) No additional constraints.

Sample Input 1

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

Sample Output 1

4

Consider the case where devices 3 and 4 are destroyed.

Then Bitaro can use only devices 1 and 2. When moving from point 1 to point 8, Bitaro will always make at most one warp travel, so the condition is satisfied.

In this case, the total paid cost is 4. Since it is impossible to make the cost at most 3, the correct output is 4.

This input example satisfies the constraints of all subtasks.

Sample Input 2

12 7 2
1 5 3
4 8 2
2 4 5
2 4 8
7 9 4
9 11 7
3 10 5

Sample Output 2

6

Destroying devices 2 and 5 is optimal.

This input example satisfies the constraints of subtasks 2,3,4,5,6.

Sample Input 3

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

Sample Output 3

0

In this case, there is no need to destroy any device.

This input example satisfies the constraints of subtasks 2,3,4,5,6.

Problem Statement

The country of JOI is an equilateral triangle with side length L whose vertices are points A, B, and C. Here, L is a positive integer. Side AB connects vertices A and B in the east-west direction, and vertex A is the westernmost point of the country of JOI, while vertex B is the easternmost point. Vertex C is the northernmost point of the country of JOI.

The country of JOI is divided into L^2 regions, each of which is an equilateral triangle with side length 1. A point that is a vertex of some region is called a lattice point. For integers x, y satisfying 0\leq y\leq L and 0\leq x\leq L-y, the lattice point that is the (1+y)-st from the south and the (1+x)-st from the west is denoted by (x,y). In particular, A, B, and C are denoted by (0,0), (L,0), and (0,L), respectively. For example, the following figure shows the regions and the lattice points when L=5.

In the country of JOI, weather forecasts for the next N days have been announced. On day i, rain is forecast to fall in the triangular region T_i whose vertices are lattice points (X_i, Y_i), (X_i + Z_i, Y_i), and (X_i, Y_i + Z_i). An region is said to be forecast to receive rain on day i if the entire region is contained in T_i.

In order to prepare for disasters caused by rainfall, it is necessary to determine, for each k=1,2,\ldots,K, the number of regions that are forecast to receive rain on at least k days.

Given the size of the country of JOI, the weather forecasts, and K, write a program which, for each k=1,2,\ldots,K, computes the number of regions that are forecast to receive rain on at least k days.

Constraints

• 2\leq L\leq 10^9.
• 2 \leq N \leq 200\,000.
• 1 \leq K \leq 5.
• 0\leq X_i\leq L (1\leq i\leq N).
• 0\leq Y_i\leq L (1\leq i\leq N).
• 1 \leq Z_i\leq L (1\leq i\leq N).
• X_i+Y_i+Z_i\leq L (1\leq i\leq N).
• All input values are integers.

Subtasks

1. (4 points) N = 2, K = 2.
2. (5 points) L\leq 100, N\leq 100.
3. (5 points) L\leq 1\,000.
4. (7 points) N\leq 2\,000.
5. (10 points) X_i = 0 (1\leq i\leq N), K = 1.
6. (10 points) X_i = 0 (1\leq i\leq N).
7. (23 points) K = 1.
8. (18 points) K \leq 2.
9. (18 points) There are no additional constraints.

Sample Input 1

5 2 2
1 0 3
0 1 4

Sample Output 1

21
4

If we illustrate, for each region, the number of days on which rain is forecast to fall, we obtain the following figure.

This sample input satisfies the constraints for Subtasks 1, 2, 3, 4, 8, and 9.

Sample Input 2

5 4 5
1 0 4
0 1 3
2 0 2
1 2 2

Sample Output 2

21
10
2
0
0

If we illustrate, for each region, the number of days on which rain is forecast to fall, we obtain the following figure.

This sample input satisfies the constraints for Subtasks 2, 3, 4, and 9.

Problem Statement

There is a vast field in JOI Village. The field is represented by the infinite xy-plane, where the positive direction of the x-axis is East and the positive direction of the y-axis is North.

The mayor of JOI Village plans to place several scarecrows in the field in order to protect it from enemies. Each scarecrow protects a certain region of the plane depending on its position and direction.

Currently, N placement plans have been proposed, numbered from 1 to N. Executing plan i (1 \leq i \leq N) requires a cost of C_i. Each plan is described by three integers T_i, X_i, Y_i as follows.

• If T_i = 1, a scarecrow is placed at the point (X_i, Y_i) facing West. This scarecrow protects all points on the plane satisfying x \leq X_i.
• If T_i = 2, a scarecrow is placed at the point (X_i, Y_i) facing East. This scarecrow protects all points on the plane satisfying x \geq X_i.
• If T_i = 3, a scarecrow is placed at the point (X_i, Y_i) facing South. This scarecrow protects all points on the plane satisfying y \leq Y_i.
• If T_i = 4, a scarecrow is placed at the point (X_i, Y_i) facing North. This scarecrow protects all points on the plane satisfying y \geq Y_i.

The mayor wants to select and execute some of these N plans so that every point on the plane is protected by at least K scarecrows. Among all such choices, the total cost should be minimized. It is guaranteed that the coordinates (X_i, Y_i) are pairwise distinct among the N plans.

Given the information of the N plans, determine whether it is possible to select plans so that every point on the plane is protected by at least K scarecrows. If it is possible, output the minimum possible total cost of the selected plans.

Constraints

• 1 \leq K \leq N \leq 200\,000．
• T_i is one of 1, 2, 3, or 4 (1 \leq i \leq N).
• 0 \leq X_i \leq 10^9 (1 \leq i \leq N)．
• 0 \leq Y_i \leq 10^9 (1 \leq i \leq N)．
• (X_i, Y_i) \neq (X_j, Y_j) (1 \leq i < j \leq N)．
• 0 \leq C_i \leq 10^9 (1 \leq i \leq N)．
• Given values are all integers.

Subtasks

1. (4 points) K = 1．
2. (6 points) K \leq 2．
3. (11 points) N \leq 500，K \leq 300．
4. (27 points) N \leq 6\,000．
5. (19 points) N \leq 75\,000．
6. (33 points) No additional constraints.

Sample Input 1

7 1
2 45 21 96
1 5 85 70
1 36 73 78
1 28 12 80
2 15 49 21
1 45 11 96
2 63 26 19

Sample Output 1

99

For example, suppose that plans 3 and 5 are executed. Then the scarecrows are placed as follows.

• In plan 3, one scarecrow is placed at the point (36,73) facing West. The cost is 78.
• In plan 5, one scarecrow is placed at the point (15,49) facing East. The cost is 21.

In this case, every point on the coordinate plane is protected by at least one scarecrow. For example, the point (0,0) is protected by the scarecrow placed at (36,73) facing West in plan 3. The total cost is 78 + 21 = 99. It is impossible to protect every point on the plane with at least one scarecrow with a smaller total cost, so the output should be 99.

This sample input satisfies the constraints of all subtasks.

Sample Input 2

7 3
2 45 21 96
1 5 85 70
1 36 73 78
1 28 12 80
2 15 49 21
1 45 11 96
2 63 26 19

Sample Output 2

-1

This example differs from Sample Input 1 only in the value of K. Since it is impossible to protect every point on the coordinate plane with at least 3 scarecrows, the output should be -1.

This sample input satisfies the constraints of subtasks 3,4,5,6.

Sample Input 3

19 5
2 36 42 64
2 7 89 74
1 0 15 82
1 10 63 55
2 58 28 19
2 45 91 3
2 2 34 97
1 7 55 82
1 17 12 17
2 59 76 82
1 7 4 68
2 51 98 47
1 51 21 38
2 19 0 72
1 73 73 11
2 62 19 74
1 45 7 94
1 79 32 21
1 85 50 21

Sample Output 3

315

This sample input satisfies the constraints of subtasks 3,4,5,6.

Sample Input 4

8 3
4 4 21 80
2 59 65 69
4 63 36 3
2 29 13 23
1 37 45 95
2 79 14 89
3 91 54 76
1 85 46 62

Sample Output 4

328

This sample input satisfies the constraints of subtasks 3,4,5,6.

Problem Statement

There are N towns in the country of IOI where JOI-kun lives, numbered from 1 to N. Also, there are N-1 roads in the country of IOI, numbered from 1 to N-1. Road j (1 \leq j \leq N-1) connects town U_j and town V_j in both directions. It is possible to travel from any town to any other town by using some number of roads.

A stamp rally will now be held in the country of IOI. One stamp station will be installed in each town. The stamp station in town i (1 \leq i \leq N) will be installed at time T_i.

JOI-kun decides to participate in the stamp rally. At time 0, JOI-kun starts from one of the towns. Also, JOI-kun has stamina D at time 0.

When JOI-kun is in town i at time t, he takes the following actions.

1. First, if a stamp station has already been installed in the current town, he presses the stamp. That is, he presses the stamp if T_i \leq t.
2. Next, he chooses either to finish the stamp rally or to move to another town. However, he can choose to move to another town only if there exists an adjacent town connected to town i by a road that he has not visited yet, and his current stamina is at least 1.
3. If JOI-kun chooses to move to another town, he chooses an unvisited town j among the towns connected to town i by a road, and moves there. His stamina decreases by 1, and he arrives at town j at time t+1.
4. If JOI-kun chooses to finish the stamp rally, the rally is successful if he has pressed a stamp at least once up to that point, and he can receive a present there. Otherwise, the rally is unsuccessful.

Assume that all times other than travel time between towns are negligible. Note that JOI-kun cannot stay in the same town.

You are an event organizer. If JOI-kun succeeds in the stamp rally, you need to prepare presents in the corresponding towns. However, the number of presents is limited, so you want to prepare presents in as few towns as possible. Unfortunately, you do not know from which town JOI-kun will start. Therefore, for each s (1 \leq s \leq N), you want to find the number of towns in which presents must be prepared when JOI-kun starts from town s. In other words, you need to count the number of g (1 \leq g \leq N) such that it is possible for the stamp rally to be successful when JOI-kun finishes at town g.

Given the information about the towns and roads in the country of IOI, JOI-kun's stamina, and the installation times of the stamp stations, write a program that computes, for each town, the number of towns in which presents must be prepared when JOI-kun starts from that town.

Constraints

• 2 \leq N \leq 400\,000.
• 0 \leq D \leq N-1.
• 0 \leq T_i \leq N (1 \leq i \leq N).
• 1 \leq U_j < V_j \leq N (1 \leq j \leq N-1).
• It is possible to travel from any town to any other town by using some number of roads.
• Given values are all integers.

Subtasks

1. (3 points) D\leq 1.
2. (7 points) N\leq 3\,000, (U_j,V_j)=(j,j+1) (1\leq j \leq N-1).
3. (10 points) N\leq 3\,000.
4. (11 points) (U_j,V_j)=(j,j+1) (1\leq j \leq N-1).
5. (41 points) D=N-1, N \leq 150\,000.
6. (28 points) No additional constraints.

Sample Input 1

5 2
2 2 0 1 3
1 2
2 3
2 4
4 5

Sample Output 1

2
3
4
2
2

We show one example of JOI-kun's actions when s=1.

• At time 0, JOI-kun is in town 1 and takes the following actions.
  • The stamp station in town 1 has not been installed yet, so JOI-kun does not press a stamp.
  • JOI-kun's current stamina is 2. He moves to town 2, which is one of the unvisited towns connected to town 1 by a road.
  • JOI-kun's stamina decreases by 1, and he arrives at town 2 at time 1.
• At time 1, JOI-kun is in town 2 and takes the following actions.
  • The stamp station in town 2 has not been installed yet, so JOI-kun does not press a stamp.
  • JOI-kun's current stamina is 1. He moves to town 3, which is one of the unvisited towns connected to town 2 by a road.
  • JOI-kun's stamina decreases by 1, and he arrives at town 3 at time 2.
• At time 2, JOI-kun is in town 3 and takes the following actions.
  • The stamp station in town 3 has already been installed, so JOI-kun presses a stamp.
  • JOI-kun chooses to finish the stamp rally here. Since he has pressed a stamp at least once, the stamp rally is successful. He receives a present there.

Therefore, when JOI-kun starts from town 1 and finishes the stamp rally at town 3, the stamp rally can be successful, so it is necessary to prepare a present in town 3. When JOI-kun starts from town 1, presents must be prepared only in towns 3 and 4, so the first line of the output should be 2.

Also, when JOI-kun starts from town 2, presents must be prepared only in towns 3, 4, and 5, so the second line of the output should be 3.

This input example satisfies the constraints of subtasks 3,6.

Sample Input 2

5 1
0 1 2 1 2
1 2
2 3
3 4
4 5

Sample Output 2

2
1
2
0
1

This input example satisfies the constraints of subtasks 1,2,3,4,6.

Sample Input 3

7 6
2 3 0 4 1 3 4
1 2
2 3
2 4
1 5
1 6
6 7

Sample Output 3

2
2
7
5
1
2
5

This input example satisfies the constraints of subtasks 3,5,6.

Problem Statement

JOI Bakery is a bakery famous for its mouth-watering croissants. JOI Bakery has N bakers numbered from 1 to N. Baker i (1 \leq i \leq N) takes i minutes to make one croissant. One baker cannot make multiple croissants at the same time.

Today, M customers numbered from 1 to M are scheduled to visit JOI Bakery, and each customer plans to order one croissant. Customer j (1 \leq j \leq M) will order a croissant at time T_j, where time t denotes the time t minutes from now. However, a customer who cannot receive their croissant within L minutes of ordering will give up and leave the shop. In other words, to fulfill the order of customer j (1 \leq j \leq M), the croissant must be finished by time T_j + L (including exactly at time T_j + L).

Manager K, who manages JOI Bakery, plans to have exactly one baker work today and is considering which baker to send and at what time. Since bakers focus intensely on bread-making during their shift, they ignore all orders placed after their start time (not including exactly at the start time). That is, a baker starting work at time t cannot fulfill orders from customers j (1 \leq j \leq M) such that T_j > t.

Manager K is currently considering Q work plans. The q-th plan (1 \leq q \leq Q) is to have baker A_q start work at time B_q. To help with the decision, for each of the Q plans, he wants to know the maximum number of customers whose orders can be fulfilled if that plan is executed. Note that the time it takes for a baker to start making a croissant after arriving, and the time it takes to start making a new croissant after finishing one, can be ignored.

Given information about the customers visiting JOI Bakery and the work plans, create a program to find the maximum number of customers whose orders can be fulfilled for each plan.

Constraints

• 1 \leq N \leq 4\times 10^{12}.
• 1 \leq M \leq 2\,000\,000.
• 1 \leq L \leq 2\times 10^{12}.
• 1 \leq Q \leq 400\,000.
• 0 \leq T_j \leq 2\times 10^{12} (1 \leq j \leq M).
• T_j \leq T_{j+1} (1 \leq j \leq M-1).
• 1 \leq A_q \leq N (1 \leq q \leq Q).
• 0 \leq B_q \leq 4\times 10^{12} (1 \leq q \leq Q).
• Given values are all integers.

Subtasks

1. (8 points) M \leq 10, Q \leq 100\,000.
2. (12 points) M \leq 500, Q \leq 100\,000.
3. (30 points) T_M \leq B_q < T_1+L (1 \leq q \leq Q).
4. (10 points) T_M \leq B_q (1 \leq q \leq Q).
5. (22 points) M \leq 500\,000, Q \leq 100\,000.
6. (18 points) No additional constraints.

Sample Input 1

4 4 6 4
0 2 3 8
2 3
1 6
3 3
4 7

Sample Output 1

3
2
2
0

Regarding the 1st work plan, baker 2 starting at time 3 can fulfill the orders of 3 customers 1, 2, and 3, for example, as follows:

• First, to fulfill customer 1's order, start making a croissant at time 3 and finish it 2 minutes later at time 5. (This satisfies the condition to finish by time T_1 + L = 0 + 6 = 6.)
• Next, to fulfill customer 2's order, start making a croissant at time 5 and finish it 2 minutes later at time 7. (This satisfies the condition to finish by time T_2 + L = 2 + 6 = 8.)
• Finally, to fulfill customer 3's order, start making a croissant at time 7 and finish it 2 minutes later at time 9. (This satisfies the condition to finish by time T_3 + L = 3 + 6 = 9.)

Customer 4's order is ignored because it arrives after the baker's start time, so it cannot be fulfilled. Thus, a maximum of 3 customers' orders can be fulfilled, so the 1st line outputs 3.

Regarding the 2nd work plan, baker 1 starting at time 6 can fulfill the orders of 2 customers 2 and 3, for example, as follows:

• First, to fulfill customer 3's order, start making a croissant at time 6 and finish it 1 minute later at time 7. (This satisfies the condition to finish by time T_3 + L = 3 + 6 = 9.)
• Next, to fulfill customer 2's order, start making a croissant at time 7 and finish it 1 minute later at time 8. (This satisfies the condition to finish by time T_2 + L = 2 + 6 = 8.)

Customer 4's order is ignored because it arrives after the start time. Also, the order of customer 1, which needs to be finished by time 6, cannot be fulfilled. Thus, a maximum of 2 customers' orders can be fulfilled, so the 2nd line outputs 2.

Regarding the 3rd work plan, baker 3 starting at time 3 can fulfill orders for customers 1 and 3, or customers 2 and 3, but cannot fulfill all orders for customers 1, 2, and 3. They also cannot fulfill the order for customer 4 which arrives after the start time. Thus, a maximum of 2 customers' orders can be fulfilled, so the 3rd line outputs 2.

Regarding the 4th work plan, baker 4 starting at time 7 cannot fulfill any customer's order. Thus, the 4th line outputs 0.

This sample input satisfies the constraints of Subtasks 1,2,5, and 6.

Sample Input 2

20 5 12 4
1 2 4 8 10
1 12
3 10
3 11
15 10

Sample Output 2

5
4
3
0

This sample input satisfies the constraints of all the subtasks.

Sample Input 3

100000 6 272273 10
5 9 209 8128 17202 50102
164 9
11 24
835 9267
2 256
2 314156
18475 142
1826 18978
44757 1
4 1646
218 44

Sample Output 3

2
2
4
3
1
2
5
0
3
2

This sample input satisfies the constraints of Subtasks 1,2,5, and 6.

Problem Statement

JOI Kingdom consists of N cities and N-1 highways. The cities are numbered 1 through N, and the highways are numbered 1 through N-1. It is possible to travel from any city to any other city by traversing a number of highways.

Each city has a popularity, represented by a non-negative integer. The popularity of city i (1 \leq i \leq N) is initially C_i. Each highway has a travel time, represented by a positive integer. Highway j (1 \leq j \leq N-1) connects city A_j and city B_j, and its travel time is initially D_j.

Each city in JOI Kingdom has a cauldron. JOI Kingdom keeps its tradition that, in a festival, cities ignite their cauldrons, and these ignitions signal the departure of parades from those cities.

City u is adjacent to city v if these two cities are directly connected by a highway. At the exact moment when a city ignites its cauldron, one parade will depart from this city for each of its adjacent cities, spending time equal to the travel time of the corresponding highway. To be precise, for two adjacent cities v and u, the parade from city v reaches city u at time t+d, where t is the time when the cauldron of city v is ignited, and d is the travel time of the highway connecting cities v and u.

Some cities ignite their cauldron the moment the festival starts, while other cities only do so after the festival heats up enough. Let the time 0 be the start of the festival. For the city i whose popularity is c, the time when city i ignites its cauldron is determined as follows:

• If c = 0, city i ignites its cauldron at time 0.
• If c \geq 1, city i ignites its cauldron at the time when the number of parades that have arrived from adjacent cities becomes at least c. If this never happens, city i never ignites its cauldron.

Mr. K will stay at JOI Kingdom. During his stay, JOI Kingdom will have Q events related to its festival. These events are numbered 1 through Q from earliest to latest.

Event k (1 \leq k \leq Q) is one of the following 3 types:

• Type 1: The popularity of city V_k changes to X_k.
• Type 2: The travel time of highway E_k changes to X_k.
• Type 3: Mr. K visits city V_k. Assuming a festival starts at this moment, you must determine whether {city \nolinebreak V_k} would ignite its cauldron, and if so, calculate the time that the cauldron is ignited.

Write a program which, given the structure of JOI Kingdom, popularity of each city, travel time of each highway, and details of the events, for each Type 3 event, determines when the city Mr. K visits ignites its cauldron.

Constraints

• 2 \leq N \leq 150\,000.
• 0 \leq C_i \leq N (1 \leq i \leq N).
• 1 \leq A_j < B_j \leq N (1 \leq j \leq N-1).
• 1 \leq D_j \leq 1\,000\,000 (1 \leq j \leq N-1).
• It is possible to travel from any city to any other city by traversing a number of highways.
• 1 \leq Q \leq 150\,000.
• If P_k = 1, we have 1 \leq V_k \leq N, 0 \leq X_k \leq N (1 \leq k \leq Q).
• If P_k = 2, we have 1 \leq E_k \leq N-1, 1 \leq X_k \leq 1\,000\,000 (1 \leq k \leq Q).
• If P_k = 3, we have 1 \leq V_k \leq N (1 \leq k \leq Q).
• Given values are all integers.

Subtasks

1. (6 points) N \leq 2\,000, Q \leq 2\,000.
2. (7 points) A_j = 1, B_j = j+1 (1 \leq j \leq N-1). If P_k = 3, we have V_k = 1 (1 \leq k \leq Q).
3. (14 points) N-1 is divisible by 3. A_j = ((j - 1) \bmod \frac{N-1}{3}) + 1, B_j = j+1 (1 \leq j \leq N-1). If P_k = 3, we have V_k = 1 (1 \leq k \leq Q).
4. (25 points) P_k \neq 1. If P_k = 3, we have V_k = 1 (1 \leq k \leq Q).
5. (12 points) If P_k = 3, we have V_k = 1 (1 \leq k \leq Q).
6. (22 points) P_k \neq 1 (1 \leq k \leq Q).
7. (14 points) No additional constraints.

Sample Input 1

7
1 2 30
2 3 30
1 4 70
2 5 20
1 6 10
2 7 50
2
3
0
0
0
1
0
8
3 1
1 6 0
3 1
2 6 10
3 1
1 2 7
1 6 7
3 1

Sample Output 1

80
70
60
-1

In the festival considered in event 1, the times when the cities ignite their cauldrons are as follows:

• At time 0, cities 3,4,5,7 ignite their cauldrons.
• At time 50, city 2 ignites its cauldron. By then, the parades from cities 3,5,7 have reached city 2.
• At time 80, city 1 ignites its cauldron. By then, the parades from cities 2,4 have reached city 1.
• At time 90, city 6 ignites its cauldron. By then, the parade from city 1 has reached city 6.

Since city 1 would ignite its cauldron at time 80, output 80.

In the festival considered in event 3, the times when the cities ignite their cauldrons are as follows:

• At time 0, cities 3,4,5,6,7 ignite their cauldrons.
• At time 50, city 2 ignites its cauldron. By then, the parades from cities 3,5,7 have reached city 2.
• At time 70, city 1 ignites its cauldron. By then, the parades from cities 4,6 have reached city 1.

Since city 1 would ignite its cauldron at time 70, output 70.

In the festival considered in event 5, the times when the cities ignite their cauldrons are as follows:

• At time 0, cities 3,4,5,6,7 ignite their cauldrons.
• At time 30, city 2 ignites its cauldron. By then, the parades from cities 3,5,7 have reached city 2.
• At time 60, city 1 ignites its cauldron. By then, the parades from cities 2,6 have reached city 1.

Since city 1 would ignite its cauldron at time 60, output 60.

In the festival considered in event 8, the times when the cities ignite their cauldrons are as follows:

• At time 0, cities 3,4,5,7 ignite their cauldrons.

Cities 1,2,6 would never ignite their cauldrons. Since city 1 would never ignite its cauldron, output -1.

This sample input satisfies the constraints of Subtasks 1,3,5,7.

Sample Input 2

6
1 2 10
1 3 30
1 4 50
1 5 30
1 6 10
2
0
0
0
0
1
10
3 1
2 3 20
3 1
1 6 0
3 1
1 1 4
3 1
1 2 6
1 3 6
3 1

Sample Output 2

30
20
10
30
-1

This sample input satisfies the constraints of Subtasks 1,2,5,7.

Problem Statement

Do you know Just Odd Inventions Co., Ltd.? This company engages in nothing but just odd inventions. We abbreviate it as JOI.

In one of JOI's laboratories, there is a complicated electric circuit. The circuit consists of N nodes and M thin electric resistors. The nodes are numbered 0 through N - 1, and the resistors are numbered 0 through M - 1. Each node can be set to one of two states: high voltage or low voltage. Resistor i (0 \leq i \leq M - 1) is connected from node A_i to another node B_i. Current flows through this resistor if and only if node A_i is set to high voltage and node B_i is set to low voltage. In all other cases, no current flows through it. Also, for any two nodes, there is at most one resistor connecting them, regardless of its direction.

You are a researcher at JOI, and you are going to conduct an experiment using this circuit. The resistors in the circuit are so thin that you cannot visually determine which pairs of nodes they connect. However, there is one clue: while the voltages are being set, the temperature of the circuit rises according to the number of resistors through which current flows. Therefore, after setting the voltages, you decide to touch the circuit and read its temperature. Although you cannot measure the exact temperature of the circuit, you can perform two voltage settings and compare which one makes the circuit hotter. That is, by specifying two voltage settings, you can obtain one of the following pieces of information:

• In the first voltage setting, the number of resistors through which current flows is larger.
• In the two voltage settings, the number of resistors through which current flows is the same.
• In the second voltage setting, the number of resistors through which current flows is larger.

Your goal is to repeat such temperature comparisons and determine all resistors in the circuit, that is, all ordered pairs (a, b) such that there is a resistor from node a to node b. You are given in advance the number of nodes N and the number of resistors M. You also know that every resistor connects two distinct nodes, and that for any two nodes there is at most one resistor connecting them, regardless of direction. Under these conditions, determine the entire set of ordered pairs (a, b) corresponding to the resistors in the circuit, from the information obtained by the temperature comparisons. Note that, depending on the structure of the circuit, it may be impossible to determine the resistors uniquely no matter what comparisons are performed or how many are performed. In that case, you must report that it is impossible to determine them uniquely.

To prevent deterioration of the resistors, you are allowed to compare temperatures at most 30\,000 times.

Incidentally, what kind of invention JOI is making with this odd circuit is top secret even within the company, and nobody except the president knows it.

Given the numbers of nodes and resistors in the circuit, write a program that determines the resistors in the circuit, or reports that this is impossible, using at most 30\,000 temperature comparisons.

Implementation Details

Your submitted program must include voltage.h using the #include preprocessor directive, and must implement the following function.

• bool solve(int N, int M)
  • This function is called exactly once in each execution.
  • The argument N represents the number of nodes in the circuit, N.
  • The argument M represents the number of resistors in the circuit, M.
  • This function must return false if the resistor connections cannot be uniquely determined no matter what temperature comparisons are performed or how many are performed; otherwise, it must return true.
  • If this function returns true when the resistor connections cannot be determined uniquely, your program is judged as Wrong Answer [1].
  • If this function returns false even though the circuit can be determined from temperature comparisons, your program is judged as Wrong Answer [2].

Your program may call the following functions.

• int query(std::vector<int> x, std::vector<int> y)
  • By using this function, you can perform two voltage settings and compare their temperatures.
  • The argument x specifies the first voltage setting, and the argument y specifies the second voltage setting.
  • The arguments x and y must be arrays of length N consisting of 0's and 1's.
  • If x[k] (0 \leq k \leq N - 1) is 1, then in the first voltage setting, node k is set to high voltage; if x[k] is 0, then node k is set to low voltage.
  • If y[k] (0 \leq k \leq N - 1) is 1, then in the second voltage setting, node k is set to high voltage; if y[k] is 0, then node k is set to low voltage.
  • The return value of this function is the result of comparing the temperatures of the circuit under the first and second voltage settings, and is one of -1, 0, or 1.
    • If the return value is -1, then the number of resistors through which current flows is larger in the first voltage setting than in the second.
    • If the return value is 0, then the numbers of resistors through which current flows are equal in the first and second voltage settings.
    • If the return value is 1, then the number of resistors through which current flows is larger in the second voltage setting than in the first.
  • If the length of x is not N, your program is judged as Wrong Answer [3].
  • If x contains a value other than 0 or 1, your program is judged as Wrong Answer [4].
  • If the length of y is not N, your program is judged as Wrong Answer [5].
  • If y contains a value other than 0 or 1, your program is judged as Wrong Answer [6].
  • You must not call this function more than 30\,000 times. If this function is called more than 30\,000 times, your program is judged as Wrong Answer [7].
• void answer(int a, int b)
  • Use this function to report a resistor that you have identified.
  • The arguments a and b indicate that there is a resistor directed from node a to node b.
  • It must hold that 0 \leq a \leq N - 1 and 0 \leq b \leq N - 1. If this condition is not satisfied, your program is judged as Wrong Answer [8].
  • You must not call this function two or more times with the same pair (a, b). If this condition is violated, your program is judged as Wrong Answer [9].
  • You must not call this function more than M times. If this function is called more than M times, your program is judged as Wrong Answer [10].
  • When the function solve returns true, the function answer must have been called exactly M times by then. If this condition is not satisfied, your program is judged as Wrong Answer [11].
  • When the function solve returns true, for every pair (a, b) passed as arguments to answer up to that point, there must actually exist a resistor directed from node a to node b. If this condition is not satisfied, your program is judged as Wrong Answer [12].

Important Notices

• You may implement additional helper functions or declare global variables for internal use.
• Your submitted program must not use standard input/output or any other file interaction. However, you may use standard error output for debugging.

Compilation and Execution

You can download an archive file from the contest webpage which contains the sample grader to test your program. The archive file also contains a sample source file of your program.

The sample grader is the file grader.cpp. To test your program, place the files grader.cpp, voltage.cpp, and voltage.h in the same directory, and compile them using the following command:

g++ -std=gnu++20 -O2 -o grader grader.cpp voltage.cpp

Alternatively, you can execute the compile.sh file included in the archive by running:

./compile.sh

If compilation is successful, an executable file named grader will be generated.

Note that the actual grader is different from the sample grader. The sample grader is launched as a single process, which will read input data from the standard input and write the results to the standard output.

Input for the Sample Grader

The sample grader reads input from standard input in the following format:

N M
A_0 B_0
\vdots
A_{M-1} B_{M-1}

Output of the Sample Grader

The sample grader outputs the following information to standard output (quotation marks are not included in the actual output).

• If your program is judged as one of Wrong Answer [3] – [12], the type of Wrong Answer is printed as in "Wrong Answer [5]".
• Otherwise, the number of calls to the function query and the return value of the function solve are printed as in "Accepted: 30 true". The sample grader, unlike the actual grader, does not judge whether the verdict should be Wrong Answer [1] or [2], that is, whether the return value of the function solve is correct.

The sample grader terminates execution as soon as any of the conditions for Wrong Answer [3] – [12] is met. If multiple incorrect conditions are met, only one of them is displayed.

Notices on Grading

The actual grader is not adaptive; it has a fixed answer from the beginning of the interaction.

Constraints

• 2 \leq N \leq 600.
• 1 \leq M \leq 1\,000.
• 0 \leq A_i \leq N - 1 (0 \leq i \leq M - 1).
• 0 \leq B_i \leq N - 1 (0 \leq i \leq M - 1).
• A_i \neq B_i (0 \leq i \leq M - 1).
• (A_i, B_i) \neq (A_j, B_j) and (A_i, B_i) \neq (B_j, A_j) (0 \leq i < j \leq M - 1).
• N, M, A_i, and B_i are integers (0 \leq i \leq M - 1).

Subtasks

1. (10 points) N \leq 100, M = N - 1, B_i = A_{i+1} (0 \leq i \leq N - 3), and the N values A_0, A_1, \ldots, A_{N-2}, B_{N-2} are all distinct.
2. (12 points) M = N - 1, B_i = A_{i+1} (0 \leq i \leq N - 3), and the N values A_0, A_1, \ldots, A_{N-2}, B_{N-2} are all distinct.
3. (27 points) N \leq 100, A_i \neq A_j (0 \leq i < j \leq M - 1).
4. (18 points) A_i \neq A_j (0 \leq i < j \leq M - 1).
5. (17 points) N \leq 100.
6. (16 points) No additional constraints.

Example Interaction

Below is an example of input that the sample grader reads and the corresponding function calls.

Sample Input 1

5 6
0 2
2 1
0 3
3 2
3 4
4 1

In the first call to query, the two voltage settings and the resistors through which current flows are as follows.

• In the first setting, nodes 0 and 1 are set to low voltage, and nodes 2, 3, and 4 are set to high voltage. At this time, current flows through resistors 1 and 5.
• In the second setting, nodes 3 and 4 are set to low voltage, and nodes 0, 1, and 2 are set to high voltage. At this time, current flows through resistor 2.

Since the number of resistors through which current flows is larger in the first voltage setting, the return value is -1.

This sample input satisfies the constraints for subtasks 5, 6.

Among the files available for download from the contest site: sample-01-in.txt corresponds to Sample Input 1. Additionally, sample-02-in.txt satisfies the constraints for all subtasks, and sample-03-in.txt satisfies the constraints for subtasks 3, 4, 5, 6.