A new IT company has recently founded their office in the city! Their headquarters are located at the point $$$(0, 0)$$$, and the campus is a rectangle with corners at $$$(0, 0)$$$ and $$$(1, 1)$$$. The campus is very small and has no facilities yet. However, there are many facilities in the neighborhood. Why not to enlarge the campus and have them all inside?

The facilities will be captured and added to the campus one by one. After taking control of each facility, the company has to rebuild the fence around the campus. The fence should be the smallest rectangle with sides parallel to coordinate axes that contains the headquarters and all captured facilities.

It is possible to reuse material from the previous fence, but sometimes the total length of the fence may increase. In this case it is necessary to buy some new material. If the length of the fence before the capture was $$$a$$$ meters, and after the capture it became $$$b$$$ meters, $$$b - a$$$ units of material should be bought.

It is hard to justify the needs for huge buys. Find the order of capturing the facilities such that the maximum increase in the length of the fence after the capture is minimized.

The material required for building the initial fence (of size 4) is not considered an increase, as it is initially present.

In yet another card game, there are several types of cards and a deck of 30 cards. For each card type, there is either a single card of that type in the deck or two such cards. Initially, the deck is shuffled. Afterwards, the cards are drawn randomly from the deck one by one until it is empty.

Having played $$$100\,000$$$ games, you noticed that the dealer draws the cards unfairly. Instead of picking the next card randomly, he follows some strange algorithm. The $$$i$$$-th card type is assigned a weight $$$X_i$$$ ($$$0 \lt X_i \leq 1$$$). On every turn, the probability that the next drawn card would be of type $$$i$$$ is $$$c_i X_i / S$$$, where $$$c_i$$$ is the number of remaining cards of the $$$i$$$-th type and $$$S = \sum\limits_{j} c_j X_j$$$ is the sum of weights of all remaining cards.

In order to be prepared for the next playing session, you want to be able to predict the actions of the dealer. Fortunately, you remember the order in which the cards were drawn in all $$$100\,000$$$ games. Given that information, find the weight assigned to each card type.

In the modern world, diversity is the major concern, language diversity in particular. That's why the upcoming talent show is going to be held in multiple languages. However, making the program both diverse and not boring is a tough problem.

There are $$$n$$$ singers going to participate in the show and $$$m$$$ songs to be performed. Each singer has several songs in their repertoire, and some of them may be sung in different languages. For a program to be complete, each participant should sing at least one song and each song should be sung at least once. For a program to be not boring, each participant should use each language no more than once, and each song should be sung in each language no more than once as well.

Given the repertoire of each singer, make a complete and not boring program of the show, or determine that it is impossible.

Alice and Bob love playing the Nim game (if you do not remember the rules, please refer to the Notes section). They played it so many times that they learned how to determine the winner at a first glance: if there are $$$a_1$$$, ..., $$$a_n$$$ stones in the heaps, the first player wins if and only if the bitwise xor $$$a_1 \oplus \ldots \oplus a_n$$$ is nonzero.

They heard that in some online games players pick their characters before the game, adding a strategic layer. Why not do it with Nim?

They came up with the following version. Alice and Bob each have several boxes with heaps. In the first phase they pick exactly one heap from each box. In the second phase Alice chooses some nonempty subset of those heaps, and the regular Nim game starts on chosen heaps with Bob to move first.

Bob already knows which heaps Alice picked. Help him to perform his picks so that he wins the game no matter which heaps Alice chooses during the second phase.

At last, the famous spy and secret agent James Bond succeeded in finding his current nemesis, Dr. Zlo. They met at the roulette table of the casino Permutasino, and now 007 tries to guess the latest evil plan of his vicious enemy.

The roulette table consists of $$$n!$$$ cells containing all possible permutations of integers between $$$1$$$ and $$$n$$$. Betting process in this roulette is rather unusual: player puts no more than $$$n$$$ bets on some of the cells. Each bet is a non-negative number $$$b_{\pi}$$$ where $$$\pi$$$ denotes the permutation it corresponds to. The sum of all bets should be equal to $$$1$$$.

