Askhat is a prospective businessman. He quickly figured that programming is an unprofitable business, so he decided to open a chicken farm.

His farm consists of $$$n$$$ chickens ordered in a row. The $$$i$$$-th chicken can eat at most $$$a_i$$$ grains. There are $$$m$$$ feeders, each described by integers $$$l_j$$$, $$$r_j$$$, $$$c_j$$$. The $$$j$$$-th feeder can feed the $$$i$$$-th chicken if $$$l_j \le i \le r_j$$$, and there are $$$c_j$$$ grains in this feeder.

Turns out that every business has its own pitfalls, in this case it has the face of chicken feeding control, represented by Ildar. He claims that every respectable chicken farm must have a chicken representative. That is, there must exist a chicken $$$i$$$ such that $$$l_j \le i \le r_j$$$ holds for every feeder $$$j$$$. All feeders that don't obey this rule must be exterminated.

Now Askhat asks you to find, for each $$$i$$$, what is the maximum number of grains that can be fed to chickens if we leave only feeders that can feed chicken $$$i$$$.

You are given $$$n$$$ segments $$$[l_i,r_i]$$$ ($$$1 \le l_i \le r_i \le m$$$). Each segment has a weight $$$c_i$$$.

Let us choose a subsequence of segments, from each chosen segment choose an integer and arrange them in the same order as initial segments. By this operation we will get an integer sequence. We say that a subsequence of segments is good if we can construct a nondecreasing integer subsequence from it.

Let $$$k$$$ be the maximum weight of a good subsequence (the sum of weights of all segments in the subsequence). Calculate $$$k$$$ and the number of good subsequences of weight $$$k$$$. Since the number of subsequences can be large, calculate it modulo $$$998\,244\,353$$$.

Maksim, a well-known computer scientist in the field of networking, came up with a new protocol that Ramazan suggested to call cerr_maksim.

For simplicity, let us say that there are two computers in the network, and they are connected with a wire of throughput $$$w$$$. Files are being transferred from the first computer to the second computer. Transferring a file of size $$$s$$$ takes $$$\frac{s}{w}$$$ seconds.

There are $$$n$$$ files to be transferred, each has a moment $$$t_i$$$ when it starts being transferred, size $$$s_i$$$ and priority $$$p_i$$$. If multiple files are being transferred simultaneously, then wire's throughput is divided between transfers proportionally to their priorities.

For each file, calculate the moment when it will reach the second computer.

You are given an integer array $$$a_1, \ldots, a_n$$$. A subsegment of even length $$$a_i,\ldots, a_{i + 2m - 1}$$$ is called good if $$$\left|\max(a_i,\dots, a_{i + m - 1}) - \max(a_{i + m}, \ldots, a_{i + 2m - 1})\right| \leq k$$$.

Let us define an integer sequence $$$f$$$ as follows:

• $$$f_1 = 3240$$$
• $$$f_2 = 3081$$$
• $$$f_3 = 2841$$$
• $$$f_4 = 343$$$
• $$$f_i = f_{i-1} \cdot 223 + f_{i-2} \cdot 229 + f_{i-3} \cdot f_{i-4} \cdot 239 + 17$$$ for $$$i \gt 4$$$

Calculate the sum $$$(a_{i+m-1} + 10) \cdot f_{m}$$$ among all good subsegments. Since this number can be large, print it modulo $$$998\,244\,353$$$.

You are given a string $$$s$$$ consisting of lowercase English letters.

Let us consider a segment $$$[\ell, r]$$$ such that $$$2 \leq \ell \leq r \leq |s|$$$. Let us define $$$f(\ell, r)$$$ as the length of the longest suffix of substring $$$s[1, \ell-1]$$$ such that this suffix can be divided into prefixes of substring $$$s[\ell, r]$$$. If there are no such suffixes then $$$f(\ell, r) = 0$$$.

Find the sum $$$\displaystyle \sum\limits_{\ell=2}^{|s|} \sum\limits_{r=\ell}^{|s|} f(\ell, r)$$$.

Let us recall a well-known problem (also called a "bayan" in Russian). You are given an array $$$a_1, a_2, \ldots, a_n$$$ of integers. Answer the queries: given a segment $$$[l, r]$$$ ($$$1 \leq l \leq r \leq n$$$), check if there exist two equal elements among $$$a_l, a_{l+1}, \ldots, a_r$$$.

Please help to make good tests for this well-known problem! You are given two integers $$$n$$$, $$$m$$$, and also $$$2m$$$ different segments $$$[l_i, r_i]$$$. Find any array $$$a_1, a_2, \ldots, a_n$$$ such that, for exactly $$$m$$$ queries, the answer is positive, and for exactly $$$m$$$ queries, the answer is negative. You should report if there is no such array.

This is an interactive problem.

Ivan came up with new rules for the battleship game!

