A normal magic square of order $$$n$$$ is an $$$n \times n$$$ grid (where $$$n$$$ is the number of cells on each side), filled with distinct positive integers in the range from $$$1$$$ to $$$n^2$$$, so that each cell contains a different integer and the sum of the integers in each row, column, and diagonal (primary and secondary) is equal.

Normal magic squares exist for all orders except $$$2 \times 2$$$ (order $$$n = 2$$$). The $$$1 \times 1$$$ magic square, with only one cell containing the number $$$1$$$, is called trivial. The minimal non-trivial case of order $$$3$$$ is shown below.

You can practice building normal magic squares in your spare time, but now your task is to write a program that returns the sum of numbers in the first line, given the order of the square.

Imagine rectangles drawn on a piece of squared paper, their sides matching the lines of the grid. In such case, the cells within a rectangle are either external if they are adjacent to the sides (marked black in the figure below) or internal if they are not attached to the sides (marked grey in the figure).

Calculate how many rectangles there are with the number of external cells exactly $$$n$$$ times smaller than the number of internal cells. Print the sizes of all appropriate rectangles in the ascending order based on the length of the smaller side.

Magic football is very popular in the Magic Land. In this game, the only way to hit the ball is using your magic skills. Unfortunately, players become exhausted after their magic efforts so they have to be substituted quite often. According to the rules of the game, each combination of players can play for exactly one minute. Each time only one player is substituted. It is prohibited to repeat the same team composition twice during the game.

The team from the Emerald City has $$$n$$$ players. According to the rules of magic football, $$$k$$$ players must be present in the field at any given moment. The game lasts $$$t$$$ minutes.

Example: let $$$n = 5, k = 3$$$; in this case, $$$10$$$ different team composition options are possible.

Write a program that will either generate a substitution schedule based on the given team size $$$n$$$, number of players in the field $$$k$$$, and game duration $$$t$$$ minutes or conclude that there is no suitable solution.

If there are several suitable schedule options, any one of them is regarded as a right solution.

Players are numbered $$$1$$$ to $$$n$$$.

There is an iconic Russian animated cartoon about a constrictor whose length equals to $$$5$$$ monkeys, $$$2$$$ little elephants or $$$38$$$ parrots plus one parrot wing because animals are not familiar with the metric system. Doctor Dolittle wants to check whether it is possible to find an appropriate unit of measurement for the patients waiting in queue to see him. The doctor spends most of his working hours treating the patients so he can only do the measurements during his leisure time.

When animals come to see the doctor, they wait in queue. Once a new patient joins the queue, the doctor's assistant measures his or her length and writes the result down in a list. Reception is in order of turn. Once the patient leaves, he or she is crossed out from the list. Every now and then, Doctor Dolittle checks the list and tries to find an animal that can be used to measure everyone else (not crossed out yet) so that their lengths would be positive integers.

Write a program to help Doctor Dolittle!

In the course of decoding flight recorders, an error was discovered in the microcode of one of the controllers that resulted in distortion of the data recorded. According to the results of the investigation, instead of recording $$$n$$$-digit binary numbers ($$$x_1x_2x_3...x_n$$$), the device recorded $$$n$$$-digit results of multiple summing of the initial value with a simultaneous shift to the left ($$$x_1x_2x_3...x_n + x_2x_3...x_n0 + x_3...x_n00 + ... + x_n00...0$$$).

As the capacity of the register where intermediate data are stored equals to $$$n$$$ bits, most significant bits resulting from shifts and summing were discarded. For example, initial number $$$0101$$$ would be transformed into $$$1011$$$:

Moreover, the result of summing was recorded in the order from the least significant bit to the most significant one (i.e., the least significant bit on the left and the most significant, on the right), so the number from the example above would be eventually transformed into $$$1101$$$.

Write a program that will restore the initial number from the encoded one and print the result in the order from the least significant bits to the most significant one.

It is a well-known fact that most of intelligence information comes from public sources. Following this rule, the Fairy-Tale Kingdom established an analytical unit. The first task of the unit was to map the shipment routes for magic crystals in the neighboring Magic Land. The following information was collected:

• Crystals can only be shipped from one city to another
• There is a crystal mine near one of the cities – the source of crystals
• Crystals are processed in one of the cities – and that is the final destination
• To make it harder to intercept the trucks, crystal shipment routes often change
• Only certain roads are used for crystal shipment
• Each road is used to ship crystals in one direction only
• The roads are mapped in such a way that it is impossible to return crystals to the city where they have already been, no matter which one of the cities was the origin
• Any two cities are connected by no more than one road.

The analysts managed to collect information about the number of routes between the source of crystals and other cities. Your task is to plot a possible shipments map. There are $$$n$$$ cities in the Magic Land, with pairs of cities connected by a road. The cities are numbered from $$$1$$$ to $$$n$$$. Only some of roads are used to ship magic crystals. It is known that the crystal mine is located in city $$$m$$$. The number of possible routes from city $$$m$$$ to other cities is represented by vector $$$D$$$, where $$$D[i]$$$ is the number of different routes from city $$$m$$$ to city $$$i$$$.

