Given two integers $$$s$$$ and $$$x$$$, find any shortest array such that the sum of its elements is $$$s$$$, and all elements are coprime to $$$x$$$.

Two integers are coprime if the only positive integer that divides both of them is $$$1$$$.

There is a square $$$ABCD$$$ whose vertices have integer coordinates, with $$$A$$$ on the positive $$$y$$$-axis.

You are given the squared distances $$$AO^2$$$, $$$BO^2$$$, $$$CO^2$$$, $$$DO^2$$$, where $$$O(0,0)$$$ is the origin. Find the vertices of the square.

Note the low memory limit!

You are given a binary tree with $$$n$$$ nodes in it, rooted at node $$$1$$$. This means that each node has at most $$$2$$$ children. You are also given two arrays of $$$n$$$ integers, $$$a$$$ and $$$b$$$

The subset problem for node $$$i$$$ is defined to be the question: Can you take a subset $$$S$$$ of the ancestors of node $$$i$$$ and itself, such that $$$\sum_{j \in S} (a_j) = b_i$$$

You can do at most $$$5000$$$ operations on array $$$a$$$. In one operation you choose two integers $$$i$$$ and $$$x$$$ ($$$ 1 \leq i \leq n$$$, $$$0 \leq x \leq 2 \cdot 10^6$$$), and set $$$a_i := x$$$.

After these operations, solve the subset sum problem for each node $$$i$$$, and output the results as a bitstring.

There's a board with $$$n \times m$$$ white squares. Jeroen plays a single-player game on this grid. Each turn he colors one square black. Two squares are adjacent if they share an edge. The squares, together with these adjacency relations form a planar graph. The game ends when a simple cycle of black squares is formed that has a non-empty interior. By drawing the edges of the graph with straight lines, between the centres of the squares we get a drawing of the planar graph. A square that does not lie on the cycle, is in the interior of the cycle, if it lies in the interior of the polygon that the edges of the cycle form, when drawn as straight line segments. Jeroen wants to produce a pretty picture on the playing board when he's done so he already thought of the moves he is going to play. If a move happens to end the game, he doesn't play it. In the input there are $$$k$$$ distinct positions $$$(r_i,c_i)$$$, the moves that Jeroen has planned out.

Your job is to figure out for each move, if it would end the game or not, and print a bitstring with $$$1$$$ if the $$$i$$$-th move ends up being played, and $$$0$$$ if this move would end the game, and does not get played.

You're given a polynomial $$$A(x) = a_0 + \dots + a_n x^n$$$ with integer coefficients and an integer $$$m$$$.

Consider a multivariate polynomial $$$D(x_1,\dots,x_m)$$$, defined as $$$$$$ D(x_1,\dots,x_m) = \prod\limits_{i=1}^m A(x_i) \prod\limits_{j=1}^{i-1} (x_i - x_j). $$$$$$

Let $$$s$$$ be the sum of squares of all coefficients of $$$D(x_1,\dots,x_m)$$$. Find $$$s$$$ modulo $$$10^9+7$$$.

You are given $$$n$$$ points in the plane, with no $$$3$$$ points collinear. You can choose some non-empty subset of the points, and choose an order for this subset. If the points in your chosen ordered subset are $$$p_0,p_1, \dots, p_{k-1}$$$, we want for $$$1 \leq i \leq k+1$$$, that the angles $$$ \angle p_{i-1} p_{i} p_{i+1}$$$ are alternating clockwise and counterclockwise in increasing order of $$$i$$$. In the labeling of the points in the angle, you should take the indices $$$\mod k$$$. Note that $$$k$$$ must be even, otherwise due to parity it is impossible. Such an ordered subset of points is called an alternating cycle.

You have to find the alternating cycle with the smallest number of points in it, and print it to the output, or report no such cycle exists.

Note the unusual memory limit.

Adamant is a famous person for writing educational blog posts on math and programming. One day, he finally decides that he has written too many blogs and it's time to go outside and touch some grass.

Adamant has a lawn on which $$$n$$$ grass plants grow. The grasses are indexed from $$$1$$$ to $$$n$$$. We can draw the lawn and grasses on the 2D plane: the ground is the line $$$y=0$$$, and grasses grow up vertically. Each grass can be described by two numbers $$$x$$$ and $$$y$$$, meaning it can be considered as a vertical line segment from $$$(x, 0)$$$ to $$$(x, y)$$$.

