Dilation – is one of the simplest methods of morphological image processing. Its main purpose is to expand image objects by applying some kernel.

Suppose we have some initial image $$$A$$$ consisting only of black (objects) and white (background) pixels. If a $$$3 \times 3$$$ kernel is used for dilation, then in the target image $$$B$$$ the pixel $$$B_{i, j}$$$ will be black if it was black in the source image ($$$A_{i, j}$$$ is black) or at least one was black from neighboring pixels (some neighbors may not exist): $$$A_{i - 1, j - 1}$$$, $$$A_{i - 1, j}$$$, $$$A_{i - 1, j + 1}$$$, $$$A_{i, j - 1}$$$, $$$A_{i, j + 1}$$$, $$$A_{i + 1, j - 1}$$$, $$$A_{i + 1, j}$$$ or $$$A_{i + 1, j + 1}$$$.

Let's assume that you have a processed $$$B$$$ image. Can you restore the original one? Write a program that, based on the image $$$B$$$, builds the image from which $$$B$$$ came after dilation using a kernel of size $$$3 \times 3$$$, if possible.

The grandson of Professor R. Vanya downloaded the game 'Destroy them all!' and plays it all day long.

The game has a checkered field of size $$$n \times m$$$. It contains $$$k$$$ cells. The player can select any unmarked cell of the field and destroy all the marked cells exactly in one of the directions (left, right, above, below it). The grandson really wants to know the maximum number of cells he can destroy in one move at the current state of the field, but he is still too young to calculate this number. Help him – find the maximum number of cells that can be destroyed in one move if the coordinates of the $$$k$$$ marked cells are known.

Vasya has been very interested in exploring other planets since childhood. Growing up, he was able to fulfill his dream and participate in the launch of a meteorological station to Mars. Unfortunately, an error was made during the assembly of the station. To even greater regret, it was discovered after the station started working on the surface of the planet.

The problem lies in the data from an ultra-sensitive temperature sensor capable of receiving readings with an accuracy of up to millionths of a degree. Vasya was instructed to try to solve the problem.

The sensor takes data every second and sends readings to Earth as a series of 32-bit integers. The series consists of $$$n$$$ sequential temperature measurements $$$t_1, t_2, ..., t_n$$$.

After watching the video of the satellite assembly, Vasya found out that some sensor connectors were connected backward ; as a result, some bits are transmitted in an inverted form ($$$0$$$ instead of $$$1$$$ and $$$1$$$ instead of $$$0$$$). Also, in all measurements, these bits have the same numbers (the numbering of bits traditionally starts with the least significant one, which has the number $$$0$$$). It is not clear from the video which bits are being transmitted incorrectly, but Vasya decided to try to determine them from the data received.

Vasya has a series of measurements consisting of $$$n$$$ obtained distorted numbers $$$t_1, t_2, ..., t_n$$$. From the readings of other devices, it is known that the temperature first rose and then fell during the measurement process. Vasya wants to try to select some value $$$k$$$ and apply $$$t_i$$$ to the elements using the xor operation (bitwise exclusive «OR»): $$$r_i = t_i \, xor \, k$$$. The resulting sequence $$$r_1, r_2, ..., r_n$$$ should behave like the Martian temperature. First, it does not decrease and then does not increase, and the intervals of non-decreasing and non-increasing must be of length at least 2 (the intervals themselves can intersect).

Write a program that helps Vasya find the number $$$k$$$.

In nature, DNA molecules are responsible for the transmission of hereditary information. The structure of DNA is simple and complex at the same time – its molecules are two long polymer strands bonded together in a double helix. Each DNA strand is built based on only four nucleotides: Adenine (A – Adenine), Guanine (G – Guanine), Thymine (T – Thymine), and Cytosine (C – Cytosine). It is customary to encode nucleotides in capital Latin letters and write their sequence as a line. For example: «ACTG».

In the first strand, nucleotides are connected sequentially in any order. Still, the second strand of the helix is built strictly on the principle of complementarity: Adenine always forms a pair with Thymine (A–T or T–A) and Cytosine with Guanine (C–G or G–C). So, a nucleotide located at a particular place in the first strand uniquely defines a nucleotide situated at the same place in the second strand.

For example, if one strand consists of «ACTGTAC» nucleotides, then the second will have the form «TGACATG».

This method of recording information is redundant and, in some places, ambiguous. For example, it may happen that the same sequence of nucleotides occurs in the first strand in one direction, in the second strand – in a different place and in exactly the opposite direction.

Write a program that, based on the sequence of nucleotides in one strand, will determine the longest subsequence of consecutive nucleotides that also occurs in the complementary strand, but in the reverse sequence. The location of the searched subsequence is not important.

Positive integers that are convenient for forming various measurement systems are called practical. A positive integer $$$x$$$ will be practical if any natural number less than $$$x$$$ can be represented as the sum of any different divisors of $$$x$$$.

