Our teacher is, as usual, late for the first lesson... Of course, someone opened the classroom, but the resentment towards the teacher, who keeps repeating his mistakes, is only growing. It's time to teach our teacher a lesson!

Suddenly, someone had the idea to rummage through the closet. There turned out to be $$$n$$$ sticks from a broken cross, gifted for the New Year. To scare and punish the culprit, something terrifying needs to be created—a non-degenerate triangle$$$^{\text{∗}}$$$ with a huge perimeter!

Since doing this manually is difficult, help us understand what the maximum perimeter of a triangle can be obtained, or $$$-1$$$ if it is impossible to form any triangle. Two sticks cannot form one side. That is, for example, with sticks $$$1,1,2,2$$$, it is not possible to make a triangle with sides $$$2$$$, $$$2$$$, and $$$1+1$$$.

You are given a set of $$$n$$$ weights, where $$$a_i$$$ is the weight of the $$$i$$$-th weight. In the store, there is an infinite number of products of each natural weight.

You only have balance scales in your store, where you can place products on the right pan and weights on the left pan. Your task is to determine the maximum weight $$$p$$$ such that any product in the store that weighs no more than $$$p$$$ can be uniquely (that is, you can guarantee to say what the weight of a particular product is) determined using the given balance scales for an unlimited number of weighings.

This is an interactive problem

Imagine that you find yourself as an investigator in a well-known game. You need to expose $$$n$$$ deviants who have committed outrageous crimes. Each android $$$i$$$ has a punishment measure $$$a_i$$$ ($$$1 \le a_i \le 10^9$$$, $$$a_i$$$ is an integer) and a stress parameter $$$c_i$$$, initially equal to zero. Since we have little time, you will conduct a parallel interrogation. With one question, you can shout aloud (all non-confessing deviants will hear your statement) "$$$X$$$ STAB WOUNDS! You didn't want to leave him a chance, huh?" Each deviant perceives this statement personally and starts to think:

• If $$$X \gt a_i$$$, the deviant will be sure that you do not know that he committed a crime and are just guessing, so after this, he will stop responding to any questions.
• If $$$X \le a_i$$$, the deviant receives $$$X$$$ units of stress because he is sure that you are about to uncover his sins. That is, $$$c_i := c_i + X$$$ (the value of $$$c_i$$$ increases by $$$X$$$).

When a deviant confesses, he leaves the interrogation room and does not hear any further questions.

Your task is to ensure that all deviants confess, and also to find out their measures of punishment. If at least one deviant does not confess, you will receive a Wrong Answer verdict even if you output the correct measures of punishment. Also, in some subgroups, you will not be required to find out the measures of punishment; it is enough to ensure that everyone confesses.

In this problem, you can ask questions of two types:

• "$$$?$$$ $$$X$$$" ($$$1 \le X \le 10^9$$$). You make an accusation with $$$X$$$ stabs.

  After each query, the interactor returns the following data:

  In the first line, the number $$$m$$$ ($$$0 \le m \le n$$$), the number of deviants who want to confess.

  In the next $$$m$$$ lines, $$$n + 1$$$ numbers are given: $$$j$$$ and $$$n$$$ numbers $$$b_i$$$, where $$$b_i = a_j + a_i$$$ for all $$$j \neq i$$$. For $$$i = j$$$, $$$b_i = 0$$$. The number of the confessing deviant and information about accomplices, respectively.

  It is guaranteed that each deviant, if they confess, will confess only once.

• "$$$!$$$ $$$a_1\ a_2\ \dots\ a_n$$$". This question means that you are ready to state all measures of punishment, and the interrogation ends, and your program must terminate immediately. If not all deviants confessed, you will receive a Wrong Answer verdict. All numbers you output $$$a_i$$$ must be integers, and it must also hold that $$$0 \le a_i \le 10^9$$$ ($$$0$$$ means that you do not know the measure of punishment). If at least one number is not an integer or outside this range, you will receive a Wrong Answer verdict. Also, if $$$t = 1$$$ and you output at least one incorrect measure of punishment, you will receive a Wrong Answer verdict.

  After making this query, your program must terminate.

The interactor in this problem is non-adaptive.

After outputting each query, do not forget to output a newline and flush the output buffer. Otherwise, you will receive a verdict of "Idleness Limit Exceeded" To do this, use:

• fflush(stdout) or cout.flush() in C++;
• sys.stdout.flush() in Python;
• see the documentation for other languages.

Buses on Leninsky Prospekt have started to run infrequently. Mark has become a victim of this transportation reform and is constantly late for school because of it. Nobody liked this, not even Mark, so he decided to optimize his route in other ways. Specifically, by using scooters.

It is known that Mark walks at a speed of $$$a$$$ m/s, while the scooter travels at a speed of $$$b$$$ m/s ($$$b \gt a$$$). Mark chooses a scooter as follows: the app suggests a circle centered at Mark's location with a minimum radius that contains at least one scooter, and marks all the scooters on this circle (there may be multiple scooters at some points). Mark selects one such scooter so that the total time walking to it and riding the scooter to school is minimized. If walking turns out to be no worse, Mark will walk; otherwise, he will ride that scooter.

Mark liked his method of traveling to school, so he decided to use it not only for school but also for other points in the city. Specifically, on $$$q$$$ days, he needs to get to the point ($$$x_i, y_i$$$). He lives at the point ($$$0, 0$$$). On each of the days, the circle and scooters will be the same (as companies return scooters to their places). There will always be $$$n$$$ scooters at the same distance from ($$$0, 0$$$). For each of the days, output the travel time from Mark's home to the respective point.

