Sunny has been practicing his violin a lot, preparing for his recital with his older sister Mari; his violin has $$$2\times 10^{18} +1$$$ micro-strings indexed from $$$-10^{18}$$$ to $$$10^{18}$$$ from left to right.

There are $$$n$$$ vibrations on the strings; the $$$i$$$-th vibration $$$(1 \le i \le n)$$$ is located on the string with index $$$a_i$$$. No two vibrations are located on the same string. Since Sunny has been practicing a lot, he can precisely choose one string $$$k$$$ $$$(-10^{18} \le k \le 10^{18})$$$ and play a note on it.

When Sunny plays a note on string $$$k$$$, every vibration existing to the right of this string gets shifted to the next string to its right, and every vibration to the left of this string gets shifted to the next string to its left, and if a vibration exists on string $$$k$$$, it stays on string $$$k$$$. More formally, when Sunny hits string $$$k$$$, the following happens simultaneously for each vibration $$$i$$$:

1. If $$$a_i \gt k$$$, $$$a_i := a_i + 1$$$ (increase $$$a_i$$$ by one).
2. Otherwise, if $$$a_i \lt k$$$, $$$a_i := a_i - 1$$$ (decrease $$$a_i$$$ by one).
3. Otherwise, do nothing.

Now, Mari wants Sunny to make the vibrations on the violin have indices $$$b_1, b_2, ..., b_n$$$; since Sunny wants to make his sister feel proud, he wants to know if it is possible to change the initial positions $$$a$$$ of the $$$n$$$ vibrations to the desired positions $$$b$$$. Sunny can play an arbitrary number of notes (including not playing any note).

School is starting, and Aubrey is excited for the activities she is going to perform at school. During the break, Aubrey enjoys her favorite hobby of hunting sprout moles.

The school yard has a tree containing $$$n$$$ nodes rooted at some node (let that node be $$$r$$$). The $$$i$$$-th $$$(1 \le i \le n)$$$ node has $$$a_i$$$ sprout moles. Aubrey starts her hunt by choosing a node $$$i$$$, and then chooses a subset of nodes in the subtree of node $$$i$$$, and starts hunting the sprout moles in each node in the chosen subset.

When Aubrey hunts a group of $$$a_i$$$ sprout moles in a single node $$$i$$$, her hunting score gets XORed by $$$a_i$$$, and Aubrey initially has a hunting score of $$$0$$$.

Now consider the set of all possible distinct final scores Aubrey can achieve by choosing a subset of nodes from the subtree of node $$$i$$$, name it $$$S_i$$$. $$$f(i)$$$ is equal to the summation of the elements of $$$S_i$$$.

Now Aubrey does not know where the tree is rooted at, so she wants to know, from every root $$$r$$$ from $$$1$$$ to $$$n$$$ inclusive, what is the summation of $$$f(i)$$$ over all nodes $$$i$$$ $$$(1 \le i \le n)$$$ assuming the tree is rooted at $$$r$$$? Since $$$\displaystyle\sum_{i=1}^n f(i)$$$ can be very large, Aubrey wants to find its value modulo $$$998244353$$$.

After achieving the title "Employee of the Month" three times, Mr. Jawsum promoted Hero to "Manager of Cryptocurrencies" as a reward for his hard work. Hero then found an opportunity to earn money using a new coin called "NEAR".

To gain NEAR, you need to work on some tasks related to training "Artificial Intelligence" to solve problems related to "Competitive Programming"; there are $$$n$$$ types of tasks to work on, the $$$i$$$-th type of tasks $$$(1 \le i \le n)$$$ has a "Profit value" equal to $$$a_i$$$.

Since Hero is currently the "Manager of Cryptocurrencies", he has enough power to hire people to work for him. Due to "The Last Resort" policies, the employees he hires can only work in a specific range $$$[l, r]$$$, meaning they can only work on tasks of type $$$i$$$ such that $$$(l \le i \le r)$$$.