Write a program that will plot a possible shipments map based on given data ($$$n, m$$$, and vector $$$D$$$). If there are several possible maps, any one of them is acceptable.

«Your passion for gambling will do you no good,» Bob said as he agreed to play one more game with Alice.

The rules of the game are the following: players have a set of $$$n$$$ positive integers. They take turns. During each move, the player (either Alice or Bob) must choose two subsequent numbers and divide each of them by they greatest common factor other than $$$1$$$. If one of the players is unable to make a move, he or she loses. The question is the following: who will eventually win if both players do their best? Do not forget that Alice always starts first.

A student named Vasily had to solve the following problem during his Unified State Exam in Computer Science.

Executor $$$A17$$$ works with three commands numbered $$$1$$$ through $$$3$$$:

1. Add $$$1$$$ to the current value
2. Add integer $$$x$$$ to the current value ($$$x \gt 1$$$)
3. Multiply the current value by $$$7$$$.

The first command adds $$$1$$$ to the number on the screen, the second one adds $$$x$$$, and the third one multiplies it by $$$7$$$.

Program for Executor $$$A17$$$ contain a sequence of commands numbered $$$1$$$ through $$$3$$$. Executor $$$A17$$$ transforms the number on the screen in accordance with the given sequence of commands. The first value is always $$$1$$$. The final result of running the program is $$$N$$$.

After pondering on the subject for a while, Vasily calculated the value of $$$K$$$ – number of program options for Executor $$$A17$$$ resulting in a certain number $$$N$$$. For example, when $$$x = 5, N = 7$$$, the number of options $$$K = 4$$$ (numbers of commands):

• 1, 1, 1, 1, 1, 1;
• 2, 1;
• 1, 2;
• 3.

After the exam, Vasily started wondering how to calculate the number $$$x$$$ based on input data $$$N$$$ and $$$K$$$.

Write a program that will determine the smallest number x meeting the problem's requirements based on given numbers $$$N$$$ and $$$K$$$.

The task is to punch n identical holes along the central axis of a narrow paper tape. The holes should be $$$1$$$ cm apart and $$$n$$$ identical holes must be punched (where $$$n$$$ is always an even number). A hole punch always makes two holes at once, $$$k$$$ cm apart. Let's count that it is prohibited to make one hole with the punch. The available set of hole punches covers all possible distances between the holes, i.e. $$$k=1, k=2, k=3$$$, etc. Your task is to write a program that will use the number $$$n$$$ to list hole punches with the distance $$$k$$$ suitable for the job.

The distance between points $$$a = (a_1, a_2, \dots, a_n)$$$ and $$$b = (b_1, b_2, \dots, b_n)$$$ in an $$$n$$$-dimensional space is determined according to the Euclidean metric: $$$$$$dist(a, b) = \sqrt{(a_1-b_1)^2 + (a_2-b_2)^2+ \dots + (a_n-b_n)^2}.$$$$$$ Some optimization tasks require calculation of partial distance between points – only for coordinates with indices within a certain range $$$[i, j]$$$: $$$$$$dist(a, b, i, j) = \sqrt{(a_i-b_i)^2 + (a_{i+1}-b_{i+1})^2 + \dots + (a_j-b_j)^2}.$$$$$$ Such calculations can be performed multiple times. Write a program that will efficiently calculate partial distance based on given points.

In an effort to master their skills, participants in the programming championship regularly solve the "Tower of Hanoi" problem. All teams use the standard classical algorithm of moving, consisting of $$$2^N-1$$$ moves.

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; 

We have the intermediate results that some teams have achieved. All results are represented as rows of length $$$N$$$ (the number of disks), where element $$$i$$$ of the string is the symbol denoting the rod on which disk $$$i$$$ is located. For instance, let $$$N = 4$$$. Then the record $$$"BBCA"$$$ means that the first and second disks are on rod $$$B$$$, the third disk on rod $$$C$$$ and the fourth on rod $$$A$$$. The table below shows all the $$$7$$$ moves necessary to solve the Tower of Hanoi puzzle with three disks. $$$$$$ \begin{array}{|c|c|} \hline \text{Move No} & \text{Distribution of disks among the rods} \cr \hline 0 & AAA \cr \hline 1 & BAA \cr \hline 2 & BCA \cr \hline 3 & CCA \cr \hline 4 & CCB \cr \hline 5 & ACB \cr \hline 6 & ABB \cr \hline 7 & BBB \cr \hline \end{array} $$$$$$ Write a program that will identify the number of the team with the maximum amount of moves in the Tower of Hanoi. If there are several such teams, determine the number of the first one.

In a country set among forests, there is a small village consisting of $$$N$$$ houses. The people of this village are mainly engaged in animal husbandry, raising goats and sheep. The village consists of houses of different shapes and sizes. The villagers have only one problem – wolves attacking their livestock. In order to protect their property and provide security, the residents have decided to build a single fence around the village. For the residents it is very important to minimize the length of the fence, thereby reducing the cost of construction. Nevertheless, they want the fence to be at least $$$R$$$ meters away from each house. The shape of house $$$i$$$ is defined by a set of $$$K_i$$$ vertices $$$(a_j, b_j)$$$ of a polygon with real coordinates. Write a program that will compute the minimum length of the fence.