Many puzzles (Sudoku, towers, etc.) require filling the square field $$$ n \times n $$$ with numbers in such a way that in each row and each column the numbers $$$ 1...n $$$ occur exactly once. For the computer construction of such puzzles, it is necessary to be able to generate a square field with the specified property.

Write a program, that given the first row, fills in the remaining cells of the table so that each row and each column contain all the numbers from $$$ 1 $$$ to $$$ n $$$.

Igor and Ira decided to determine the head of the family, for this they will hold an archery tournament. The tournament is held according to simple rules: each of the participants shoots $$$n$$$ times (the first participant makes all his shots, then the second). Target — a circle consisting of $$$k$$$ rings, $$$1$$$ to $$$k$$$ points are given for hitting each of them. The head of the family is the one who scores more points.

Igor has already made his $$$n$$$ shots and scored $$$p$$$ points. Now it's Ira's turn. She has already adapted to archery, and now she always hits the target, unlike Igor. Ira hits each ring with the same probability.

Help Ira determine the number of winning combinations from $$$n$$$ shots.

Many recurrent sequences acquire new interesting properties if they are calculated modulo of some number. Due to the finiteness of the division residues, sequences turn into cycles or loops. The Fibonacci numbers are a good example of a looping sequence. The Fibonacci sequence is defined by the recurrence relation $$$ F_i = F_{i-1} + F_{i-2} $$$, where $$$ F_0 = 0, F_1 = 1 $$$.

When calculating such a sequence taken modulo $$$ n $$$, after a certain number of steps, there is a return to the initial values of $$$ 0 $$$ and $$$ 1 $$$. The minimum number of steps required to loop the sequence is denoted as $$$ \pi(n) $$$ and is called the Pisano period. The number $$$ \pi(n) $$$ exists for any $$$ n $$$. For each $$$ \pi(n) $$$ is valid $$$ F_{i} \equiv F_{i+\pi(n)} (mod~n) $$$ with any $$$ i $$$.

The relationship between the length of the Pisano period $$$ \pi(n) $$$ and the number $$$ n $$$ itself is quite complex and comes down to calculating Pisano periods for prime numbers. For a prime number $$$ p $$$, the value of $$$ \pi(p) $$$ is calculated according to the following rules:

1. Two special cases are distinguished: $$$ \pi(2) = 3 $$$ – the only period with an odd length, and $$$ \pi(5) = 20 $$$.
2. If $$$ p \equiv \pm 1 (mod~5) $$$, then $$$ \pi(p) $$$ will be the divisor of the number $$$ (p - 1)$$$.
3. If $$$ p \equiv \pm 2 (mod~5) $$$, then $$$ \pi(p) $$$ will be a divisor of $$$ (2p + 2)$$$.

A thin stream of sand is poured into a conical fire bucket with a height of $$$ h $$$ and an upper diameter of $$$ d $$$. The sand is poured strictly into the center of the bucket, installed vertically, and forms a pile. As soon as the top of the pile reaches the upper edge of the bucket, the process stops. Find the volume of sand poured into a bucket if it is known that the angle at the base of a pile of sand poured onto a flat surface is 34 degrees.

Today Igor and Ira together with friends  — Sasha and Lesha — are playing a new board game "Brass Birmingham".

In each round, the players take turns making moves. During the turn, the player can build one industry per city, a road connecting two cities, or perform an action. Players pay money for all their buildings in this game, as in the real world, everything costs money. At the end of his turn, the player builds a tower of spent coins and puts it next to his figure in the payment field, and at the end of the round, the spent coins are returned to the bank.

Igor wants to start the next round as soon as possible, so he decided to optimize the process of returning money to the bank. In one operation, he collects coins of the same nominal from all the tops of the towers. How often does Igor need to repeat this operation to start a new round as quickly as possible?

Today Igor and Ira with their friends Sasha and Lesha decided to play a new board game "Brass Birmingham".

In each round, the players take turns making moves. During the turn, the player can build one industry per city, a road connecting two cities, or perform an action.

To perform an action or build something, each player has $$$K$$$ cards in their hands. There are two types of cards: cards of cities with the name of a certain city, allowing to build any industry in a given city, and cards of industries that allow to build a given industry in any city, to which there is a player's road.

Igor keeps to his strategy and wants to put a steel plant in the city of Birmingham, which has the number 1. In his opinion, if one puts a steel plant in this city, then he wins the game for sure.

