Walk Alone has a sequence $$$a_1,a_2,...,a_n$$$, and he can use a magic on it:

• Choose an odd prime number $$$p$$$ and an interval $$$[l, r] \subseteq [1,n]$$$ satisfying $$$r-l+1=p$$$ , and then add $$$1$$$ or $$$-1$$$ to every $$$a_i$$$ in this interval. That is, choose $$$x\in \{1, -1\}$$$, then $$$\forall i \in [l, r], a_i \leftarrow a_i+x$$$.

Remind that odd prime is numbers that are odd greater than $$$1$$$ and can only be divided by $$$1$$$ and itself.

Walk Alone likes growing things, so he wants to use this magic to make this sequence non-decreasing. Besides, Walk Alone doesn't like negative numbers, so during the whole operations any number cannot be negative.

He wants to accomplish this idea with minimal number of magic usage. Although Walk Alone has this magic, he doesn't know in which order to use it, so he asks you for help.

Walk Alone likes to go with the flow, so he designs a function on digits about mode.

Let $$$f(x)$$$ be the maximal occurrence among the digits in decimal expression of the number $$$x$$$. For example, $$$f(133)=2$$$ since digit $$$3$$$ occurs twice, while $$$f(213)=f(0)=1$$$ since every digit appears exactly once in both numbers. Walk Alone gives you a task to calculate the range sum of function $$$f$$$, i.e. $$$\sum_{i=l}^r f(i)$$$.

Princess Celestia, is an Alicorn pony, the former co-ruler of Equestria alongside her younger sister Princess Luna. Princess Celestia raises the sun and governs Equestria, while Princess Luna raises the moon and oversees the realm of dreams.

In early days, Luna felt overshadowed and ignored by the ponies of Equestria, who slept through her beautiful night sky. These negative emotions festered and eventually led her to be consumed by the darkness and power of the mythical creature known as Nightmare Moon.

The darkness was spreading, and could be transformed into the following model:

In an $$$n\times m$$$ white 2D grid, there are several black grid points.

Every second, all white points that are 4-neighbors of at least two black points will turn black.

What is the minimum number of black points needed to turn the entire grid black in the end?

Princess Celestia and Princess Luna argued, and the spreading darkness could be transformed into the following model:

In an infinitely large white 2D grid, there are initially $$$n$$$ black grid points.

Every second, all white points that are 4-neighbors of at least two black points will turn black.

What is the total number of black points in the end?

Walk Alone is an expert in dynamic programming, but he gets bored with traditional dynamic programming problem like counting paths on a 2-dimension grid, so he wants to do it in reverse. The problem he raised is as follows:

On a 2-dimension grid of size $$$n \times n$$$, originally you are on grid $$$(1,1)$$$. The grid consists of $$$0$$$ and $$$1$$$, and you can only walk on the grid with number $$$1$$$ in it. You can only go down or right, i.e. you can only increase your $$$x$$$ or $$$y$$$ by one. Also you cannot walk outside the grid.

Given the number $$$x$$$ of ways to walk from $$$(1,1)$$$ to $$$(n,n)$$$, you need to construct a grid of $$$n \times n$$$ so that the ways to walk is exactly $$$x$$$. However, since Walk Alone's brain is too small to memorize such a big grid, you need to guarantee that the size of the grid $$$n$$$ is equal to or smaller than $$$30$$$.

Walk Alone is an expert in strings, but he gets bored with traditional algorithms like Manacher, so he wants to do it in reverse. The problem he raised is as follows:

There's a hidden string $$$S$$$ only consisting character 'a' and 'b'. You are given $$$n$$$–the length of the string. Then the string $$$S$$$ is transformed as follows:

• First, add two character $$$\&|$$$ to the beginning of the string.
• Second, for every character in the original string, add a character $$$|$$$ to the right of it.

For example, string $$$abaaa$$$ is transformed into $$$\&|a|b|a|a|a|$$$, and string $$$aaaaa$$$ is transformed into $$$\&|a|a|a|a|a|$$$. After this operation, the length of the string $$$S$$$ has become $$$2n+2$$$. Let the transformed string be $$$T$$$.

He then will give you a sequence $$$\{a_n\}$$$ of length $$$2n+2$$$, the $$$i$$$-th of which denotes the maximal length of palindrome centered at the $$$i$$$-th character. Formally, $$$a_i=j$$$ where $$$j=\max\{x|x \in \mathbb{N}^*, \forall y \le x, T_{i-y+1}=T_{i+y-1}\}$$$. For example, the original string $$$abaaa$$$ can generate the final sequence $$$\{1,1,2,1,4,1,2,3,4,3,2,1\}$$$. Note that every character in the string is compared through ASCII code, so character $$$\&$$$ cannot be in pair with any other character.

Your work is to restore the string $$$S$$$ using sequence $$$\{a_n\}$$$.

This is an interactive problem.

There is a hidden polynomial $$$f(x)=\sum_{i=1}^n a_i\cdot x^{p_i}$$$ where $$$0\le n\le 10^3,1\le a_i\le 10^5$$$, $$$0\le p_i\le 8\cdot 10^6$$$, and $$$p_1,p_2,\dots,p_n$$$ are pairwise distinct.

You can query in the format "$$$?\ x$$$", and the interactor will respond you $$$f(x)\bmod 998\,244\,353$$$.

You need to find the function by no more than $$$2\cdot 10^4$$$ queries.

You can make no more than $$$2\cdot 10^4$$$ queries to guess the polynomial. To make a query, output "$$$?\ x$$$" $$$(0\le x \lt 998\,244\,353)$$$ on a separate line, then you should read the response from standard input.

