One of the shops of N-sky machine-building plant produces spare parts for cars. In order to monitor the quality, the weight of every detail is to be controlled. For that there is a special controlling person in charge. Unfortunately, the controller in this checking unit is rather lazy, and instead of weighing every detail separately, he decides to «optimize» the process a little. Also all similar (of the same type) parts are supposed to be of the same weight.

At the end of the working day, a box with many identical parts arrives for inspection. The controller knows that a quality part should weigh a interger number of grams, but is too lazy to look into the documents and find out how much exactly.

The «optimized» control process is as follows:

1. The controller carries out $$$k$$$ weights, and numbers them from $$$1$$$ to $$$k$$$.
2. For the $$$i$$$-th weighing, the number $$$a_i$$$ is randomly chosen for the number of parts; this number is recorded in the weights register-book.
3. The selected number of parts is placed on the scales, and their total weight $$$w_i$$$ is also recorded in the register-book.
4. Upon completion of $$$k$$$ weighing, the register-book is analyzed and a conclusion is made on the presence or absence of defects.

Naturally, such an «optimized» process does not always reveal the presence of faulty spare parts, and does not indicate a specific defective part. The controller is so lazy that in the event of signs of a defective item rejects the entire batch. In all other cases, the batch receives a sign of quality.

Your task will be to write a program that, according to the weights register-book, will determine whether the batch will receive a quality mark or will be rejected.

There's an emergency in a county-level American town. Gremlins have scattered around the town and thus the rest of the world is in danger, as, at least, one of them seems to have left the town. Special intelligence services are currently restoring the course of events and trying to identify the earliest moment when it could happen.

The town is represented in the form of a square checkered board of size $$$N\times N$$$. Each cell represents a single house. Gremlins are, typically, afraid of bright light and therefore tend to hide in darkness. Furthermore, as people go to bed, the lights in the houses are going out. Gremlins can move horizontally and vertically from one house, where the light is off, to another. As soon as they reach the house which is on the border of the town, they escape from the town.

You have reliable data about which houses gremlins occupied in the beginning, as well as the history of turning the lights off in the houses. You need to display number of the house in history, from which after turning the light off, at least, one gremlin could escape from the town. If gremlins can escape from the town immediately, type 0. The numbering of houses in history starts with one.

When performing various physical calculations, it is often necessary to deal not only with numbers, but also with the dimensions of quantities. In this case, the dimensions can be very complex and they need to be reduced: for example, the dimension kg / (kg / m / s) is just m / s.

Write a program that minimizes the dimension as much as possible and registers all occurring values from left to right in alphabetical order (if the dimension is a fraction, then the numerator and denominator are written in alphabetical order separately).

As you know, oranges are made up of slices, and it is quite convenient to divide them into several portions for several people. Obviously, anyone can eat it up by oneself, or divide it for a company in which there are as many people as slices in the orange itself.

If the orange slices can be equally divided among $$$n$$$ people, then we say that it is suitable for such a company. And what minimum number of slices $$$m$$$ should be in an orange, so that it could be suitable for $$$k$$$ different companies (companies are considered different if they consist of a different number of people)?

Write a program which, according to the number of companies $$$k$$$, will find the minimum number of orange slices suitable for exactly these different companies $$$k$$$ or report that such a number does not exist.

It has become a good tradition in programming competitions to solve the problem of Hanoi Tower.

Let us briefly recall the rules of this puzzle game.

There are three rods: $$$A$$$, $$$B$$$, $$$C$$$. Initially, $$$N$$$ disks of different diameters are placed on the source rod $$$A$$$: the smallest disk is at the top, and then come other disks as the diameter increases. The second and third rods are empty so far.

You want to move all the disks from the source rod $$$A$$$ to the resultant rod $$$B$$$, using the third rod $$$C$$$ as an auxiliary. In one move, it is allowed to take one (necessarily upper) disk and put it on another rod, possibly empty. Moreover, a disc of a larger diameter can not be placed on a smaller disc.

Many programming textbooks provide a solution to this puzzle.

Procedure Hanoi (X, Y, Z: char; N: integer);
Begin
 If N>0 then 
    Begin
       Hanoi (X, Z, Y, N-1);
       Writeln('Disk ', N, ' from ', X, ' to ', Y);
       Hanoi (Z, Y, X, N-1)
    End