According to the rules of the game, all players take turns, this time Igor will go last. In this round, all players can build either one building or a road (they do not want to do actions).

According to the rules, the player can build a building in the city:

1) If a player has a card of the corresponding city, then he plays it and discards it from his hand.

2) If the player has a card with the corresponding industry and there is either a building in this city or the road of this player leading to this city. This card is also played and discarded.

Igor understands that the other players will definitely build a steel plant in Birmingham to stop him if they have the opportunity.

Igor writes down the entire course of the game in his notebook, so he knows which cards have already left the game, as well as he knows how many cards there were originally for each city and each industry.

With what probability will Igor be able to build a steel plant in the city of Birmingham?

Today Igor and Ira with friends  — Sasha and Lesha — decided to play a new board game "Brass Birmingham".

In each round, the players take turns making moves. During the turn, the player can build one industry per city, a road connecting two cities, or perform an action.

In his turn, Igor wants to open as many of his factories as possible. To open one factory, the player needs to transfer exactly one barrel of "beer" to the factory, because without a barrel of "beer" it will not be possible to have a formal opening. Thus, the more barrels of "beer" Igor transfers, the more factories he will be able to open.

Barrels of "beer" are in breweries previously built by players. Each brewery has exactly one barrel of "beer".

Igor wants to use his barrels of "beer", which he has prepared earlier, to open factories. If they are not enough, then Igor will have to use the barrels of other players.

The rules of the game state that one can use barrels of "beer" from his breweries without any restrictions. If the player wants to move a barrel of "beer" from someone else's brewery to build his factory, then this action can be done only if the factory and the brewery are in the same city, or there is a road path between the brewery and the factory.

How many of his own and other people's barrels of "beer" will Igor use?

Today Igor and Ira with friends — Sasha and Lesha — decided to play a new board game "Brass Birmingham".

In each round, the players take turns making moves. During the turn, the player can build one industry per city, a road connecting two cities, or perform an action.

The game ended late at night, and it was time to sum up the results. Igor was in charge of counting points for building roads. Each road built by the player earns him several points equal to the total number of industries opened in the cities connected by this road.

Unfortunately, Igor accidentally knocked over the playing field so that all the cards got mixed up. Igor was disappointed. He remembered that during the game, he wrote down the actions of each player in a notebook. Help Igor count the points for the roads received by each player.

In 1932, Lothar Collatz formulated a seemingly simple problem that has not been solved yet. Suppose we have some number $$$ n $$$, then if it is even, we divide it by $$$2$$$, and if it is odd - multiply it by $$$3$$$ and add one. Let's call this transformation a Collatz step. The hypothesis, which has not been proven, states that after a certain number of steps, any integer turns into one. For all numbers up to $$$ 10^{22} $$$, it is proved to be true.

Denote by $$$ t(n) $$$ the number of steps necessary for the number $$$ n $$$ to turn into one, and write down the consecutive values $$$ t(1), t(2), t(3), \dots $$$: $$$ 0, 1, 7, 2, 5, 8, 16, 3, 19, 6, 14, 9, 9, 17, 17, 4, 12, 20, 20, \dots $$$

Analyzing the given sequence, you can find that it very often contains pairs of identical values, so that $$$ t(i) = t(i + 1) $$$. According to some estimates, up to half of the sequence elements form such pairs. There are also longer segments of repeating values, for example, the first triple occurs already at $$$28$$$-th place $$$ t(28) = t(29) = t(30) = 18 $$$.

Write a program that, on an interval of length $$$ w $$$, starting with the element $$$ s $$$, finds the longest segment of the same values $$$ t() $$$. If there are several such segments, then you need to find the leftmost of them (with the minimum first element). Elements falling outside the range $$$ [s, s + w - 1] $$$ are not taken into account.

Professor Sh. has recently become interested in number theory. In particular, he was very interested in the decomposition of a number into prime factors. Recall that a natural number is called a prime number if it has exactly two distinct natural divisors: 1 and the number itself. Professor Sh. calls a number N interesting if it can be presented as a product of exactly six pairwise distinct primes. Unfortunately, the professor does not know how to check too large numbers for interest.

Help Professor Sh. – write a program that based on a given number N will find if it is interesting.

