You are to hold a cookie party! You have prepared $$$N$$$ cookies numbered from $$$1$$$ through $$$N$$$. The **sweetness** of the cookie $$$i$$$ is $$$A_i$$$. You expect that $$$M$$$ children numbered from $$$1$$$ to $$$M$$$ will attend the party. All of them will bring their homemade cookies, and the child $$$i$$$ will bring a cookie of sweetness $$$B_i$$$. Besides, you know the taste preference of each child. The child $$$i$$$ loves sweet cookies if $$$S_i=$$$'S' and loves bitter cookies if $$$S_i=$$$'B'.

The party will proceed in the following manner:

• First, you are given an integer $$$k$$$ and put cookies $$$1,2,\cdots,k$$$ on the table.
• Then, children $$$1,2,\cdots,M$$$, in this order, come to the table. When the child $$$i$$$ comes to the table, the child first put his/her homemade cookie on the table. Then, if the child loves sweet cookies, he/she eats the sweetest cookie (a cookie with the largest sweetness) on the table. If the child loves bitter cookies, he/she eats the bitterest cookie (a cookie with the smallest sweetness) on the table. Note that each child eats exactly one cookie, and a child may eat his/her cookie.
• Finally, you eat all the cookies left on the table.

You have not yet decided the value of $$$k$$$. For each integer $$$k=1,2,\cdots,N$$$, find the sum of the sweetness of cookies you will eat.

Note that only after you get the answer for $$$k=i$$$ can you know the value of $$$A_{i+1}$$$. See the input section for more details.

There are $$$N+2$$$ towns in a straight line. The towns are numbered from $$$0$$$ through $$$N+1$$$ from left to right. Each town $$$i$$$ ($$$1 \leq i \leq N$$$) has a shelter which can contain up to $$$A_i$$$ people.

Currently, $$$S$$$ people are traveling together and visiting one of the towns. However, you don't know which town they are visiting.

You just got to know that there are $$$Q$$$ meteorites that can hit the towns. The $$$i$$$-th meteorite may strike towns $$$L_i,L_i+1,\cdots,R_i$$$. To ensure the safety of the travelers, for each meteorite, you want to calculate the **evacuation cost**.

The evacuation cost for a meteorite is calculated as follows:

• The evacuation cost is the minimum total cost needed to make all travelers **safe** no matter which town they are visiting.
• A person is safe if he/she is in a shelter or a town outside the effect of the meteorite.
• It takes $$$1$$$ unit cost to move one person to an adjacent town (two towns are adjacent iff their numbers differ by exactly $$$1$$$).

Note that only moving people costs money, and other actions (like accommodating people in a shelter) don't. It is guaranteed that towns $$$0$$$ and $$$N+1$$$ will never be affected by meteorites, so it is always possible to make all travelers safe.

Write a program that, for each meteorite, calculates the evacuation cost for that meteorite.

Snuke found a random number generator. It generates an integer between $$$1$$$ and $$$N$$$ (inclusive). An integer sequence $$$A_1, A_2, \cdots, A_N$$$ represents the probability that each of these integers is generated. The integer $$$i$$$ ($$$1 \leq i \leq N$$$) is generated with probability $$$A_i / S$$$, where $$$S = \sum_{i=1}^{N} A_i$$$. The process of generating an integer is done independently each time the generator is executed.

Snuke has an integer $$$X$$$, which is now $$$0$$$. He can perform the following operation any number of times:

• Generate an integer $$$v$$$ with the generator and replace $$$X$$$ with $$$X + v \mod M$$$.

Find the expected number of operations until $$$X$$$ becomes $$$K$$$, and print it modulo $$$998244353$$$. More formally, represent the expected number of operations as an irreducible fraction $$$P/Q$$$. Then, there exists a unique integer $$$R$$$ such that $$$R \times Q \equiv P \mod 998244353,\ 0 \leq R \lt 998244353$$$, so print this $$$R$$$.

We can prove that the expected number of operations until $$$X$$$ becomes $$$K$$$ is a finite rational number. However, we did **not** prove its integer representation modulo $$$998244353$$$ can be defined. Our sincerest apologies. Nonetheless, you don't have to worry about division by $$$0$$$. More precisely, We can model this problem as an absorbing markov chain( https://en.wikipedia.org/wiki/Absorbing_Markov_chain), and we guarantee that in all tests, the corresponding fundamental matrices can be defined modulo $$$998244353$$$.

