Igor is renovating again! Once more! This wallpaper! It's everywhere! On every wall!

This renovation is maddening; the next stage of wallpapering has begun. Igor has a very unusual house: it has $$$n$$$ walls, each is $$$3$$$ meters high and $$$a_i$$$ meters wide. Igor came to the hardware store to buy wallpaper. It turns out that there is an infinite number of rolls, each measuring $$$k$$$ meters wide and $$$3$$$ meters high. Our hero wants to save money, so he wants to buy as few rolls as possible. To wallpaper each wall, Igor decided to buy enough rolls so that, for each of wall, all but possibly one roll would be used to its full width of $$$k$$$. If a section less than $$$k$$$ meters wide remains uncovered with wallpaper, Igor cuts the needed piece from a full roll and then doesn't use that roll again for aesthetic reasons (yes, he wants to save money on buying rolls, but not too much). Help Igor calculate how many rolls of wallpaper he needs.

Inspired by the matches of the World Classic Tetris Championship, Professor R.'s grandson found Professor R.'s old game console in the pantry and a Tetris cartridge in it. The cartridge game starts at level zero, tetris (clearing four full rows from the playing field) gives 10 points. Every time the player clears 10 rows, the game advances to the next level, and then the score for tetris increases by 10 points. The Professor's grandson became curious: at which level will he be when his total score reaches at least $$$X$$$ points if he clears rows only by making tetrises? Help the grandson by writing a program that determines the level number at the moment his score becomes at least $$$X$$$, as well as the total number of points earned.

The level map of a certain game is a rectangular maze with the size of $$$N \times M$$$ cells. The player needs to move from the top-left cell to the bottom-right cell. In one move, the player can step to a side-adjacent cell, if there is no obstacle in it.

After reviewing the game results, the game designer determined that the shortest path from the top-left to the bottom-right cell was too short. Therefore, he wants to place an additional obstacle in one of the free cells so that the shortest path becomes longer, but still exists. Find all possible ways to do this.

Student Vasya is preparing to submit a physics lab report and decided to slightly embellish the data obtained as a result of the experiment. During the work, Vasya measured a certain value and recorded the results as a sequence of integers $$$ A = (a_0, a_1, a_2, ..., a_{n - 1}) $$$. Vasya wants to leave in the sequence only those measurements that form an oscillating subsequence $$$ B = (b_0, b_1, b_2, ..., b_{k - 1}) $$$. A sequence is considered oscillating if every element (except the first and the last) is either strictly greater than both of its neighbors $$$(b_{i-1} \gt b_i \lt b_{i+1})$$$ or strictly smaller than them $$$(b_{i-1} \lt b_i \gt b_{i+1})$$$. Help Vasya – write a program that, for a sequence $$$ A = (a_0, a_1, a_2, ..., a_{n - 1}) $$$, finds its longest oscillating subsequence $$$ B $$$ with a length of at least three.

The input to your program is a valid arithmetic expression that can contain only integers in the range from 0 to 1000, parentheses, and the signs of binary operations '+' and '-'. There are no unary operations.

You are allowed to change any plus sign to a minus sign, and any minus sign to a plus sign. Change the signs so that the value of the expression is as small as possible.

Professor R.'s grandson enjoys watching the classic Tetris World Championships. For anyone who might have forgotten what classic Tetris is, let's take a moment to refresh your memory.

The Classic Tetris World Championship (CTWC) is a video game competition series organized by the Portland Retro Gaming Expo. It was first held in 2010 during the production of the film "Ecstasy of Order: The Tetris Masters". The championship's goal is to determine the world's top Tetris player. For its first two years, the championship took place in Los Angeles, California, but then it moved to Portland, Oregon, where it has been held annually since 2012.

Participants in the tournament compete using the 1989 Nintendo version of Tetris on the Nintendo Entertainment System, played on specialized TVs. The final rounds are streamed online and displayed on screens, with a head-up display added to enhance the viewing experience for the audience.

Let's recall how the game "Tetris" works. There are 7 types of tetramino shapes in the game, each identified by a specific letter (see the image below).

In Tetris, random tetromino shapes fall from the top into a rectangular playfield that is 10 cells wide and 20 cells high. While the piece is falling, the player can rotate it 90 degrees or move it horizontally. It's also possible to "drop" the piece – to make it fall faster once its landing spot is decided. Each piece continues to fall until it lands on another piece or reaches the bottom of the playfield. When a horizontal row of 10 cells is completely filled, it disappears, and all blocks above it shift down by one row. A preview of the next piece is also shown, allowing the player to plan their moves ahead. As the game progresses, the speed gradually increases. The game ends when a new piece can no longer fit into the playfield. Players earn points for each filled row, so the main goal is to complete as many horizontal lines as possible while preventing the playfield from filling up vertically, maximizing their score.