For example, the number $$$6$$$ is practical since using the sum of its divisors $$$1, 2, 3, 6$$$, you can represent any number from $$$1$$$ to $$$6$$$: $$$1 = 1$$$, $$$2 = 2$$$, $$$3 = 3$$$, $$$4 = 1 + 3$$$, $$$5 = 2 + 3$$$, and $$$6 = 6$$$.

On the other hand, the number $$$9$$$ is not practical since, using its divisors $$$1, 3, 9$$$, it is impossible to represent the numbers $$$2, 5, 6, 7$$$ and $$$8$$$.

There are infinitely many practical numbers, and they have many useful properties. In particular:

• the product of two practical numbers is also always a practical number;
• if $$$p$$$ is a practical number, and $$$d$$$ is some kind of its divisor, then their product $$$p \cdot d$$$ is also a practical number;
• one is the only odd number among practical number.

Among the practical numbers, primitive practical numbers stand out - those that cannot be obtained from other practical numbers by multiplying them or multiplying a practical number by any of its divisors.

Write a program that, by the number $$$n$$$, returns the $$$n$$$-th largest primitive practical number.

Alexander hosted tournaments in the sports version of the game "What? Where? When?" for a long time.

In sports version of "What? Where? When?" several teams of 6 people play simultaneously. The host asks a question, after which, within 60 seconds, the teams must come up with an answer to it and write it down on the answer form. After a minute to think, players have 10 seconds to hand over the forms to the moderator.

Sasha is collecting questions for a new game. The game consists of $$$R$$$ rounds, with $$$Q$$$ questions in each round. There is a database of $$$N$$$ questions; for each question, it is known how many teams tried to answer the question and how many teams answered it incorrectly. Based on this data, a question rating is calculated for each question: the proportion of incorrect answers to the question is counted, multiplied by 10000 and rounded down to an integer. The easiest question has the lowest rating. Sasha wants to form a pack of questions for the game according to the following rules:

• There must be at least one question in the package with a rating less than $$$L$$$. This question is called "candle" and is answered correctly by almost all teams. If there are several candidates for such a question, then "candle" is the question with the lowest rating among the candidates. A question with a minimum rating in the database may not be a "candle".
• There must be at least one question in the package with a rating of more than $$$C$$$. Such a question is called "coffin", and only the best teams answer it correctly. If there are several candidates for such a question, then "coffin" is the question with the highest rating among the candidates. The question with the highest rating in the database may not be "coffin".
• The "candle" question should be in the first half of the game.
• The "coffin" question should be in the middle of the game. If the number of questions in game is even, then the "coffin" can be any question in the middle.
• Round ratings should strictly increase to the middle of the game (in the first half), then strictly decrease (in the second half). The rating of each round is the rounded down arithmetic mean of the round questions' ratings.
• The game needs to be diverse. If we order all the questions in the game by rating $$$Q_1 \le Q_2 \le \dots \le Q_{RQ}$$$, then the complexity of any two consecutive questions $$$Q_i$$$ and $$$Q_{i+1}$$$ satisfies the inequality $$$Q_{i+1} - Q_i \ge D$$$, where $$$D$$$ is the diversity coefficient.
• If there are more than 2 questions in a round, the question ratings cannot strictly increase or strictly decrease.
• If you order all the questions in the game by rating $$$Q_1 \le Q_2 \le \dots \le Q_{RQ}$$$, then the complexity of any two consecutive questions $$$Q_i$$$ and $$$Q_{i+1}$$$ should not differ by more than $$$S$$$.

Help Sasha: form a pack of questions for the game, that satisfies the rules above.

Veronica loves to play with her toys. Cubes are one of her favorite toys.

Veronica builds towers, pyramids, and many other forms from multi-colored cubes. Today, Veronica wants to build a tower of $$$n$$$ cubes in height. Veronica has unlimited quantities of red, green, and blue cubes. Veronica wants to build a beautiful multi-colored tower, so she wants the tower to have no more than $$$k_r$$$ in a row of red cubes, $$$k_g$$$ in a row of green cubes, and $$$k_b$$$ in a row of blue cubes.

Help Veronica to determine how many different towers with a height of $$$n$$$ cubes she can build. Since this number may be very large, print the answer modulo $$$10^9 + 7$$$.

Veronika has a huge number of toys – as many as $$$n$$$ pieces. Veronica decided to determine which toys she liked the most. To do this, she put all $$$n$$$ toys in one row. She gave the first toy a value equal to $$$a_1$$$. She gave each next toy a value according to the following rule:

where $$$k$$$, $$$p$$$  — beauty parameters. Veronica wants to find out the five largest values from the whole set of her toys. Help her in this difficult task.

Line pinball is played with $$$n$$$ metal balls having weights of $$$1, 2, 3, ..., n$$$ grams. Along a straight line, there are $$$n + 1$$$ holes equipped with plungers. The holes are numbered from left to right with numbers from $$$0$$$ to $$$n$$$.