To touch grass, Adamant will move his hand $$$m$$$ times. Each time he moves his hand from the coordinates $$$(x_1, y_1)$$$ to the coordinates $$$(x_2, y_2)$$$ along a straight path. We say that his hand touches the $$$i$$$-th grass, if the segment $$$(x_1, y_1) - (x_2, y_2)$$$ touches the segment (or its endpoints) defined by the $$$i$$$-th grass.

Your task is to determine, for each time Adamant moves his hand, whether he will touch any grass. If the answer is yes, you also need to find the index of any grass he will touch.

You are a game designer working on a new video game, Outstandingly Captivating Platforming Challenge. The game consists of $$$n$$$ levels indexed $$$1 \ldots n$$$, which the player must complete in that order. In addition to the normal progression, the levels are also connected through $$$n$$$ one-way warp portals. A different team in your company has already completed the design of each level. They have placed one warp portal entrance and one warp portal exit in every level. Your task is to connect each entry portal to an exit portal on a different level such that each exit portal is also connected to only one entry portal.

However, there is an additional restriction: the player must not be able to skip ahead in the game. That is, the player must not be able to enter a portal, exit at a portal on a later level, and keep playing on that later level. In order to make this possible, the level designers have placed some exit portals in isolated locations from which the rest of the level is not accessible. That is: if an entry portal on level $$$u$$$ leads to an exit portal on some level $$$v \gt u$$$, then the exit portal on level $$$v$$$ must be in an isolated location.

You have already written a program to examine all allowed ways to connect each entry portal to an exit portal, in order to measure the predicted audience engagement. That program has been running for a while now, your boss is getting angry, and you want to know how long this program will take. Thus, calculate the number of allowed ways to connect each entry portal to an exit portal. Print the answer modulo $$$998\,244\,353$$$.

Jeroen made a new algorithm for checking if a point is inside a polygon:

Given a simple polygon $$$\bf{p}_0, \bf{p}_1 \dots \bf{p}_{n-1} $$$ and a query point $$$\bf{q}$$$, his algorithm does the following:

• Initialize $$$\text{ans}:=0$$$
• Draw a ray from $$$\bf{q}$$$ in the positive $$$x$$$-direction.
• For all $$$0 \leq i \lt n$$$: Check if the closed segment $$$\bf{p}_i \bf{p}_{(i+1) \mod n}$$$ intersects the ray, if so, increment $$$\text{ans}$$$.
• For all $$$0 \leq i \lt n$$$ if $$$\bf{p}_i$$$ lies on the ray, add $$$1$$$ to $$$\text{ans}$$$.
• If $$$\text{ans}$$$ is odd, the algorithm says inside, otherwise outside.

Note that two polygons $$$\bf{a}$$$ and $$$\bf{b}$$$ are considered the same polygon if the point list of $$$\bf{a}$$$ is a cyclic rotation of the points of $$$\bf{b}$$$. Two polygons are also considered the same, if the reversed point list of $$$\bf{a}$$$ is a cyclic rotation of $$$\bf{b}$$$. So in these cases, only one of $$$\bf{a}$$$ and $$$\bf{b}$$$ is included in the infinite list. Note that although placing an extra integer point on one of the edges of a polygon produces the same shape, this will be counted as a different polygon.

Nim is a classical strategy game played by two players. There are $$$n$$$ piles of stones, the $$$i$$$-th of which contains $$$a_i$$$ stones. Players alternate in taking turns. On each turn, the player must pick a pile with a positive number of stones and remove a positive number of stones from it. The player who can't make a move loses.

The Blue Monster wanted to add an interactive Nim problem to the Ordinary & Common Problem Collection. In this problem, your program would have to play Nim against an opponent who always plays optimally. However, the Blue Monster is too lazy to learn how to create interactive problems. Therefore, you are asked to only make moves where the opponent has only one optimal move.

You are given $$$a_1, a_2, \ldots, a_n$$$ — an instance of Nim. It is guaranteed that if both players play optimally, then the first player loses. You will play as the first player, your opponent will play as the second player. Your opponent will always make optimal moves. You have to play in such a way that after each of your moves, there is only one move that your opponent can make such that you will lose if both players play optimally after that point.

