Making tasks is hard. That's why Vlad went to play with hedgehogs and dice. He had 2 types of dice, $$$x$$$ dice with the letter A drawn on them, and $$$y$$$ dice with the letter C drawn on them. He came up with an ACC triangle, based on the principle of Pascal's triangle. On the $$$i$$$-th layer $$$(i \gt 0)$$$ of the ACC triangle, there should be exactly one letter A and exactly $$$i-1$$$ letters C following it.

example of an ACC triangle of height 4

Since Vlad doesn't have time for dice (he has hedgehogs), he asked you to tell him the maximum height of the triangle he can build from the dice he has.

This is an interactive problem.

You are given a sorted array $$$a$$$ of length $$$n$$$ in non-decreasing order. Array elements do not exceed $$$n$$$. You only know the length of the array. Using no more than $$$2 \cdot n$$$ queries, you need to guess the entire array. Queries can be made of the following type: «? i x», where $$$1 \leq i \leq n$$$ and $$$x$$$ is an integer. The jury will respond as follows:

• = if $$$a_i = x$$$,
• > if $$$x \gt a_i$$$,
• < if $$$x \lt a_i$$$.

After you determine the array, you must output it as follows: «! $$$a_1$$$ $$$a_2$$$ ... $$$a_n$$$», where $$$a_1, a_2, \ldots, a_n$$$ are the elements of the array that you guessed.

1. Output your queries in the format «? i x».
2. The jury will respond with one of three characters: «=» if $$$a_i = x$$$, «>» if $$$x \gt a_i$$$, or «<» if $$$x \lt a_i$$$.
3. Output your answer in the format «! $$$a_1$$$ $$$a_2$$$ ... $$$a_n$$$».

Recently, Maxim flew to Korea and wanted to attend the fireworks festival in Busan.

The Korean train system is represented by a tree of $$$n$$$ vertices. Train routes are bidirectional, and each trip requires $$$1$$$ ticket.

Maxim starts his journey from vertex $$$1$$$ and needs to reach vertex $$$n$$$. While at vertex $$$i$$$, he can buy any number of tickets for $$$a_i$$$ won.

Find the minimum number of won needed for Maxim to reach vertex $$$n$$$ from vertex $$$1$$$.

You are given an array $$$a$$$ of length $$$n$$$. A triple of numbers $$$(x, y, z)$$$ is called beautiful if the following conditions hold: $$$x$$$ is divisible by $$$y$$$ without a remainder, $$$y$$$ is divisible by $$$z$$$ without a remainder, and $$$x \gt y \gt z$$$.

You are given $$$q$$$ queries of the form $$$(l, r)$$$. For each query, you need to find indices $$$i \lt j \lt k$$$ in the array $$$a$$$ such that the triple $$$(a_i, a_j, a_k)$$$ is beautiful and $$$l \leq i \lt j \lt k \leq r$$$. Among all such triples, choose the one that maximizes the value $$$n^2 \cdot a_i + n \cdot a_j + a_k$$$. If there are multiple triples with the maximum value, choose the lexicographically smallest triple $$$(i, j, k)$$$.

Shenfe1 accidentally stumbled upon a hedgehog clearing during RO 2023. Initially, there are no hedgehogs in the clearing. Each of the $$$n$$$ ($$$1 \leq n \leq 300$$$) hedgehogs has three characteristics. The $$$i$$$-th hedgehog has three characteristics: $$$L_i$$$ ($$$1 \leq L_i \leq 10^8$$$), $$$C_i$$$ ($$$-10^8 \leq C_i \leq 10^8$$$) and speed. If $$$i \lt j$$$, then the hedgehog number $$$i$$$ is faster than the hedgehog number $$$j$$$. Also, it is guaranteed that all $$$L_i$$$ are unique.

In the $$$L_i$$$-th minute, the $$$i$$$-th hedgehog arrives at the clearing, and if it is still in the clearing, then after $$$T$$$ ($$$1 \leq T \leq 10^8$$$) minutes it will leave. Note that all hedgehogs are in the clearing for the same amount of time, and that the $$$i$$$-th hedgehog will still be in the clearing at time $$$L_i + T$$$.

Shenfe1 can, at any time, if there is at least one hedgehog in the clearing, throw them food. In this case, if the $$$i$$$-th hedgehog is the fastest hedgehog in the clearing, then it takes the food and leaves, and $$$C_i$$$ irritation is added to Shenfe1's mood. The time of throwing food, picking up food and the arrival/departure of the hedgehog can be neglected.

Shenfe1 wants to know what the maximum irritation he can get in the worst case, if his initial irritation is 0.

Once upon a time, our good friend Minim Tsoi went to the Intergalactic Programming Olympiad. It turns out that if you win this Olympiad, you will be given a lot of money, and you will be honored. Finding his motivation, Minim decided to give up all the benefits until the Olympiad and devote himself entirely to preparation.

But here's the problem, Minim needs to eat and sleep at least. After thinking for a bit, he made a list of hours when he can eat and sleep. There is no hour when he can both eat and sleep. In each hour, Minim can either eat or sleep. Also, Minim, unfortunately, is just a human, so he can go without sleep for $$$a$$$ hours, and without food for $$$b$$$ hours. Since he needs to train a lot for the honor, he wants to minimize the total time he spends eating and sleeping. Help Minim find out how many hours he will spend on useless things. The last time he ate and slept was at hour 0.