After bets are made, the roulette mechanism picks a random permutation from the distribution defined by the numbers $$$b_{\pi}$$$. Formally, the permutation $$$\pi$$$ will be chosen with probability $$$b_{\pi}$$$ if there is a bet on permutation $$$\pi$$$, or with probability $$$0$$$ otherwise.

In order to beat Dr. Zlo in this mind battle and persuade him to disclose his evil plan, 007 has to make bets in such way that the expected value of the resulting permutation is a vector $$$(x_1, x_2, \ldots, x_n)$$$. Consider expected value of a random permutation of length $$$n$$$ to be defined as a vector of length $$$n$$$, where $$$i$$$-th element is the expected value of the $$$i$$$-th element of the random permutation.

Help James Bond to make appropriate bets, or determine that it is not possible and he has to save the world by using different means (like shooting everyone and blasting every building on his way) this time.

Some of you may know how to find a Minimum Cut in a graph. Some of you may also have heard about the fact that Maximum Cut problem is NP-complete (more formally, the decision version of finding the cut of value at least $$$k$$$ is NP-complete). I bet that some of you even thought about something like: "Hmm, what if I simply negate all costs and transform a Max Cut problem into a Min Cut problem? Where are my Turing Award and billion dollars... Oh, snap, I got it."

It turns out that, for some restricted classes of graphs, problems may become easier than in the general case. Consider the Planar Maximum Cut problem which is formulated as follows. Consider an undirected graph $$$G$$$ consisting of $$$n$$$ vertices $$$V = \left\{v_1, v_2, \ldots, v_n\right\}$$$ and $$$m$$$ edges $$$E = \left\{(v_{a_1}, v_{b_1}), (v_{a_2}, v_{b_2}), \ldots, (v_{a_m}, v_{b_m})\right\}$$$. The graph is planar, and you are given its embedding into the plane: besides the description of the graph, you know the coordinates of the vertices such that, if we draw segments corresponding to the edges of the graph, no two edges would share an internal point. There is also an integer cost $$$c_j$$$ associated with $$$j$$$-th edge of the graph.

Your task is to partition vertices of the graph into two disjoint sets $$$A$$$ and $$$B$$$ ($$$A \cup B = V$$$) such that the total cost of cut edges is maximum possible. An edge is called a cut edge if exactly one of its endpoints belongs to $$$A$$$ and exactly one belongs to $$$B$$$.

Have you ever played Battle Royale games? In this kind of games, players are left alone and empty in a large area, and they must collect weapons, ammo, medkits and armor in order to kill each other. The game ends when only one player remains, this player is declared the winner.

To provoke players to fight each other, the safe zone is introduced. Players who are outside the safe zone are getting damage. Safe zone is always getting smaller and smaller, until it becomes a single point, so sooner or later each player has to make a choice: get inside a safe zone and fight other players or stay outside, lose hit points and eventually die.

In one-dimensional world, there is a famous Battle Royale game: BattleUnknown's Playergrounds. The game area is a segment $$$[L, R]$$$. Initially, the safe zone is the whole segment $$$[L, R]$$$, and in the end of the game it will narrow to a single point $$$M$$$ ($$$L \le M \le R$$$), where $$$M$$$ is chosen equiprobably on the segment $$$[L, R]$$$. The safe zone narrows in such a way that $$$\frac{M-L}{R-M} = const$$$, and each second its length decreases by 1.

Today we got a match between $$$n$$$ extremely passive players: the $$$i$$$-th of them is hiding in the house with the coordinate $$$x_i$$$ and is not going to move. Imagine it, they better die outside the safe zone than move out of their houses! Their plan is to outlive all others using the medkits they have collected: the $$$i$$$-th player can stay alive for $$$a_i$$$ seconds outside the safe zone.

For each player, determine the probability that this player wins the game.