The way Hero hires employees is as follows: he first chooses a range $$$[l, r]$$$ $$$(1 \le l \le r \le n)$$$, and then hires $$$\frac{x(x+1)}{2}$$$ employees such that $$$x$$$ is equal to the size of the range $$$(r - l + 1)$$$; he hires each of the $$$\frac{x(x+1)}{2}$$$ to work on all distinct sub-ranges in the range $$$[l, r]$$$. If an employee works on a range $$$[L, R]$$$, the total amount of money he achieves after working for one day is equal to $$$\text{LCM}(a_L, a_{L+1}, a_{L+2}, ..., a_{R-1}, a_R) \times L \times R$$$ worth of NEAR, where $$$\text{LCM}$$$ is the Least Common Multiple.

At the end of the day, Hero collects all money gained from all of his hired employees. Now since Hero wants to maximize his profit, he thought that he needed to choose the whole array of types of tasks as the initial range he hires people in. But he forgot that in "Dreamspace", every bank account has a limit of $$$998244352$$$ NEAR coins. When the number of coins in an account exceeds that number, it overflows and bounces back to $$$0$$$ NEAR coins. So the actual profit Hero gets is equal to the gained profit taken under modulo $$$998244353$$$.

Hero chose $$$Q$$$ candidate ranges as initial ranges to hire people in; the $$$j$$$-th $$$(1 \le j \le Q)$$$ range is equal to $$$[l_j, r_j]$$$ , and he wants to find the final profit he gets at the end of the day if he chooses that range, modulo $$$998244353$$$.

More formally, the answer to the $$$j$$$-th query is equal to $$$\displaystyle\sum_{L = l_j}^{r_j}\sum_{R = L}^{r_j} \text{LCM}(a_L, a_{L+1}, a_{L+2}, ..., a_{R-1}, a_R) \times L \times R$$$ taken under modulo $$$998244353$$$.

Kel was sitting bored on Mari's picnic blanket as everyone else was doing something, but after sometime he had an idea how to spend his time! He asked Basil to borrow his camera, and Basil agreed.

Mari's picnic blanket consists of $$$4$$$ different rectangular pieces each of dimensions $$$L \times W$$$, linked in a way such that the whole blanket has dimensions $$$2L \times 2W$$$.

Basil's camera has a laser like technique which generates laser from both sides (frontview and back view) to take $$$1\text{D}$$$ pictures; the laser can be thought of as a straight line (even though the actual camera can not generate an infinite straight line, Kel assumes it is a straight line as the blanket's dimensions are not too big).

Kel is trying to place and orient the camera in a way such that the generated laser passes by all $$$4$$$ rectangles in the blanket. A straight line is said to pass by a rectangle if a line segment of non-zero length — which is a subset of that straight line — intersects the rectangle.

Now Kel wants to find the number of different straight lines generated from his placement and orientation that can pass by all $$$4$$$ rectangular pieces in the blanket. Since this number can be large, you are asked to output it modulo $$$10^9+7$$$.

Mari is currently baking cookies for OMORI's quest (as they need a lot of juice and heart in this one). She currently has a cookie dough with nutrition value $$$a_1$$$.

There are $$$n-1$$$ ovens numbered from $$$1$$$ to $$$n-1$$$. Mari puts each cookie in every oven by order, starting from oven $$$1$$$ till oven $$$n-1$$$. Ovens in dreams are different from casual ovens; they have two modes: Heating mode and Freezing mode, and also each oven $$$i$$$ has a power value $$$a_{i+1}$$$.

When baking a cookie with nutrition $$$x$$$ in the $$$i$$$-th oven, Mari can do one of the following options :

1. Set the $$$i$$$-th oven on heating mode; this will change the nutrition value of the cookie from $$$x$$$ to $$$\max(x,a_{i+1})$$$.
2. Set the $$$i$$$-th oven on freezing mode; this will change the nutrition value of the cookie from $$$x$$$ to $$$\min(x,a_{i+1})$$$.

Mari will try every possible configuration of modes to all $$$n-1$$$ ovens, and she wants to find the summation of the nutrition values of all final cookies over every possible configuration of ovens. Since this sum can be large, Mari wants its value taken under modulo $$$10^9+7$$$.

Two configurations of ovens are considered different if there exists an oven $$$j$$$ $$$(1 \le j \lt n)$$$ such that oven $$$j$$$ is set on heating mode in one configuration and set on freezing mode in the other one.

Basil wants to play a game with his best friend Sunny; he starts by explaining the rules to him.