For clarification, let's say he last ate at hour $$$x$$$. Then, if from time $$$x+1$$$ to time $$$x+b$$$ inclusive, he doesn't eat, then Minim will die, and it will be very sad... The same goes for sleep.

We all know our dear friend - Leba Non. Playboy, billionaire, philanthropist, and also the creator of ACC tasks. This task is about him.

While creating the tournament tasks, the evil villain Bashkirov Daniil locked all the jury members in cages. For communication, there is a one-way tunnel from each cage to another. Initially, the $$$i$$$-th jury member sits in cage $$$i$$$. But for things to work efficiently, each jury member needs to be well-fed. For this, Daniil entrusted Leba Non with one task - to feed all the jury members. To do this, Leba Non decided to organize $$$q$$$ dinners. Each dinner is held in one of the cages. If a jury member can reach the cage with dinner, he goes there and does not return. The distance between cages is the number of tunnels that make up the path between them. Help Leba Non calculate the total distance that each jury member will travel.

It turns out that Railgun loves geometry problems. His mentor in this matter, fractal, gave him a set of $$$N$$$ points on the plane, some of which can be made anime-like. The peculiarity of an anime-like point (for example $$$H$$$) is that, having an arbitrary point $$$P$$$, you can turn it into a point $$$P'$$$ in one operation by rotating it around $$$H$$$ by any angle. In other words, if we describe a circle $$$\omega$$$ around point $$$H$$$ with a radius of $$$dist(H, P)$$$, then $$$P' \in \omega$$$ must hold.

fractal also gave him $$$Q$$$ independent requests: having an arbitrary point $$$A(x, y)$$$, say whether it is possible to move from it to point $$$B(-x, -y)$$$ by rotating it around anime-like points. Initially, Railgun has no anime-like points. And since it takes a long time to make them, he asked you to tell him the minimum number of anime-like points that he will need (if, of course, fractal's request is feasible). And also tell him how many ways there are to choose them. Since this number can be large, he asked you to output it modulo $$$10^9 + 7$$$.

You don't need to minimize the number of operations.

fractal loves geometry, so let's place him in a space he's familiar with, a two-dimensional plane. Initially, fractal is at coordinate O(0, 0) and facing the Ox axis. He was given a task, a piece of paper, and an even number $$$n$$$ $$$(4 \le n \le 10^6)$$$, the reason and purpose of which few know, but such is fate. He needs to perform exactly n operations, each operation happens as follows:

• fractal chooses any positive integer X.
• Gradually move X cells directly forward in the direction he is currently facing.
• Turn either right or left and write down the chosen turn on the paper.

If after performing all operations, fractal ends up at coordinate O(0, 0) and facing the Ox axis, and also never, except for the very last moment of the last operation, was at a coordinate he visited before, then the resulting record on the paper will be called the «answer» to the task.

But since fractal loves to count everything and Catalan numbers, he wanted to count how many «answers» he could get. Since the answer can be very large, output it modulo $$$10^9 + 7$$$.

In the distant future, in a galaxy governed by the Star Union, interstellar ships and planets form a complex network, resembling a tree. This network consists of $$$n$$$ vertices. The Union faces a serious threat — $$$m$$$ types of cyber-viruses that can rapidly spread through the network and infect all planets and ships.

Each of the $$$m$$$ types of cyber-viruses has unique properties and can infect neighboring vertices in the network. At time $$$t$$$, if a planet or ship $$$v$$$ is infected with a virus of type $$$i$$$, then at time $$$t + 1$$$ all neighboring vertices will also be infected with this virus. The Star Union's task is to control and track the spread of viruses to prevent catastrophic consequences.

The Star Union has created a command center to manage the spread of cyber-viruses. They receive requests of three types:

1. Virus Insertion:

   At time $$$time$$$, vertex $$$v$$$ is infected with a cyber-virus of type $$$i$$$. It is important to note that each cyber-virus of type $$$i$$$ is unique, and the times $$$time$$$ do not necessarily increase.

2. Virus Removal:

   You need to remove the cyber-virus of type $$$i$$$, which means that this virus is no longer considered in the analysis.

3. Infection Analysis:

   You need to determine the minimum time $$$t$$$ when there is a vertex that is infected with all non-removed cyber-viruses on the segment $$$[l, r]$$$, that is, a vertex $$$v$$$ such that it is infected with all viruses on the segment. You also need to output all vertices that will be infected with each cyber-virus from this range at time $$$t$$$.

Initially, none of the vertices are infected with any virus.

AAlikhan and $$$k$$$ of his friends are going to a concert by AAdo. The concert hall can be represented as a table of $$$n$$$ rows and $$$m$$$ columns (the price of a seat in row $$$i$$$ and column $$$j$$$ is equal to $$$c_{i,j}$$$), where the first row is closest to the stage, and the last row is farthest from the stage. Each cell of the table is one seat. Seats within the same column are priced in descending order from the first row to the last (the closer to the stage, the more expensive). It can be considered that the stage is on row $$$0$$$. AAlikhan and his friends want to buy one seat each so that they spend no more than $$$B$$$ betabucks in total and their seats form one connected component. They also all dream of seeing AAdo's face, so they want to sit so that the farthest friend is as close to the stage as possible. Find the row of the farthest friend.

The formation of one connected component means that all occupied seats must be connected to each other horizontally or vertically. This means that from any occupied seat you can get to any other occupied seat by moving horizontally or vertically through adjacent occupied seats.

It is guaranteed that AAlikhan will always have a way to buy $$$k+1$$$ seats.