To give your answer, firstly print "$$$!\ n$$$" on a separate line, where $$$n$$$ indicates the number of monomials. For each monomial $$$a_i\cdot x^{p_i}$$$, print "$$$p_i\ a_i$$$" on a separate line. You can print the $$$n$$$ monomials in an arbitrary order. The output of the answer is not counted towards the limit of $$$2\cdot 10^4$$$ queries.

After that, your program should terminate.

After printing a query, do not forget to output end of line and flush the output. To do this, use fflush(stdout) or cout.flush() in C++, System.out.flush() in Java, flush(output) in Pascal, or stdout.flush() in Python.

It is guaranteed that the polynomial is fixed in advance.

Walk Alone has a graph of $$$n$$$ nodes and $$$m$$$ bi-directional edges. He defines a function of $$$f(u, v)=(\deg_u \oplus \deg_v)(\deg_u | \deg_v)(\deg_u \& \deg_v)$$$, where $$${\rm deg}_u$$$ denotes the number of edges that associated with node $$$u$$$, and $$$\oplus, |, \&$$$ denotes bitwise xor, bitwise or and bitwise and. He wants you to calculate $$$\left(\sum_{i=1}^n \sum_{j=i}^n f(i, j)\right) \bmod 998\ 244\ 353$$$.

You are given $$$n$$$ rings, and the length of the $$$i$$$-th ring is $$$p_i(1\le i \le n)$$$. For the $$$i$$$-th ring, the next position of $$$p_i$$$ is $$$1$$$. At the very beginning, there is a pony at position $$$1$$$ of each ring, and the ponies move faster and faster every day.

Specifically, a pony moves $$$1$$$ step on the first day, and $$$2$$$ steps on the second day, and so on. Formally, the pony will move $$$k$$$ steps on the $$$k$$$-th day for $$$k \in \mathbb{N}^*$$$.

It is clear that on a certain day, all the ponies will arrive at position $$$1$$$. Now Miku wants to know the earliest day $$$m$$$ (except day $$$0$$$) when all the $$$n$$$ ponies will arrive at position $$$1$$$.

Applejack is a female Earth pony. She lives and works at Sweet Apple Acres with her grandmother Granny Smith, her older brother Big McIntosh, her younger sister Apple Bloom, and her dog Winona. She represents the element of honesty.

Now Applejack is going to cultivate a row of wasteland, and it could be transformed into the following model:

There are $$$n$$$ cells in a row, each containing an integer $$$a_i$$$. Applejack start by cultivating cell number $$$1$$$ and have $$$0$$$ resources just before the end of time unit 1.

Later, assuming Applejack have cultivated cells $$$[1, x]$$$, at the beginning of each unit time, she can cultivate cell $$$x+1$$$, and at the end of each unit time, she obtain resources equal to the sum of integers on all cells she have cultivated.

Applejack need to ensure that she always have non-negative resources(even after cultivating all cells). What is the minimum time needed to occupy all cells, or is it impossible?

There are $$$n+1$$$ people playing a game with dice. Every person has a dice of $$$m$$$ faces, each of which is equal-probability. Don't spend time wondering how this kind of dice can exist–You can image a generator which can generate numbers among $$$[1,m]$$$ with equal-probability.

At the beginning, each person throws his own dice, and the person with the smallest number of points loses. If more than one person throws the smallest number of dice at the same time, those who have thrown the smallest number of dice continue to throw dice until finally one person loses.

Walk Alone doesn't like randomness. He uses magic to fix the points the first person throws every time. That is, the first person will always throw $$$x$$$ points when the first person throws his dice, where $$$x$$$ is pre-chosen by Walk Alone, while other $$$n$$$ people still throw their dices randomly.

Now Walk Alone wants to know for every $$$x \in [1, m]$$$, the probability the first person will lose.

To be more precise, you need to output the probability modulo $$$998\ 244\ 353$$$. It can be proven that the probability can be presented as a fraction $$$\frac{p}{q}$$$. You need to output $$$p\cdot q^{998\ 244\ 351} \bmod 998\ 244\ 353$$$.

Sweetie Drops, or Bon Bon, is a female Earth pony with a cutie mark of three candies. Lyra Heartstrings, is a female unicorn pony with a cutie mark of a lyre.

They always appear together in TV show as background characters. In The Last Problem, Lyra is shown in newspaper as having gotten married to Sweetie Drops.

The fans use LyraBon as the femslash ship between Lyra Heartstrings and Sweetie Drops.

Today they are playing a black-white game, the game progresses turn by turn, Bon Bon moves first.

Initially, there are $$$n+1$$$ points connected by either white or black edge in a row. In one move a pony must choose at least two points and then do some removal.

More specific, Bon Bon can choose some consecutive points without black edge between any two of them, and then remove these points and all edge(s) connected to them. Be attention that black edge may be removed in the process.

Similarly, Lyra can choose consecutive points without white edge and then do removal in same way.

It is required that after either Bon Bon or Lyra's removal, the points must not be split into two separate blocks.

The pony who cannot make a move loses. If both ponys play optimally, could Bon Bon ultimately win the game?

Once upon a time, there was an onsite programming contest, which had attracted many teams to participate in. However, different teams had a different billing standard. In general, there were three types of teams:

• Teams of Type A could participate in the contest for free.
• Teams of Type B had to pay $$$1000$$$ dollars for the expenses for board and lodging.
• Teams of Type C had to pay $$$1000$$$ dollars for the expenses for board and lodging and $$$1500$$$ dollars for entry fee.

Finally the contest was held successfully with $$$x$$$ teams in total participating in, and the host had earned $$$y$$$ dollars. However, the details about the number of teams of each type had vanished. Now Walk Alone wants to restore the details using $$$x$$$ and $$$y$$$.