In the Classic Tetris World Championship, players start at level 18, where a player gets 760 points for one filled row, 1900 points for two filled rows, 5700 points for three, and 22800 points for tetris (four filled rows). Once the player clears at least 130 rows, the number of points per row increases by 40, for two rows by 100, for three rows by 300, for tetris by 1200. At the same time, the player advances to level 19, where the falling speed of the pieces also increases. Every time the total number of cleared lines reaches 140, 150, and so on, the player moves up another level, with the points increasing by the values indicated earlier.

Professor R.'s grandson wrote down the game log of the winner of the match he has just watched, but he forgot how many points the winner scored. Help him determine how many points the winner earned by the end of the game.

Student Misha became interested in card tricks, but unfortunately, he never managed to learn professional card shuffling. Since he is studying programming, he came up with the following algorithm for shuffling a deck of cards:

1. Place the deck face down on the table.
2. Remove the cards one by one from the top of the deck and distribute them into $$$k$$$ piles in order: the first card goes to the first pile, the second card to the second pile, the third card to the third pile, and so on $$$k$$$-th card to the $$$k$$$-th pile. The $$$(k+1)$$$-th card goes to the first pile, the $$$(k+2)$$$-th to the second, and so forth.
3. When placing a card on a pile, it goes on top of the existing cards in that pile. For example, the $$$(k+1)$$$-th card will be placed on top of the first card in the first pile.
4. Once all cards are distributed, the piles are stacked together to form a new deck: the first pile goes on top of the second, the second on top of the third, and so on, with the last $$$k$$$-th pile at the very bottom.
5. The resulting deck is considered shuffled.

For example, if we have a deck of $$$10$$$ cards numbered from $$$0$$$ to $$$9$$$, shuffling them into $$$3$$$ piles will get the following order: (from top to bottom) " 9, 6, 3, 0, 7, 4, 1, 8, 5, 2 ":

Trying to improve the shuffling, Misha applied this algorithm several times in a row and, to his surprise, found that consistent application of this algorithm always brings the cards back to their original order in the end. Only the number of applications of the algorithm depends on the number of initial cards $$$n$$$ and the number of piles $$$k$$$ used when everything returns to its original order. If $$$n = k$$$, then the order of the cards does not change at all.

To shuffle cards well, Misha wants to determine what minimum number of applications of the algorithm with $$$k$$$ piles a deck of $$$n$$$ cards will return to its original order.

The canonical full notation of an IP address in TCP/IP version 6 consists of 8 blocks of 4 hexadecimal digits each, separated by colons. However, this notation is very long, so there are several rules for shortening it:

• It is allowed to omit up to three leading zeros in each block of hexadecimal digits. For example, the address "0001:0000:0001:0000:0001:0000:0001:0000" it will be shortened to "1:0:1:0:1:0:1:0". If a block consists entirely of zeros, then it can be shortened to a single zero, but it cannot be completely empty.
• One, the longest sequence of consisting entirely of zeros consecutive blocks may be omitted, leaving two colons in its place "::". If there are several such sequences, any of them may be chosen, but only one. So, for example, the address of the loop from "0000:0000:0000:0000:0000:0000:0000:0001" can be shortened to "::1".

Operations can be applied to an IP address either separately or together, in any order.

In addition, there is a convention to use lowercase letters when writing the address.

Write a program that, given a shortened IP address, restores its full canonical notation.

More than anything, Professor R. loves working in the garden and even wants to retrain as an agronomist. Since gardening is a true passion of his life, and he just loves mathematics, he tries different ways to plant tomatoes.

The Professor's garden is a rectangle with its bottom-left corner at the point $$$(x, y)$$$, width $$$w$$$ (along the $$$Ox$$$ axis) and height $$$h$$$ (along the $$$Oy$$$ axis) and sides of the rectangle are parallel to the coordinate axes. The Professor can plant tomatoes only at points with integer coordinates in his garden (including the garden's boundary). Initially, he starts at the point with coordinates $$$(0, 0)$$$ and from there he can move to any point with integer coordinates located at a distance of $$$\sqrt{n}$$$, where $$$n$$$ is a number whose prime factorization contains $$$2$$$ to an odd power. From there, he can again move to another point with integer coordinates located at a distance of $$$\sqrt{n}$$$, and so on, so the Professor moves along the plane and plants tomatoes.