Igor wants to improve self-organization, so he decided to make a huge to-do list and a plan that he will stick to for $$$k$$$ days.

There were $$$n$$$ tasks in the list. Igor considered it necessary to repeat the task number $$$i$$$ from this list after $$$a_i$$$ days to develop a habit. Having decided on the list and the frequency of repetition of tasks, Igor immediately completed all tasks from the list, only to repeat them in the future. Therefore, he was very tired and completely forgot to make a plan for the next $$$k$$$ days.

Help Igor make a plan by specifying for each of the following days the number of tasks that Igor needs to complete.

Working with permutations of numbers from $$$ 1 $$$ to $$$ n $$$, programmer Vasya noticed that some of them have interesting properties. For example, in the permutations "3 1 2" and "3 2 1", the first element is equal to the sum of all other elements. In the permutation "1 2 3 4 5" already the concatenation (attribution of one number to another) of the first two elements is equal to the sum of the remaining ($$$ 12 = 3 + 4 + 5 $$$). Vasya wondered: is it possible for any $$$ n $$$ to find such a permutation of the numbers $$$ 1..n $$$ that the first element, or the concatenation of the first two, will be equal to the sum of the remaining ones?

Write a program that, based on a given number $$$ n $$$, finds which elements need to be put at the beginning of the permutation so that either the first element or the concatenation of the first two will give the sum of all the remaining ones. If there are no such elements, then the program should report the absence of a solution.

There are two billiard balls on a carom table (billiard table without pockets) with length of $$$ l $$$ and width of $$$ w $$$. The balls are located at the points $$$(x_1, y_1)$$$ and $$$(x_2, y_2)$$$, where $$$ 1 \leq x_i \lt l, 1 \leq y_i \lt w $$$, and the coordinate axes go along the sides of the table (the abscissa axis is along the "long" side, the ordinate axis is along the "wide"). It is necessary to get the first ball into the second, contacting exactly three rail cushions. For simplicity, we will assume that the balls are points, the angle of reflection of the ball does not depend on the force of impact and is equal to the angle of hitting the cushion. When the ball hits exactly the corner, it is reflected strictly in the opposite direction, and it is considered that the ball hit both cushions forming the corner. A hit is considered to be an exact match of the coordinates of the points. Write a program that calculates the impact of the first ball, which, after reflecting off the rail cushions three times, hits the second one, and overcomes the minimum distance at the same time.

Помимо теории чисел и строковых алгоритмов Профессор Ш. любит заниматься массивами, но не простыми, а отсортированными по неубыванию элементов. Сегодня Профессор Ш. придумал отличную задачу и делится её формулировкой с вами.

Изначально имеется массив $$$a$$$, состоящий из $$$N$$$ чисел, элементы которого расположены в порядке неубывания. К данному массиву можно применять запросы $$$2$$$ типов:

1. Сдвинуть массив циклически влево или вправо на $$$k$$$ позиций.
2. Проверить, есть ли в массиве число $$$x$$$. Если такое число есть, вывести его номер в массиве (возможно, измененном). Если число входит в массив несколько раз, следует вывести номер его первого вхождения в массив.

Так как Профессор Ш. умеет работать только с отсортированными массивами, он не всегда умеет проверять, есть ли в массиве число $$$x$$$. Помогите Профессору – напишите программу, которая будет верно отвечать на запросы обоих типов.

Professor Sh. is quite old, he has a grandson named Vlad, who studies at the Golovda State University. To prevent exhaustion from studying, sometimes one needs to take a break from it. Vlad does not waste time on stupid computer games, spending all his free time playing "Sea Battle" against his grandfather.

The idea of the game is the following: there is a grid of $$$10 \times 10$$$, on which $$$10$$$ ships are placed: $$$4$$$ single-deckers, $$$3$$$ double-deckers, $$$2$$$ three-deckers and $$$1$$$ four-decker, ships on the grid can only be placed horizontally or vertically. Vlad is a virtuoso of this game, so he never loses. We are only interested in the events that take place on the grid of Professor Sh. During the game, Vlad can query the following commands:

1. command "SHOT $$$X~Y$$$" - shoot into a square with coordinates $$$(X, Y)$$$ $$$(1 \le X \le 10, 1 \le Y \le 10)$$$.
2. command "SHOW" - output the number of undamaged, hit, and sunk ships on the grid of Professor Sh.