Print a sequence of such moves or declare that this is impossible. Notice that since your opponent always makes optimal moves, you know exactly what moves your opponent will make. You do not have to minimize the length of the sequence.

You are given $$$n$$$ nails mounted on a wooden board at integer coordinates. You have a piece of string that encloses all the nails and is pulled tight to form the smallest loop that encloses the points. You have to remove the nails one at a time, following this rule:

First, you pull the string tight around the remaining nails. Then, you may choose any nail that the string is pulled taut around (so the string touches this nail and makes an angle of $$$ \lt 180$$$ degrees) and remove it. You try to repeat this process until only one point remains.

Check if you can repeatedly remove nails until only one nail is left, and if so, give such a sequence of removals.

This is an interactive problem.

In an all-you-can-eat conveyor belt restaurant, meals are placed on a moving conveyor belt. The customers sit next to the conveyor belt as meals slide by. You can take any meal as it slides by you, and you can repeat that any number of times. It's a pretty good deal, but it's also easy to overeat and feel sick afterwards.

Specifically, after you sit down, meals $$$1, 2, \ldots, n$$$ will slide by. After seeing meal $$$i$$$, you judge its caloric value to be $$$a_i$$$.

In one particular such restaurant, there are two types of seats:

• Facing the direction opposite of the direction of the conveyor belt. In that case, you can see all items that will reach you in the future, and thus can plan your choices accordingly (assume there are no other customers in the restaurant).
• Facing the direction of movement of the conveyor belt. In that case, you can only see one item at a time: when meal $$$i$$$ next to you, you must decide whether you want it or not, with no knowledge of what the caloric values of the meals that come after it are. Once meal $$$i + 1$$$ slides by, meal $$$i$$$ is already too far to reach.

Therefore, it is harder to optimize your lunch when facing the direction of the conveyor belt. You did, however, come up with an unethical hack: you can get rid of a meal you have picked by discreetly sliding it on the table of another customer.

In order to prevent overeating, you have set the following rules for yourself.

• You will face the direction of movement of the conveyor belt.
• Once you start eating, you won't be able to take any new meals from the conveyor belt.
• At any time, the total caloric value of meals on your table must not exceed $$$1000$$$.

Now you have the opposite problem — you worry that if you follow all the rules, you will leave the restaurant hungry. You decided that you'll be happy as long as the total caloric value of meals you eat is at least $$$60 \%$$$ of what you'd be able to get if you were to face the opposite direction but still followed the other rules.

More formally, let $$$x$$$ be the maximum possible sum of a subsequence of $$$a_1, a_2, \ldots, a_n$$$ that doesn't exceed 1000. You'll be happy if the total caloric value of meals you eat is at least $$$0.6 x$$$.

Implement a strategy that ensures you'll always be happy. The interactor is adaptive, meaning that the sequence of caloric values is not necessarily decided in advance: it may depend on the choices your program makes.

The interaction between your program and the jury's program begins with reading a single integer $$$n$$$ ($$$1 \le n \le 10^4$$$) — the number of meals that will slide by.

The following will then happen $$$n$$$ times:

• Read a single integer $$$a_i$$$ ($$$0 \le a_i \le 1000$$$) from the input — the caloric value of the $$$i$$$-th meal.
• Print a line of the form $$$k\;t_1\;t_2\;\cdots\;t_k$$$, ($$$0 \le k \le i$$$, $$$1 \le t_j \le i$$$) indicating that you want to discard the meals with indices $$$t_1, t_2, \ldots, t_k$$$. All of the items must be on your table at that time.
• Print a line containing either the word "TAKE" (if you want to add meal $$$i$$$ on your table) or "IGNORE" (if you want to leave it on the conveyor belt). In either case, the word must be printed without quotes.

It is guaranteed that the sum of $$$n$$$ over all test cases is at most $$$10^4$$$.

If your program makes an invalid query at any time (i.e. you print a line that doesn't conform to the input specification, you have more than 1000 total value on the table at a time, you try to discard an item that is not on the table, or a test case ends without you being happy), the interactor will immediately terminate. If your program keeps reading input after that, it may receive an arbitrary verdict, as it will keep reading from a closed stream. To prevent this, always check if the input stream is still open, i.e. instead of writing

int ai; 
cin » ai;

int ai; 
if (!(cin » ai))
    exit(0);

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++;
• stdout.flush() in Python.