End;

Associate Professor P. from the city of R., preparing for the programming championship, decided to warm up and began to manually shift the disks of Hanoi Tower . (For this, he used rings from a children's pyramid and three rods taken from his granddaughter.)

At some point, the granddaughter, offended by her grandfather, selected a part of the rings, without touching the source rod with the strung discs-rings.

Help the assistant professor and calculate the minimum possible number of moves he has managed to make if the current location of the disks on the source rod is known.

Disk movements are performed using the standard algorithm described in the procedure above. The combination of disks specified in the input file is guaranteed to be achievable.

At the computer science exam, Vasya was solving the following problem:

«Two players, Petya and Vanya, are playing the following game. In front of the players there is a pile of stones. Players take turns, Petya is the first to play. In one move, the player can add $$$a$$$ stones to the pile or increase the number of stones in the pile twice. For example, if $$$a = 2$$$, having a pile of $$$10$$$ stones, in one move you can get a pile of $$$12$$$ or $$$20$$$ stones. Each player has an unlimited amount of stones to make moves.

The game ends at the moment when the number of stones in the pile becomes at least $$$n$$$. The loser is the player who made the last move, that is, who received a pile of $$$n$$$ or more stones.

At the initial moment there were $$$s$$$ stones in the pile. It is said that a player has a winning strategy if he can win in any opponent's moves.»

Unfortunately, Vasya does not remember the values of $$$a$$$ and $$$n$$$, which were at the exam, but he remembers at which initial $$$s$$$ Petya or Vanya won. He also remembers that $$$a$$$, $$$n$$$ and $$$s$$$ did not exceed $$$10^3$$$.

Write a program which, using different values of $$$s$$$ and a winning strategy for these $$$s$$$, will find the minimum suitable $$$a$$$ and $$$n$$$.

For generating pseudo-random numbers, various methods are used. One of such methods is the use of Boolean recurrent expressions. In such a case, the pseudo-random number is represented as a bit sequence, such that each next bit is calculated from the previous ones using a certain formula. However, such a task actually determines the sequence of its first members.

An alternative is the use of Boolean equations. We will say that the bit sequence x₁, x₂, x₃, ..., x_n satisfies some equation

Let's call the sequence $$$a_0$$$, $$$a_1$$$, $$$a_2$$$, … $$$a_{k-1}$$$ as «self- describing»; if the value $$$a_i$$$ is the number of numbers $$$i$$$ encountered in this sequence.

For example, in a sequence 1, 2, 1, 0 - «0» occurs 1 time, «1» is found 2 times, «2» occurs once and «3» does not occur.

Your task will be to write a program that for a given length of sequence $$$k$$$, will output its elements with the specified indices, or report that such a sequence does not exist. If there are several such sequences, any of them is considered to be correct.

There are many options for playing noughts and crosses. Let's consider one of them.

A number of crosses and noughts are placed on the checkered square board, and there are some empty cells left. The player must fill in the empty squares so that neither crosses nor noughts form lines of more than three identical signs in a row. Lines are counted horizontally, vertically, or of diagonally format.

Your task will be to write a program which, in a given initial field, fills all empty cells with crosses or noughts according to the rules described above. If there are several such arrangements, then any of them will be considered correct.

It is guaranteed that for the input data, there is at least one correct solution.

You have two strings pattern $$$p$$$ and text $$$t$$$. Strings consist of only latin lower case characters. In addition pattern may include characters $$$+$$$ which means that a previous symbol should be repeated one or more times and characters $$$*$$$ in that case previous symbol should be repeated any number times.

Your task is to answer on the question does text $$$t$$$ matche to pattern $$$p$$$.

For example, text "eboooy" matches to patterns "ebo+y", "ebo*o*o+y+", but doesn't to "ebb*oy" or to "ebooo".

Four spark chambers are installed along the large meson collider, which monitors the interactions of mesons moving in a circle at high velocities.

In order to receive reliable synchronized data from spark chambers and process it quickly, it is required to place 2 computers inside the circle, connect them via a cable to each other, as well as to the spark chambers. Each camera must be connected to at least one computer. The task is to minimize the total length of the cable for maximum synchronization.

Write a program that calculates the cable length using the known location of the spark chambers.