The game is played on an array of $$$n$$$ flower pots, where the $$$i$$$-th pot $$$(1 \le i \le n)$$$ has two values $$$a_i$$$, $$$t_i$$$, denoting the number of seeds initially in the $$$i$$$-th flower pot and the type of seeds in this flower pot, respectively.

During a move, the player has to choose a flower pot which has a non-zero number of seeds; let the index of this flower pot be $$$i$$$ $$$(1 \le i \le n)$$$, then he will do two things:

1. Pick a positive integer value $$$x$$$ $$$(1 \le x \le a_i)$$$ and decrease $$$a_i$$$ by $$$x$$$ (Choose some non-zero number of seeds from some flower pot and remove them).
2. For every flower pot $$$j$$$ such that $$$t_j \lt t_i$$$, you can set the value of $$$a_j$$$ to any non-negative integer of your choice; it can still be the original value of $$$a_j$$$ before the move (For every flower pot that has a seed type value less than the value of the type of the seeds you removed, you can either increase, do nothing to, or decrease the number of each of those flower pots to any number of your choice as Basil has an infinite supply of seeds of every type, but the number of seeds has to be non-negative after every change in each pot).

The player who can not make a move loses, and Sunny goes first.

Sunny and Basil are going to play $$$q$$$ matches; the $$$j$$$-th match $$$(1 \le j \le q)$$$ is going to be played on the subarray from index $$$l_j$$$ to index $$$r_j$$$, inclusive.

Assuming both Sunny and Basil are playing optimally, your task is to find which player wins in each of the $$$q$$$ matches.

OMORI is bored in white space; he has been living there for as long as he can remember... He creates a game out of boredom with his dolls.

There are $$$n$$$ dolls in the possession of OMORI, exactly one of these dolls resembles OMORI (has no emotion); the other $$$n-1$$$ dolls can be of three types:

1. Happy dolls (These dolls resemble Kel).
2. Angry dolls (These dolls resemble Aubrey).
3. Sad dolls (These dolls resemble Hero).

How does the game work? Since OMORI has been living alone for a lot of time, he started to make imaginary fights with dolls; he decides the winner according to the following chart:

Happy beats Angry - Angry beats Sad - Sad beats Happy

So, when two dolls fight, OMORI decides the result according to the following rules:

1. If one of the two dolls is emotionless, the result is a tie.
2. Otherwise, if the two dolls are of the same emotion, the result is a tie.
3. Otherwise, decide the winner of the two dolls based on the emotion chart described above.

After explaining, OMORI then plays the game with you; the game is as follows: OMORI shuffles the $$$n$$$ dolls and asks you to find the emotionless doll (the one that resembles OMORI). You can do up to $$$3n$$$ questions of the form i,j, $$$(1 \le i,j \le n)$$$, and OMORI will answer with either $$$0$$$ or $$$1$$$.

When you ask OMORI about two dolls i,j, he will return $$$1$$$ only if doll $$$i$$$ beats doll $$$j$$$ in a fight; otherwise, he will return $$$0$$$ (whether it was a tie or doll $$$j$$$ won).

To ask OMORI a question, you can output no more than $$$3n$$$ queries of the following format:

• "? i j", where $$$i,j$$$ are two integers satisfying $$$(1 \le i,j \le n)$$$.

In response to this query, you will receive $$$1$$$ if doll $$$i$$$ beats doll $$$j$$$ in a fight, and $$$0$$$ otherwise.

Once you have found the answer, output a query of the following format:

• "! x", where $$$x$$$ is the index of the emotionless doll.

If you make an invalid query, you will receive $$$−1$$$ instead of a response from OMORI. If you exceed the limit of $$$3n$$$ questions, you will receive $$$−2$$$ instead of a response from OMORI. If you return an incorrect answer, you will receive $$$−3$$$ instead of a response from OMORI. In all of these cases you will get the verdict Wrong answer. In this case, your program should terminate immediately to avoid undefined verdicts.

After outputting the queries/answer, do not forget to output a newline character and flush the output buffer. Otherwise, you will receive the verdict Solution "hung" (Idleness limit exceeded). To flush the buffer, use:

• fflush(stdout) or cout.flush() in C/C++;
• System.out.flush() in Java;
• flush(output) in Pascal;
• stdout.flush() in Python;
• refer to the documentation for other languages.