• The game will be played on an $$$n \times n$$$ board.
• The first player chooses an integer $$$k$$$ ($$$n \leq k \leq {\left\lceil \frac{n}{2} \right\rceil}^2$$$).
• After that, the first player places $$$k$$$ ships on the board so that the number of cells occupied by the ships is the maximum possible (among all valid placements of $$$k$$$ ships of any sizes).
• Each ship should be a rectangle of size $$$1 \times a$$$ or $$$a \times 1$$$ ($$$a$$$ is any integer from $$$1$$$ to $$$n$$$ inclusive). Any two ships should not have neighbouring cells (by side or by corner).

After that, the second player starts his game.

• The second player knows only the size of the board $$$n$$$.
• The second player can ask a query: is cell $$$(x, y)$$$ occupied by some ship?
• The second player should find any empty $$$2 \times 2$$$ square on the board, or say that there are no such squares.

The second player can ask at most $$$6n$$$ queries. Please play as the second player and win the game!

The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 100$$$) — the number of games to be played. You should play $$$t$$$ games and finish interaction after that.

At the start of the game, you are given a single integer $$$n$$$ ($$$3 \leq n \leq 1000$$$) — the size of the board.

After that, you can ask some queries. To ask a query, print a single line "? $$$x$$$ $$$y$$$" ($$$1 \leq x, y \leq n$$$) — the coordinates of the cell. You will be given an answer $$$c$$$:

• If $$$c = -1$$$, you made too many queries. You should terminate your program.
• If $$$c = 0$$$, the cell $$$(x, y)$$$ is empty.
• If $$$c = 1$$$, the cell $$$(x, y)$$$ is occupied by some ship.

To finish the game, print a single line "! $$$x$$$ $$$y$$$", where:

• $$$x=-1$$$, $$$y=-1$$$ if there are no empty $$$2 \times 2$$$ squares on the board.
• Otherwise, $$$1 \leq x, y \leq n - 1$$$ and the square with cells $$$(x, y)$$$, $$$(x+1, y)$$$, $$$(x, y+1)$$$, $$$(x+1, y+1)$$$ is empty.

If your answer is incorrect, you will be given a line with value -1, and you should terminate your program. Otherwise, you will be given a line with value 1, and you should play the next game (or finish your program if it was the last game).

It is guaranteed that the sum of $$$n$$$ for all games does not exceed $$$5000$$$.

It is guaranteed that the board in each game is fixed, and the interactor is not adaptive.

Your solution will get Idleness Limit Exceeded if you don't print anything or forget to flush the output.

You are given a simple connected undirected graph that is a cactus: each edge lies on at most one simple cycle. This cactus is triangular: the length of any simple cycle is at most $$$3$$$.

Answer the queries. In each query, you are given two vertices $$$s$$$ and $$$f$$$, and an integer $$$k$$$. Find the number of simple paths between vertices $$$s$$$ and $$$f$$$ with length exactly $$$k$$$. You should find this number modulo $$$998\,244\,353$$$.

The path is simple if all its vertices are different, the length of the path is equal to the number of edges on the path.

Ivan likes painting. He decided to paint a sun.

To do that, he took $$$n$$$ points with integer coordinates on the plane. Ivan will draw segments connecting some pairs of points to get the best sun.

• Ivan will connect exactly $$$n$$$ pairs of points with segments between them.
• All segments should not intersect (except for endpoints).
• There should be exactly one cycle. This cycle should be a convex polygon.
• Each point that is not one of the polygon vertices should lie outside of the polygon and should be connected with one of the polygon's vertices.
• It is possible that all vertices will lie on the cycle.

Ivan wants to paint a bright, pretty sun. So he came up with the score of the sun:

• Let us define $$$S$$$ as the area of the polygon.
• Let us define $$$P$$$ as the sum of lengths of all drawn segments.
• The value $$$\displaystyle \frac{S}{P}$$$ is the score of the sun.

What is the maximum possible score of the sun?

Let us consider a square city of size $$$k \times k$$$. There is exactly one house in each cell.

People can go from any cell to neighbouring cell (only by side) in $$$1$$$ unit of time.

Government decided to build $$$n$$$ fast bridges to make the city better. Each fast bridge connects two cells $$$(x_1, y_1)$$$ and $$$(x_2, y_2)$$$ such that $$$x_1 \neq x_2$$$ and $$$y_1 \neq y_2$$$. People can go from one end of the bridge to another in $$$|x_1 - x_2| + |y_1 - y_2| - 1$$$ units of time.

To analyze how the city became faster, you are asked to calculate the sum of shortest distances between all pairs of cells. Since it can be large, find it modulo $$$998\,244\,353$$$.

Aliens connected with people and sent a message containing the answer to "The Ultimate Question of Life, the Universe, and Everything".

People received $$$n$$$ bytes (integers from $$$0$$$ to $$$255$$$ inclusive). The decoding algorithm is the following:

• Let us consider all $$$n!$$$ permutations of received bytes.
• Consider each permutation as a number written in base $$$256$$$. Numbers can be equal.
• Multiply all these numbers modulo $$$65\,535$$$.
• The result is the decoded message!

For each byte $$$i$$$, you are given the number $$$c_i$$$ of received bytes $$$i$$$. Please decode the message.