Recently Monocarp got a job. His working day lasts exactly $$$m$$$ minutes. During work, Monocarp wants to drink coffee at certain moments: there are $$$n$$$ minutes $$$a_1, a_2, \dots, a_n$$$, when he is able and willing to take a coffee break (for the sake of simplicity let's consider that each coffee break lasts exactly one minute).

However, Monocarp's boss doesn't like when Monocarp takes his coffee breaks too often. So for the given coffee break that is going to be on minute $$$a_i$$$, Monocarp must choose the day in which he will drink coffee during the said minute, so that every day at least $$$d$$$ minutes pass between any two coffee breaks. Monocarp also wants to take these $$$n$$$ coffee breaks in a minimum possible number of working days (he doesn't count days when he is not at work, and he doesn't take coffee breaks on such days). Take into account that more than $$$d$$$ minutes pass between the end of any working day and the start of the following working day.

For each of the $$$n$$$ given minutes determine the day, during which Monocarp should take a coffee break in this minute. You have to minimize the number of days spent.

A plane is flying at a constant height of $$$h$$$ meters above the ground surface. Let's consider that it is flying from the point $$$(-10^9, h)$$$ to the point $$$(10^9, h)$$$ parallel with $$$Ox$$$ axis.

A glider is inside the plane, ready to start his flight at any moment (for the sake of simplicity let's consider that he may start only when the plane's coordinates are integers). After jumping from the plane, he will fly in the same direction as the plane, parallel to $$$Ox$$$ axis, covering a unit of distance every second. Naturally, he will also descend; thus his second coordinate will decrease by one unit every second.

There are ascending air flows on certain segments, each such segment is characterized by two numbers $$$x_1$$$ and $$$x_2$$$ ($$$x_1 \lt x_2$$$) representing its endpoints. No two segments share any common points. When the glider is inside one of such segments, he doesn't descend, so his second coordinate stays the same each second. The glider still flies along $$$Ox$$$ axis, covering one unit of distance every second.

If the glider jumps out at $$$1$$$, he will stop at $$$10$$$. Otherwise, if he jumps out at $$$2$$$, he will stop at $$$12$$$.

Determine the maximum distance along $$$Ox$$$ axis from the point where the glider's flight starts to the point where his flight ends if the glider can choose any integer coordinate to jump from the plane and start his flight. After touching the ground the glider stops altogether, so he cannot glide through an ascending airflow segment if his second coordinate is $$$0$$$.

Recently Monocarp has created his own mini-laboratory!

The laboratory contains $$$n$$$ bacteria. Monocarp knows that he can merge any two bacteria having equal sizes, and the resulting bacterium will have the size equal to the sum of sizes of merged bacteria. For example, if two bacteria having sizes equal to $$$7$$$ merge, one bacterium with size $$$14$$$ is the result.

It becomes hard to watch for many bacteria, so Monocarp wants to merge all of them into one bacterium. It may not be possible to do this with the bacteria Monocarp has, so he can buy any number of bacteria of any possible integer sizes in a special store.

You have to determine the minimum number of bacteria Monocarp has to buy to merge them with the $$$n$$$ bacteria his laboratory contains into exactly one bacterium.

Quite often the jury of Saratov SU use the problem "Masquerade" in different practice sessions before the contest. This problem is quite easy — all you need is to print the product of two integers which were read from the input stream.

As usual, the jury had prepared this problem once again. The jury had $$$n$$$ testcases, the $$$i$$$-th testcase was a pair of positive integers $$$a_i$$$ and $$$b_i$$$, both integers didn't exceed $$$10^7$$$. All testcases were pairwise distinct.

Unfortunately, something went wrong. Due to hardware issues all testcases have disappeared. All that the jury were able to restore are the number of testcases $$$n$$$ and the answers to these testcases, i. e. a sequence of $$$n$$$ numbers $$$c_1, c_2, \dots, c_n$$$, such that $$$a_i \cdot b_i = c_i$$$.

The jury ask you to help them. Can you provide any possible testset? Remember that all testcases were distinct and all numbers in each testcase were positive integers and didn't exceed $$$10^7$$$.

There is a beautiful fence near Monocarp's house. The fence consists of $$$n$$$ planks numbered from left to right. The $$$i$$$-th plank has color $$$a_i$$$.

Monocarp's father have decided to give his son $$$m$$$ orders. Each order is a color $$$c_j$$$. After each order Monocarp finds leftmost and rightmost planks currently having color $$$c_j$$$ and repaints all planks between them into color $$$c_j$$$.

For example, if, at first, fence looked like (from left to right) $$$[1, 2, 3, 1, 4, 1, 5, 6]$$$, then after fulfilling an order with color $$$1$$$ fence will look like $$$[1, 1, 1, 1, 1, 1, 5, 6]$$$.

Assume that Monocarp fulfills all orders in the order they come, one by one.

Note that if current order is about color $$$x$$$ and there is no more than one plank in the fence having color $$$x$$$, then Monocarp doesn't repaint anything, so he can skip this order and skip to the next one.

Find out the color of each plank after Monocarp has done all the given orders.

Last $$$n$$$ days Monocarp used public transport to get to the university. He received a ticket with number $$$t_i$$$ during the $$$i$$$-th day.

Tickets' numbers are six digit non-negative integers with possible leading zeroes. For example, $$$123456$$$, $$$000000$$$, $$$099999$$$, $$$999999$$$ are correct ticket numbers, but $$$1234567$$$, $$$12345$$$, $$$9$$$ are not. Every day tickets are numbered from zero. The first passenger gets ticket number $$$000000$$$, the second one — ticket number $$$000001$$$, the third one — number $$$000002$$$ and so on every day. Assume that each day the number of passengers doesn't exceed $$$10^6$$$.

Unluckiness of the ticket is equal to absolute difference between the sum of the first three digits and the sum of the last three. For example, unluckiness of the ticket number $$$345123$$$ is equal to $$$|(3 + 4 + 5) - (1 + 2 + 3)| = 6$$$, or unluckiness of the ticket number $$$238526$$$ is equal to $$$|(2 + 3 + 8) - (5 + 2 + 6)| = 0$$$.

One passenger is luckier than other if unluckiness of first passenger's ticket is strictly less than unluckiness of the second one's ticket.

For each of $$$n$$$ days for given Monocarp's ticket's number $$$t_i$$$ calculate the number of passengers who received their tickets before him during this day and are luckier than Monocarp.

Examine examples for the further understanding of the statement.

Monocarp has drawn a tree (an undirected connected acyclic graph) and then has given each vertex an index. All indices are distinct numbers from $$$1$$$ to $$$n$$$. For every edge $$$e$$$ of this tree, Monocarp has written two numbers: the maximum indices of the vertices of the two components formed if the edge $$$e$$$ (and only this edge) is erased from the tree.

Monocarp has given you a list of $$$n - 1$$$ pairs of numbers. He wants you to provide an example of a tree that will produce the said list if this tree exists. If such tree does not exist, say so.

The Theater Square can be represented as a rectangle having height $$$n$$$ and length $$$m$$$, divided into square $$$1 \times 1$$$ cells. Let's denote the cell located at the intersection of $$$i$$$-th row and $$$j$$$-th column as $$$(i, j)$$$. The rows are numbered from top to bottom, the columns — from left to right.

There is a rectangular fountain inside the Teather Square. The cell in its left upper corner is $$$(x_1, y_1)$$$, the cell in its right lower corner is $$$(x_2, y_2)$$$.

The Theater Square soon will be paved with tiles having height $$$1$$$ and length $$$2$$$. Every cell (except cells inside the fountain) should be paved, and no cell should be covered by more than one tile. All tiles will be laid out horizontally, so the cells covered by each tile are in the same row. To pave the whole Theater Square it might be necessary to break some tiles. After breaking a tile, two new tiles of size $$$1 \times 1$$$ are formed (which cannot be broken further). You may consider that the mayor, who ordered the paving of the Theater Square, has infinite number of tiles $$$1 \times 2$$$.

Since broken tiles are not beautiful, among all possible ways to pave the Theater Square the mayor wants to choose a way such that the number of tiles to be broken into two lesser tiles is minimum possible. Pay attention that tiles should be laid horizontally, no tile can cover cells in different rows.

Help the mayor! Tell him the minimum possible number of tiles to be broken.

There was an electronic store heist last night.

All keyboards which were in the store yesterday were numbered in ascending order from some integer number $$$x$$$. For example, if $$$x = 4$$$ and there were $$$3$$$ keyboards in the store, then the devices had indices $$$4$$$, $$$5$$$ and $$$6$$$, and if $$$x = 10$$$ and there were $$$7$$$ of them then the keyboards had indices $$$10$$$, $$$11$$$, $$$12$$$, $$$13$$$, $$$14$$$, $$$15$$$ and $$$16$$$.

After the heist, only $$$n$$$ keyboards remain, and they have indices $$$a_1, a_2, \dots, a_n$$$. Calculate the minimum possible number of keyboards that have been stolen. The staff remember neither $$$x$$$ nor the number of keyboards in the store before the heist.

Monocarp has decided to buy a new TV set and hang it on the wall in his flat. The wall has enough free space so Monocarp can buy a TV set with screen width not greater than $$$a$$$ and screen height not greater than $$$b$$$. Monocarp is also used to TV sets with a certain aspect ratio: formally, if the width of the screen is $$$w$$$, and the height of the screen is $$$h$$$, then the following condition should be met: $$$\frac{w}{h} = \frac{x}{y}$$$.

There are many different TV sets in the shop. Monocarp is sure that for any pair of positive integers $$$w$$$ and $$$h$$$ there is a TV set with screen width $$$w$$$ and height $$$h$$$ in the shop.

Monocarp isn't ready to choose the exact TV set he is going to buy. Firstly he wants to determine the optimal screen resolution. He has decided to try all possible variants of screen size. But he must count the number of pairs of positive integers $$$w$$$ and $$$h$$$, beforehand, such that $$$(w \le a)$$$, $$$(h \le b)$$$ and $$$(\frac{w}{h} = \frac{x}{y})$$$.

In other words, Monocarp wants to determine the number of TV sets having aspect ratio $$$\frac{x}{y}$$$, screen width not exceeding $$$a$$$, and screen height not exceeding $$$b$$$. Two TV sets are considered different if they have different screen width or different screen height.

Let median of some array be the number which would stand in the middle of this array if it was sorted beforehand. If the array has even length let median be smallest of of two middle elements. For example, median of the array $$$[10, 3, 2, 3, 2]$$$ is $$$3$$$ (i.e. $$$[2, 2, \underline{3}, 3, 10]$$$). Median of the array $$$[1, 5, 8, 1]$$$ is $$$1$$$ (i.e. $$$[1, \underline{1}, 5, 8]$$$).

Let array be $$$m$$$-good if its median is greater or equal than $$$m$$$.

Let the partition of array $$$[a_1, a_2, \dots, a_n]$$$ be a set of subarrays $$$\{b_1, b_2, \dots, b_k\}$$$ such that $$$b_1 = [a_1, a_2, \dots, a_{i_1}]$$$, $$$b_2 = [a_{i_1 + 1}, a_{i_1 + 2}, \dots, a_{i_2}]$$$, ..., $$$b_k = [a_{i_{k-1} + 1}, a_{i_{k-1} + 2}, \dots, a_n]$$$. For example, array $$$[10, 3, 2, 3, 2]$$$ can be partitioned as follows: $$$\{[10, 3, 2, 3, 2]\}$$$ or $$$\{[10], [3], [2], [3], [2]\}$$$, or $$$\{[10], [3, 2, 3, 2]\}$$$, or $$$\{[10, 3], [2], [3, 2]\}$$$ and so on.

You are given array $$$a$$$ of length $$$n$$$ and integer $$$m$$$. Find the partition of $$$a$$$ into maximum number of subarrays such that each subarray is $$$m$$$-good.

You are given a tube which is reflective inside represented as two non-coinciding, but parallel to $$$Ox$$$ lines. Each line has some special integer points — positions of sensors on sides of the tube.

You are going to emit a laser ray in the tube. To do so, you have to choose two integer points $$$A$$$ and $$$B$$$ on the first and the second line respectively (coordinates can be negative): the point $$$A$$$ is responsible for the position of the laser, and the point $$$B$$$ — for the direction of the laser ray. The laser ray is a ray starting at $$$A$$$ and directed at $$$B$$$ which will reflect from the sides of the tube (it doesn't matter if there are any sensors at a reflection point or not). A sensor will only register the ray if the ray hits exactly at the position of the sensor.

Examples of laser rays. Note that image contains two examples. The $$$3$$$ sensors (denoted by black bold points on the tube sides) will register the blue ray but only $$$2$$$ will register the red.

Calculate the maximum number of sensors which can register your ray if you choose points $$$A$$$ and $$$B$$$ on the first and the second lines respectively.