Determine whether there exists a sequence of $$$N$$$ nonnegative integers $$$a_1,a_2,\cdots,a_N$$$ that satisfies all of the following conditions, and if it exists, find the minimum possible value of the maximum of the array.

• $$$a_1+a_2+\cdots+a_N=S$$$
• $$$a_1 \oplus a_2 \oplus \cdots \oplus a_N=X$$$ (Here $$$\oplus$$$ denotes bitwise xor operation)

Note that there are $$$T$$$ tests in one input file.

You are given $$$K$$$ distinct nonnegative integers $$$A_1,A_2,\cdots,A_K$$$. Count the number of sequences of $$$N$$$ nonnegative integers $$$a_1,a_2,\cdots,a_N$$$ that satisfies all of the following conditions, modulo **$$$2$$$**.

• $$$a_1+a_2+\cdots+a_N=S$$$
• For each $$$i$$$ ($$$1 \leq i \leq N$$$), there exists an integer $$$j$$$ such that $$$a_i=A_j$$$.

Note that there are $$$T$$$ tests in one input file.

There are $$$N$$$ robots numbered from $$$1$$$ through $$$N$$$ and $$$N$$$ antennas numbered from $$$1$$$ through $$$N$$$ in a straight line. The coordinate of the robot $$$i$$$ is $$$a_i$$$ and the coordinate of the antenna $$$i$$$ is $$$b_i$$$. All coordinates are distinct.

Currently, all antennas are inactive. You are going to activate them one by one. When you activate an antenna, the nearest robot (if two robots are closest to it, only the left one) moves to the antenna and explodes along with it.

Find an order to activate antennas so that the total distance of robots' moves is minimum possible.

You have an $$$N$$$ by $$$N$$$ grid board, which is initially empty. You will write an integer to each cell, using each integer from $$$1$$$ to $$$N^2$$$ exactly once. Let $$$M_{i,j}$$$ be the integer written on the cell in the $$$i$$$-th row from the top and the $$$j$$$-th column from the left.

Let's define sequences $$$A$$$ and $$$B$$$ as follows:

• $$$A = M_{1,1}, M_{1,2}, \dots, M_{1,N}, M_{2,1}, M_{2,2}, \dots, M_{2,N}, \dots, M_{N,N}$$$
• $$$B = M_{1,1}, M_{2,1}, \dots, M_{N,1}, M_{1,2}, M_{2,2}, \dots, M_{N,2}, \dots, M_{N,N}$$$

For example, when the board looks like this,

1 3 4

2 7 6

9 8 5

$$$A$$$ and $$$B$$$ are defined as follows.

• $$$A = 1,3,4,2,7,6,9,8,5$$$
• $$$B = 1,2,9,3,7,8,4,6,5$$$

You are given integers $$$N, X, Y$$$. Find a way to fill in the cells so that the inversion numbers of $$$A$$$ and $$$B$$$ are $$$X$$$ and $$$Y$$$ respectively, or report that it is impossible to do so.

Note: an inversion number of a sequence $$$C = c_1, c_2, \dots, c_{N \times N}$$$ is the number of pairs $$$(i, j)$$$ s.t. both $$$i \lt j$$$ and $$$c_i \gt c_j$$$ are satisfied.

Construct four points $$$a,b,c$$$ and $$$d$$$ on the two-dimensional plane that satisfy the following conditions:

• $$$x$$$ and $$$y$$$ coordinates of all points are integers, and their absolute values don't exceed $$$10^9$$$
• $$$a$$$ and $$$b$$$ are different, and $$$c$$$ and $$$d$$$ are different.
• Let $$$l$$$ be the line passing through $$$a$$$ and $$$b$$$, and let $$$m$$$ be the line passing through $$$c$$$ and $$$d$$$. Then,
  • $$$l$$$ and $$$m$$$ are not parallel.
  • the absolute values of $$$x$$$ and $$$y$$$ coordinates of the cross point of $$$l$$$ and $$$m$$$ are not less than $$$10^{27}$$$.