Let rad$$$(n)$$$ denote the product of all distinct prime divisors of the number $$$n$$$. For example, rad$$$(504)$$$ = rad$$$(2^3 \cdot 3^2 \cdot 7)$$$ $$$= 2 \cdot 3 \cdot 7$$$ $$$=42$$$. We define rad$$$(1) = 1$$$.

The statement of this problem is simple: you have an array $$$a$$$ of size $$$n$$$. You are given $$$q$$$ queries $$$[\ell;r]$$$, and you need to compute rad of the product of the numbers $$$a_\ell, a_{\ell + 1}, \dots, a_r$$$, that is: $$$$$$\displaystyle\texttt{rad}\left(\prod_{i=\ell}^{r} a_i\right) = \texttt{rad}\left(a_\ell \times a_{\ell + 1} \times \dots \times a_r \right)$$$$$$ Since this number can be quite large, output it modulo $$$10^9 + 7$$$.

Please note the low time limit. Solutions in Python should be submitted under PyPy 3-64.

Welcome, aspiring thieves! Today, you are tasked with robbing room number $$$25$$$. In your gear, we will only provide you with a small backpack, as there isn't much valuable stuff at the destination. However, even such items can be useful for the Headquarters! Yes, the backpack is a bit old, but it can hold a lot of useful and necessary items for the Headquarters! Periodically, you will receive queries from the base. The queries can be as follows:

1. + x. You are instructed to pick up and put a chocopie worth $$$x$$$ burleys into the backpack.
2. - x. You urgently need to throw out any chocopie worth $$$x$$$ burleys from the backpack to avoid being caught by Kirill Evgenievich. The Headquarters closely monitors the contents of your backpack, so you must always throw out a chocopie that is present in the backpack.
3. ? W. Vladimir Evgenievich is nearby, and he will consider the backpack suspicious if the total value of the chocopies in it exceeds $$$W$$$. The base wants to know the maximum value of chocopies that can hypothetically be left in the backpack after throwing out some chocopies. Chocopies are not thrown out after the query is made.

Mark found an old automaton with two buttons in his attic, which he used to play with as a child. The toy is quite rusty, but it still performs its function. When the first button is pressed, a single $$$0$$$ appears on the screen, and when the other button is pressed, either due to age or malfunction, the automaton outputs $$$k$$$ ones at once.

Mark became curious about how many different strings of lengths from $$$\ell$$$ to $$$r$$$ can be obtained if the automaton outputs $$$k$$$ ones when the second button is pressed. However, since the automaton is old and Mark's curiosity is great, you will have to answer $$$q$$$ queries instead of the automaton.

Since the answer to any of Mark's queries can be very large, compute it modulo $$$998244353$$$.

Since time immemorial, a delegation from our lyceum has been traveling to the beautiful city $$$\mathbb{S}$$$ to participate in a well-known olympiad. Let's dive into the year when our school team first arrived in this city. At that time, the infrastructure was not so developed, the streets were filled with intellectuals, and parts of the city were connected by boats. However, traveling by boat is not a cheap pleasure, so the local government decided to establish the construction of bridges between the islands that make up the city.

Since building a bridge that lasts forever is quite challenging, bridges in the city $$$\mathbb{S}$$$ are constructed every year. In year number $$$i$$$, starting from the first arrival of the lyceum students in this city, a new bridge is built between islands $$$u_i$$$ and $$$v_i$$$. Some bridges are so impressive that they are called important. A bridge $$$v_i \leftrightarrow u_i$$$ is considered important if the islands $$$u_i$$$ and $$$v_i$$$ become disconnected upon its removal; in other words, it is impossible to reach island number $$$u_i$$$ from $$$v_i$$$ using any bridges without using the direct bridge between them.

As time goes on, more majestic and beautiful bridges are built, and the old ones inevitably cease to be important. The government of the city $$$\mathbb{S}$$$ became interested in how many years a particular bridge was important. Since the government of the city $$$\mathbb{S}$$$ mostly deals with bureaucratic matters, this task falls to you. For each bridge, output the number of years it will be important, or $$$-1$$$ if it remains important indefinitely.

A correct parentheses sequence is a string that consists only of the characters «(» and «)», from which it is possible to obtain a valid arithmetic expression by inserting the characters «+» and «1». For example, «», «(())» and «()()» are correct, while «)(» and «(()» are not correct parentheses sequences. A simple parentheses sequence is defined as a string made up of the characters «(» and «)».

We will define the correctness of a parentheses sequence as the maximum length of its correct parentheses subsequence. For example, consider the string «()())((())()». Its correct subsequences include, for example, the following: «$$$\color{red}{\underline{\color{red}{\text{()}}}}$$$())((())()», «$$$\color{red}{\underline{\color{red}{\text{(}}}}$$$)$$$\color{red}{\underline{\color{red}{\text{(}}}}$$$))((($$$\color{red}{\underline{\color{red}{\text{))}}}}$$$()», «$$$\color{red}{\underline{\color{red}{\text{()()}}}}$$$)$$$\color{red}{\underline{\color{red}{\text{((())}}}}$$$($$$\color{red}{\underline{\color{red}{\text{)}}}}$$$», as well as others (but the problem statement is too short to list them all). As can be seen, a subsequence is our sequence from which zero or more elements have been removed, and the order of the remaining elements has not changed. For this sequence, the correctness will be equal to $$$10$$$ (the last of the provided subsequences has this length).

Given $$$n$$$ initially empty parentheses sequences. There are $$$q$$$ queries of two types:

• «$$$1 \ \ell \ r \ x$$$» — append $$$|x|$$$ parentheses to the sequences in the segment $$$[\ell, r]$$$. If $$$x \gt 0$$$, then opening parentheses, if $$$x \lt 0$$$ — closing parentheses.
• «$$$2 \ \ell \ r$$$» — output the sum of the correctness of the sequences in the segment $$$[\ell, r]$$$.