Each plunger is inclined to the right and has its impact force $$$p_i$$$, where $$$i$$$ is the number of the hole. The design and inclination of the plunger are such that if it hits a ball with a mass of $$$x$$$ grams with force $$$p_i$$$, then the ball will move into the hole numbered $$$i + \lfloor p_i / x \rfloor$$$, where $$$\lfloor ... \rfloor$$$ means round down to a lower integer.

The game begins with one of the balls being placed in the starting hole numbered $$$0$$$. Next, the plungers of all the holes into which the ball falls are used sequentially. The game ends and is considered successful when the ball hits the hole number $$$n$$$. The game is considered lost if, at some point, the force of the plunger is too small to throw the ball into another hole or too strong and throws it further than the hole number $$$n$$$.

Write a program that selects the impact force $$$p_i$$$ for all $$$n$$$ plungers so that any ball with a mass from $$$1$$$ to $$$n$$$, starting from hole $$$0$$$, ends up in hole $$$n$$$.

Veronika really likes to visit shops because there are a lot of different colorful items. Arriving at the shop, Veronica first asks her dad to pick her up. As soon as Veronica is picked up, she immediately begins to command where to go. To do this, Veronica points her finger in the direction to go and says the word «there». Dad, of course, is happy to carry Veronica in his arms and goes in the direction shown by Veronica, but only until he meets an obstacle in the form of another customer, a shelf, or a wall.

For simplification, the shop can be represented as a rectangular matrix of size $$$n \times m$$$. Each cell of the shop can be empty and marked with the symbol «.», or occupied «#». Initially, Veronica is in the Dad's arms in the bottom left cell with coordinates $$$x$$$ equal to 1 and $$$y$$$ equal to 1. Veronica can show one of the four directions in letters, setting the movement: «U»  — increasing the coordinates of $$$x$$$, «D»  — decrease of the $$$x$$$ coordinate, «R»  — increase of the $$$y$$$ coordinate, «L»  — decrease of the $$$y$$$ coordinate.

Find the coordinates of Veronica and her dad after following all the instructions.

Before the appearance of Veronica, Igor and Ira chose a stroller for a long time. The stroller should satisfy many parameters: it should be comfortable, warm, stable, and multifunctional. One of the essential criteria is its size when folded.

For transportation during the trip, the stroller must be located in the trunk of the car. The trunk is a rectangle with the size $$$a \times b$$$. The stroller must be transported only folded to not damage it. When folded, the stroller occupies a space of $$$c \times d$$$. Igor wants to find out if a folded stroller will fit in the trunk. Help him - write a program to determine whether it can be done.

Veronica is very good at drawing and coloring pictures. Igor and Ira bought her a new bee coloring book.

The coloring consists of $$$n$$$ lines, each contains exactly $$$m$$$ cells. Each cell is a regular hexagon, like a honeycomb in bees, and has no more than 6 neighbors. As an example, the $$$5 \times 5$$$ field looks like this:

Initially, some cells in the coloring are already colored. Veronica wants to get a continuous line of colored cells that connects the first row with the $$$n$$$-th row by coloring the minimum number of cells.

A group of n students decided to go to the cinema. They bought a whole row of seats in the cinema for n places in advance. Of course, some seats for students are preferable to others. Therefore, each student knows the number of a seat he wants to sit in. Moreover, it is known that a student will be dissatisfied if he sits in the wrong place. You need to seat the students so that the total dissatisfaction is minimal.

A keen entomologist, Vasya studied an ant population in the neighboring forest. He discovered a huge anthill and, after spending a lot of time, determined that $$$k$$$ ants lived in it.

Due to the imposed quarantine, Vasya could not continue his field research. However, Vasya knows that there are $$$n$$$ anthills in total in the forest, which means that one may try to apply Zipf's law to estimate their size.

Zipf's law states: if $$$k$$$ insects live in the largest anthill, then in the second largest will be approximately half as many ($$$k / 2$$$), in the third three times less ($$$k / 3$$$), and in the $$$i$$$-th largest will live $$$i$$$ times less than ($$$k / i$$$).

Vasya made a forecast – a series of integers $$$c_1, c_2, ..., c_n$$$, where $$$c_i = k / i$$$, rounded to the nearest integer (according to mathematical rules, that is, numbers like $$$1.5, 2.5, ... $$$ were rounded up).

Unfortunately, the ants living on the home ant farm did not appreciate the researcher's impulse and damaged his notes. The saddest thing is that the original number $$$k$$$ was also damaged. However, some of the $$$c_i$$$ numbers have been preserved. Help Vasya recover the lost data.

Write a program that uses the preserved records $$$c_i$$$ to find the minimum initial number $$$k$$$. If there are several such numbers, print the minimum of them.