You are given a positive integer $$$N$$$. Construct a sequence of permutations of $$$(1,2,\cdots,N)$$$, $$$p_1,p_2,\ldots,p_K$$$, that satisfy following conditions, or report that it's impossible.

• $$$0 \leq K \leq \lceil \log_2 N \rceil + 1$$$, where $$$K$$$ is the length of the sequence.
• $$$p_1,p_2,\ldots,p_K$$$ are permutations of $$$(1,2,\ldots,N)$$$. In other words, they are bijections from $$$\{1,2,\ldots,N\}$$$ to $$$\{1,2,\ldots,N\}$$$.
• For all $$$x$$$ and $$$y$$$ ($$$1 \leq x,y \leq N$$$), there is a sequence of bijections $$$q_1,q_2,\ldots,q_K$$$ such that $$$(q_K \circ q_{K-1} \circ \cdots \circ q_1)(x) = y$$$ and $$$q_i=p_i$$$ or $$$p_i^{-1}$$$ for all $$$i$$$.

Here, $$$\circ$$$ denotes function composition, and when $$$K=0$$$, $$$q_K \circ q_{K-1} \circ \cdots \circ q_1$$$ is defined as an identity function.

Do you know this problem(https://atcoder.jp/contests/agc022/tasks/agc022_e)? We generalize it a bit.

You got a binary string $$$P = P_0P_1P_2P_3P_4P_5P_6P_7$$$ of length $$$8$$$.

You think a binary string $$$X$$$ of odd length $$$N$$$ is beautiful if it is possible to apply the following operation $$$\frac{N-1}{2}$$$ times so that the only character of the resulting string is '1' :

• Choose three consecutive bits of $$$X$$$, $$$(X_i,X_{i + 1},X_{i + 2})$$$, and replace them by the $$$(X_i + 2X_{i + 1} + 4X_{i + 2})$$$-th bit of $$$P$$$.

Note that, when $$$P = 00010111$$$, this definition is the same as the original AGC problem.

You have a string $$$S$$$ consisting of characters '0', '1', and '?'. You want to know the number of ways to replace the question marks with '1' or '0' so that the resulting string is beautiful, modulo $$$10^9 + 7$$$.

Note that there are $$$T$$$ tests in one input file.

Alice and Bob are going to play a game. The rule of the game is as follows:

• There are some monsters, each of which has a specified HP.
• Alice and Bob take turns alternately, with Alice going first.
• In Alice's turn, she chooses one of the monsters and increases its HP by $$$1$$$.
• In Bob's turn, he chooses one of the monsters and decreases its HP by $$$2$$$. If the monster's HP becomes $$$0$$$ or less, the monster disappears.
• The game ends when $$$k$$$ monsters disappear.

Alice's objective is to finish the game as late as possible, while Bob's is as soon as possible.

Initially, there are no monsters. You have to process $$$Q$$$ queries of the following types:

• Type $$$1$$$: You are given two integers $$$X_i$$$ and $$$Y_i$$$. After this query, the number of monsters whose HPs are $$$X_i$$$ becomes $$$Y_i$$$.
• Type $$$2$$$: Given an integer $$$K_i$$$, calculate how many turns would Bob take if the game started with current monsters and $$$k=K_i$$$, assuming both players play optimally.

Note that the game doesn't happen in reality, and the monsters don't disappear.

Can you replicate my master thesis in 5 hours?

You are given $$$N$$$ red points and $$$N$$$ blue points on a two dimensional plane. The $$$i$$$-th red point's coordinate is $$$(r^x_i, r^y_i)$$$, and its weight is $$$r^w_i$$$. The $$$i$$$-th blue point's coordinate is $$$(b^x_i, b^y_i)$$$, and its weight is $$$b^w_i$$$.

Process $$$Q$$$ queries. In the $$$i$$$-th query, you are given two integers $$$L_i$$$ and $$$R_i$$$, and choose a red point $$$j$$$ and a blue point $$$k$$$ with following conditions:

• $$$r^y_j \lt b^y_k$$$
• ($$$r^x_j \lt L_i$$$ and $$$R_i \lt b^x_k$$$) or ($$$L_i \lt r^x_j$$$ and $$$b^x_k \lt R_i$$$)

Your task is to maximize the sum of weights of the two points or report that it is impossible to select two points.