You are playing the final round of an intellectual game. A total of $$$n$$$ topics were selected, and each of the $$$n$$$ authors prepared a question for each topic. For each topic $$$i$$$ and each author $$$j$$$, you know the probability that you will answer the question from the $$$j$$$-th author on the $$$i$$$-th topic.

Before you actually get the question, $$$n-1$$$ turns are made. Two actions happen during each turn. First, you discard all questions of any single topic. Second, the moderator discards all questions from any single author. Eventually only one question remains. If you answer it correctly, you win the round.

Of course, you discard columns trying to maximize the probability of your victory. On the contrary, the moderator tries do minimize it.

If you both play optimally, what is the probability that you answer the remaining question?

"Who wakes up first gets the slippers", a Russian proverb says. However, in our campus it is not that easy. You not only have to come early (all slippers will be already taken otherwise), but also are to obey the strict rules of the shoe case.

The shoe case looks like an $$$n \times m$$$ grid. Each cell contains a slipper, either left or right. Initially, each slipper is rotated in one of the four directions: left, right, forwards or backwards. It is allowed to take any adjacent pair of slippers (not necessarily distinct) and rotate one of them 90$$$^\circ$$$ clockwise and another 90$$$^\circ$$$ counterclockwise. When you find a pair of slippers in natural position, you may put them on and finally go away, happy and warm.

A pair of slippers is in natural position if:

• their cells share a side;
• they face the same direction;
• if you look at the two cells along that direction, one cell is to the right and another is to the left. Also, there is a right slipper in the right cell and the left slipper in the left cell.

Assuming everyone is altruistic and performs in an optimal way, find the maximum number of people that can walk away with their pair of slippers put on.

This problem was supposed to have a nice long legend about the Wild Wild West, but the author did not manage to write it in time, so use the power of your imagination!

Consider a number line. A player initially stands at the position $$$x = p$$$. At the beginning of each round, you can say either "+" or "-". After that, the player changes position according to what you said. More precisely, if you say $$$t$$$ and the player stood at position $$$x$$$, then he moves to position $$$x' = x + d_t$$$, where $$$d_+$$$ and $$$d_-$$$ are two integer constants.

You do not know the exact values $$$p$$$, $$$d_0$$$ and $$$d_1$$$, but you know that the player is either the Good, the Bad or the Ugly (yeah, imagination!):

• The Good player has $$$p = m$$$, $$$d_+ = 2$$$, $$$d_- = -1$$$;
• The Bad player has $$$p = -m$$$, $$$d_+ = 1$$$, $$$d_- = -2$$$;
• The Ugly player has either $$$p = m$$$ or $$$p = -m$$$ and either $$$d_+ = 1$$$ and $$$d_- = -1$$$ or $$$d_+ = -1$$$ and $$$d_- = 1$$$.

As you can see, the starting position of the player depends on some integer constant $$$m$$$ ($$$1 \le m \le 1000$$$)... unfortunately, you do not know it too.

After each round, the player tells you if he now stands at $$$x = 0$$$ or not.

It appears that, by playing several rounds, you can uniquely determine if the player is Good, Bad or Ugly. Do it in no more than $$$30 m$$$ rounds.

In each test, the values $$$m$$$, $$$p$$$, $$$d_+$$$ and $$$d_-$$$ are chosen according to the above rules. They are fixed in advance and don't change during the checking process.

This is an interactive problem.

If you want to play a round, print either "+" or "-" on a separate line. In response, you will get a line containing either $$$1$$$ if the player arrived at position $$$x = 0$$$, or $$$0$$$ if the player stands somewhere else.

If you are ready to guess the type of the player, print a line containing the character "!", a space and one of the words "good", "bad" or "ugly". After that, your program must terminate.

If after playing $$$30 m$$$ rounds you do not provide the answer, your solution will get a "Wrong Answer" outcome.

To prevent output buffering, flush the output buffer after each printed line: this can be done by using, for example, fflush (stdout) in C or C++, System.out.flush () in Java, flush (output) in Pascal, or sys.stdout.flush () in Python.