The Professor needs to prepare the seedlings for planting in advance; he wants to plant as many tomatoes as possible in his garden, and at the same time so that, after planting in the way described above, no seedlings remain unused — in other words, the number of seedlings must be equal to the number of points with integer coordinates in the garden that he can reach by stepping a distance of $$$\sqrt{n}$$$.

The Professor is on vacation and has not been doing calculations for a long time. Help him write a program that determines how many seedlings need to be prepared in order to plant as many tomato seedlings as possible at points with integer coordinates that can be reached from $$$(0, 0)$$$ by stepping on $$$\sqrt{n}$$$.

One day, Dunno came up with a new cube game – he lined up the cubes in a long line from left to right, and then removed pairs of adjacent cubes with a certain property. After removing a couple of cubes, the line on the right shifted to the left by two positions to fill the empty space. Dunno has exactly $$$n$$$ cubes, and each one is signed with a number from $$$1$$$ to $$$10^9$$$ (some cubes may be repeated).

Dunno experimented with various properties of pairs, but since he is currently studying the divisibility of numbers at school, he decided on the following rule: two adjacent cubes can be removed if the number on one cube is divisible by the number on the other cube (the order of the cubes in the pair is not important).

Unfortunately, with this formulation of the problem, a difficulty arises – not every line of cubes can be completely disassembled. Help Dunno – write a program that, given a preassembled line of cubes, will determine the minimum number of cubes that must be taken away so that the remaining cubes can be fully disassembled by removing pairs according to the rule used by Dunno.

Natural numbers are a fascinating subject of study, and mathematicians constantly confirm this by discovering more and more interesting patterns. Equally interesting are integer functions of natural numbers, such as factorials.

It is obvious that any natural $$$n$$$ can be represented as the ratio of two factorials: $$$$$$ n = \frac{n!}{(n - 1)!} .$$$$$$

It is also well known that some integers can be represented as the ratio of one factorial to the product of two others greater than 1: $$$$$$ n = \frac{a!}{b! \times c!} .$$$$$$

An example of such numbers are the binomial coefficients: $$$$$$ C_n^k = \frac{n!}{k! (n-k)!} \quad = \gt \quad 6 = \frac{4!}{2! \times 2!}.$$$$$$

Let us limit ourselves to considering factorials up to $$$ 50\,000! $$$, and numbers up to $$$ 1\,000\,000\,000 $$$. Write a program that, given a number $$$n$$$ , determines whether it can be represented as $$$$$$ n = \frac{a!}{b! \times c!}, $$$$$$ where $$$c \le b \lt a$$$.

Today in programming class, student Levodt learned about bit operations, specifically the "XOR" operation. This operation exists in all modern programming languages. For instance, in the languages $$$C\!+\!+$$$, $$$Python$$$, and $$$Java$$$, it is designated as "$$$ ^\wedge $$$", while in $$$Pascal$$$, it is designated as "xor". An example of the "xor" operation is: $$$10101_2 \oplus 10001_2 = 00100_2$$$. Note that "XOR" is similar to adding the corresponding bits of numbers modulo 2.

Levodt is given the following homework assignment: find any two numbers whose "XOR" equals a given non-negative number $$$N$$$.

He asks you to help in writing a program that can determine whether there are two natural numbers (not necessarily different), whose "XOR" equals the given $$$N$$$.

Memory managers are parts of operating systems and programming systems that manage memory allocation, deallocation, and optimize memory resources for processes. The lowest level of managers operates with pages of physical memory – fix-sized blocks of the same length, into which the entire available address space is divided.

Page managers must work very quickly and implement extremely simple algorithms. Develop a simple page manager that works according to the following rules:

1. Initially, a manager has $$$n$$$ free pages, numbered from $$$0$$$ to $$$n - 1$$$.
2. A manager can select pages only one at a time. Once a page is selected, it becomes occupied and cannot be selected again.
3. Each $$$i$$$th allocation request specifies a preferred page number $$$h_i$$$ – the page that the requester would like to obtain.
4. If the preferred page with the number $$$h_i$$$ is available, then the manager allocates it.
5. If the preferred page is occupied, then the nearest free one is allocated $$$r_i$$$, with a minimum difference of $$$|r_i - h_i|$$$. If there are 2 such pages, then the page with the lower number $$$r_i$$$ is selected.
6. After selecting the page, the manager marks it as occupied and returns its number $$$r_i$$$ as a response to the request.
7. It is assumed that the manager has enough free pages to satisfy all incoming requests.