The hamster Shustrik received an unusual calculator as a gift from the hedgehog Shurshik. Initially, the number $$$A$$$ is displayed on the calculator screen.

The instructions for the calculator specify a fixed number $$$M$$$. All arithmetic operations are performed with this number. Additionally, Shurshik has thought of numbers $$$N$$$ and $$$B$$$ and informed Shustrik about them.

The calculator can perform only four operations, and in one step, one of the following operations can be applied:

• Operation "+": replace the current value $$$A$$$ with $$$A + M$$$.
• Operation "-": replace the current value $$$A$$$ with $$$A - M$$$.
• Operation "*": replace the current value $$$A$$$ with $$$A \cdot M$$$.
• Operation "%": replace the current value $$$A$$$ with the remainder of the division $$$A$$$ by $$$M$$$. After this operation, the condition $$$0 \le A \lt M$$$ holds.

After performing some (possibly empty) sequence of operations, the number $$$A'$$$ will be obtained.

The hedgehog Shurshik became curious whether Shustrik can obtain such a number $$$A'$$$ that

$$$$$$ A' \equiv B \pmod N. $$$$$$

In other words, the numbers $$$A'$$$ and $$$B$$$ must have the same remainders when divided by $$$N$$$.

Your task is to help the hamster find any sequence of operations of the smallest length, after which the specified condition will be satisfied, or determine that it is impossible to obtain such a number.

Points for each subtask are awarded only if all tests for that subtask and necessary subtasks are successfully passed.

On the monorail line, there are $$$n$$$ stations, numbered in order from $$$1$$$ to $$$n$$$.

Each station $$$i$$$ has a name $$$s_i$$$ — a string of no more than 20 Latin letters. Each letter is written on a separate nameplate.

As part of the urban infrastructure upgrade project, it was decided to rename all the stations to some new names. The order for renaming has already been signed and will take effect tomorrow. However, there is a problem: no one has had time to replace the names on the nameplates at the stations. Now it is your task.

Unfortunately, there is no time to make new nameplates. Therefore, the only possible option is to move the nameplates from one station to another.

Formally, in one operation, you can choose two indices $$$1 \le i, j \le n$$$, as well as any letter from the string $$$s_i$$$, and move that letter to any position in the string $$$s_j$$$. This operation takes $$$1 + |i - j|$$$ precious units of time.

For example, if $$$s_i = \texttt{ab}$$$ and $$$s_j = \texttt{cd}$$$, then in one operation of moving a letter from $$$i$$$ to $$$j$$$, you can do:

• $$$s_i = \texttt{a}$$$; $$$s_j = \texttt{bcd}$$$ or $$$s_j = \texttt{cbd}$$$ or $$$s_j = \texttt{cdb}$$$.
• $$$s_i = \texttt{b}$$$; $$$s_j = \texttt{acd}$$$ or $$$s_j = \texttt{cad}$$$ or $$$s_j = \texttt{cda}$$$.

Note that it is also allowed to choose $$$i = j$$$ in the operation.

You need to replace the nameplates with names at each station as quickly as possible so that they correspond to the new names. Determine whether this is possible, and if so, the minimum necessary amount of time.

Here, $$$\operatorname{sorted}(s_i)$$$ denotes the string $$$s_i$$$ sorted in alphabetical order. For example, $$$\operatorname{sorted}(\texttt{abacaba}) = \texttt{aaaabbc}$$$

Persik — a shark in the world of programming — decided to create a schedule for all tracks of the Innopolis Open olympiad.

There are $$$D$$$ days in the academic year, numbered from $$$1$$$ to $$$D$$$. In total, $$$n$$$ olympiads are held.

The olympiads are numbered from $$$1$$$ to $$$n$$$ in non-decreasing order of their initially scheduled dates. Each olympiad takes place on exactly one day. For each olympiad, its initially scheduled date and its benefit for the younger generation are known.

You may change the date of any olympiad, but only to a later day within the same academic year (that is, the new date cannot be earlier than the original one and cannot exceed $$$D$$$).

After all changes, the olympiads must remain in non-decreasing order of their scheduled dates.

The total benefit of the olympiad season is defined as follows. For each day, consider all olympiads scheduled on that day. If at least one olympiad is scheduled on a given day, the benefit of that day is the maximum benefit among those olympiads. If no olympiads are scheduled on that day, the benefit of that day is $$$0$$$.

The benefit of the season is the sum of the benefits over all $$$D$$$ days.

For the benefit of the students, determine the maximum possible total benefit of the season.

The tests for this problem consist of thirteen groups. Points for each group are awarded only if all tests of the group and all tests necessary for it are passed.

This is an interactive problem.

Cyber-shark Zubastik$$$^{\dagger}$$$ works in a warehouse and stacks boxes into a single vertical tower. The height of the tower is unlimited, but the shark can only remove and place the top box on the tower. There is also a buffer nearby — a free area where boxes can be temporarily held (any number of boxes can be in the buffer).

Boxes are numbered in the order they arrive, starting from $$$1$$$. For each box, the moment in time $$$t_j$$$ when it needs to be extracted from the warehouse is known.

During the work, there are two types of events:

• + t — a new box has arrived, which needs to be extracted at time $$$t$$$ $$$(1 \le t \le T)$$$. All values of $$$t$$$ are distinct.
• - j — the moment $$$t_j$$$ has arrived, and box number $$$j$$$ needs to be extracted.

Actions. During the processing of an event, the shark can perform the following operations:

• 1 j — place box $$$j$$$ on top of the tower (allowed only if box $$$j$$$ is in the buffer).
• 2 j — place box $$$j$$$ in the buffer (allowed only if box $$$j$$$ is on top of the tower).

Rules for processing events.

• At the event + t, the new box is immediately placed in the buffer. By the end of processing this event, the buffer must be empty.
• At the event - j, by the end of processing this event, there must be exactly one box left in the buffer — box $$$j$$$. After this, box $$$j$$$ is considered extracted and removed from the system.

Your task is to output a set of operations for each event that correctly processes that event.

$$$^{\dagger}$$$ see fig.

Cyber-shark Zubastik

First, your program must read an integer $$$T$$$ — the number of events.

Then for each $$$i = 1,2,\dots,T$$$, the interactor outputs a line with the description of the event occurring at time $$$i$$$:

• + t — a new box has arrived, which needs to be extracted at time $$$t$$$ $$$(1 \le t \le T)$$$. The box receives the next sequential number. By the end of processing the event, the buffer must be empty.
• - j — box $$$j$$$ needs to be extracted. By the end of processing this event, exactly one box $$$j$$$ must remain in the buffer.

After receiving the next event, your program must output the response for it in the following format:

• In the first line, an integer $$$K$$$ — the number of operations to process the current event;
• Then $$$K$$$ lines, each with two integers: the type of operation ($$$1$$$ or $$$2$$$) and the number of box $$$j$$$.

To receive the next event, you must output a correct response for the current event and end the line with a newline character.

After outputting the response, be sure to flush the output buffer:

• fflush(stdout) or cout.flush() in C++;
• System.out.flush() in Java;
• flush(output) in Pascal;
• stdout.flush() in Python.

Note that for faster output, it is advisable to call flush (or endl) after outputting all $$$K$$$ operations, rather than after each operation.

The interactor in this problem is non-adaptive: within a single test, the sequence of events is fixed and does not change based on your responses.

In this problem, there are two types of tests.

The first type of test — an array [1, 1, 2, 2, ..., N, N] is generated and shuffled randomly, resulting in an array $$$[a_1, a_2, \dots, a_T]$$$ of size $$$T$$$, where $$$T = 2N$$$. A box is added at time $$$t_1$$$ and taken out at time $$$t_2$$$, if $$$t_1 \lt t_2$$$ and $$$a[t_1] = a[t_2]$$$.

The second type of test — it is guaranteed that the boxes are taken out in the same order they are added.

For each value of $$$N$$$ (the number of boxes), one test of each type is generated.

Elephant Filimon decided to visit his panda-friend Cheng Shi from Chengdu, China. Cheng Shi loves bamboo and showed her collection of bamboo inscriptions. Each inscription is a string of lowercase Latin letters.

Cheng Shi's collection is a dynamic multiset of strings. Initially, it is empty.

The panda can perform operations of two types:

• + s — add the string $$$s$$$ to the multiset.
• - s — remove one copy of the string $$$s$$$ from the multiset.

Elephant Filimon became curious about the minimum number of actions required after each operation to make all strings in the current multiset identical.

Allowed actions on one string from the collection:

1. Remove the last character of the string — Cheng Shi carefully bites off a piece of bamboo.
2. Add any character to the end of the string — the panda plants bamboo, and it grows, adding one character to the end.

The string to which all others are brought can be any (including empty) and does not have to be present in the multiset.

Note: The strings in the multiset are not actually changed. After each query, it is only necessary to compute the minimum number of actions required to make all strings identical. For subsequent operations, the multiset remains unchanged.

Help Cheng Shi quickly respond to Filimon's question after each change.

Alexander and Babin live on an abandoned island. Their only entertainment consists of trees, stones, and bombs (don't ask where they came from). They are very bored and want to play a game. Alexander suggested playing "Minesweeper", while Babin suggested "Nim". As a compromise, they decided to play Nimesweeper!

With no other choice, the guys chose a tree as the game board. Recall that a tree is a connected undirected graph without cycles.

In the course of the overall game, Alexander starts playing the subgame "Minesweeper". Initially, none of the vertices of the tree contain bombs. On his turn, Alexander chooses any vertex without a bomb and places a bomb in it. After that, in each vertex that does not contain a bomb, a number of stones equal to the number of bombs in its neighboring vertices is placed.

Babin can interrupt Alexander after any of his moves. Once this happens, they start playing "Nim" with the resulting piles of stones, with Babin going first.

If Babin does not interrupt Alexander, Alexander makes the next move (places another bomb), after which the piles of stones are updated, and so on, until Babin starts the game of "Nim".

The player who cannot make a move in "Nim" loses.

Babin really wants to win, so he will interrupt Alexander at the earliest possible moment when he can guarantee his victory.

Alexander, well aware that he cannot win this game, decided instead to maximize his enjoyment, so he wants to place as many bombs as possible before Babin starts the game of "Nim". Please help Alexander find the maximum number of bombs he can place!

Recall that in the game of "Nim", the first player wins if and only if the bitwise XOR of the sizes of the piles is non-zero.

Recall that XOR or Exclusive OR is a binary operation that is applied to each pair of bits in the same position in the binary representations of numbers such that the result at that position is 0 if the bits are equal, and 1 otherwise. For example, 3 XOR 5 = 6, since $$$3_{10}$$$ = $$$011_2$$$, $$$5_{10}$$$ = $$$101_2$$$, and therefore after applying the operation, the second and third bits become equal to 1, while the first bit becomes 0, resulting in $$$110_2$$$ = $$$6_{10}$$$.