It's surprising but sometimes we can use the bitwise OR to add positive integers written in the binary notation. For a set of numbers, if there are no two numbers with 1 at the same position (counting positions from the right), then the sum of those numbers is equal to their bitwise OR. Such sets of numbers are called beautiful.

You are given a set of positive integers a₁, a₂, ..., a_n. You must build a beautiful set of positive integers b₁, b₂, ..., b_n so that the condition b_i ≥ a_i holds true, and the sum b₁ + b₂ + ... + b_n is minimized.

Given the binary notation of the numbers a₁, a₂, ..., a_n, find the binary notation of the minimum possible value of the sum of numbers in the desired beautiful set b₁, b₂, ..., b_n.

Let max L be the maximum length of a binary notation of a_i.

You will get points for a group if you pass all tests in this group and all groups listed in the dependencies. The group 0 denotes the sample test(s) from the statement.

If you keep the first and the last letter of a word unchanged and rearrange other letters arbitrarily, the resulting word should still be readable. Tihs is bcuseae the huamn mnid deos not raed ervey lteter by istlef, but the wrod as a wlohe.

We will explore a similar phenomenon with sequences of sorted numbers after scrambling elements in the middle.

Let's call a sequence of integers correct if the first number is the smallest in the sequence and the last number — largest. For example, sequences $$$[1, 3, 2, 4]$$$ and $$$[1, 2, 1, 2]$$$ are correct, while $$$[1, 3, 2]$$$ and $$$[2, 1, 2]$$$ are not.

There is a sequence of $$$n$$$ numbers $$$a_1, a_2, \ldots, a_n$$$. We want to split it into the minimum number of correct segments. For example, the sequence $$$[2, 3, 1, 1, 5, 1]$$$ can be splitted into three correct segments: $$$[2, 3]$$$, $$$[1, 1, 5]$$$ and $$$[1]$$$.

Determine the minimum possible number of correct segments that the sequence can be split into.

$$$$$$ \begin{array}{|c|c|c|c|} \hline \text{Subtask} & \text{Points} & \text{Constraints} & \text{Dependencies} \\ \hline 1 & 30 & n \le 500 & 0 \\ \hline 2 & 30 & n \le 5\,000 & 0, 1 \\ \hline 3 & 40 & n \le 300\,000 & 0, 1, 2 \\ \hline \end{array}$$$$$$

You will get points for a group if you pass all tests in this group and all groups listed in the dependencies. The group $$$0$$$ denotes the sample test(s) from the statement.

The scientists invented the new UL-2018 processor that is able to quickly process arrays in some special way. A key feature of its architecture is the separation operation of a segment of the array.

Consider an array $$$[a_1, a_2, \ldots, a_n]$$$. The separation operation is characterized by two integers $$$L$$$ and $$$R$$$. Let $$$S(L, R)$$$ denote the operation of the segment $$$[a_L, a_{L+1}, \ldots, a_R]$$$. Executing the $$$S(L, R)$$$ operation reorders the elements in this segment as follows. First, the elements $$$a_{L+1}, a_{L+3}, a_{L+5}, \ldots$$$ are taken, that is elements $$$a_i$$$ that $$$i - L$$$ is odd. Their relative order remains unchanged. Then, the elements $$$a_L, a_{L+2}, a_{L+4}, \ldots$$$ are taken ($$$a_i$$$ that $$$i - L$$$ is even). These retain the relative order too.

For example, consider the array $$$[2, 4, 1, 5, 3, 6, 7, 8]$$$. Applying the operation $$$S(2, 6)$$$ changes the segment $$$[4, 1, 5, 3, 6]$$$ into $$$[1, 3, 4, 5, 6]$$$, so the entire array becomes $$$[2, 1, 3, 4, 5, 6, 7, 8]$$$.

To demonstrate the capabilities of the new processor, the scientists decided to use separation operations to sort an array of distinct numbers. You will be given an array of size $$$n$$$ ($$$1 \le n \le 3\,000$$$) with distinct numbers from $$$1$$$ to $$$n$$$. You must sort it in ascending order using no more than $$$15\,000$$$ separation operations.

For example, the mentioned array $$$[2, 4, 1, 5, 3, 6, 7, 8]$$$ can be sorted in two separation operations. First, apply $$$S(2, 6)$$$ to get $$$[2, 1, 3, 4, 5, 6, 7, 8]$$$, and then the operation $$$S(1, 2)$$$ makes the array sorted increasingly: $$$[1, 2, 3, 4, 5, 6, 7, 8]$$$.

Your task is to write a program that for a given array determines the sequence of at most $$$15\,000$$$ separation operations, after which the specified array will be sorted in ascending order. It isn't necessary to minimize the number of operations performed (just use at most $$$15\,000$$$).

$$$$$$ \begin{array}{|c|c|c|c|} \hline \text{Subtask} & \text{Points} & \text{Constraints} & \text{Dependencies} \\ \hline 1 & 20 & n \le 100; \ \text{there is a solution with } k = 1 & \\ \hline 2 & 30 & n \le 100 & 0, 1 \\ \hline 3 & 30 & n \le 1\,000 & 0-2 \\ \hline 4 & 20 & n \le 3\,000 & 0-3 \\ \hline \end{array}$$$$$$

You will get points for a group if you pass all tests in this group and all groups listed in the dependencies. The group $$$0$$$ denotes the sample test(s) from the statement.

There are n robots participating in the robomarathon, numbered from 1 to n. Robots must cover the same distance, moving along adjacent tracks, each with a width of 1 meter. The i-th robot is in the i-th track and it needs a_i seconds to cover the required distance and get to the finish line.

A signal device is installed at the start point of each robot. To make the competition less predictable, the judges decided to turn some devices off before the contest. The remaining devices are active. There must be at least one active device.

When the chief judge starts the robomarathon, all active devices send a signal. A robot begins to move at the moment when it gets a signal from some active device. The signal propagates at the rate of 1 meter per second. The distance between tracks i and j is |i - j| meters.

Let x_i denote the distance from the i-th track to the nearest track with an active device. The i-th robot will start moving x_i seconds after the start and get to the finish line in a_i seconds, so it will finish in f_i = x_i + a_i seconds after the start of the robomarathon.

Let k_i be the number of robots that finished strictly before the i-th robot. The place of this robot in the robomarathon is k_i + 1. If multiple robots finish at the same time, then all of them have the place k + 1 if k robots have finished before that.

Consider the following example. Let n = 3, a₁ = 2, a₂ = 3 and a₃ = 5. If the only active signal device is in the third track, the first robot starts moving 2 seconds after the start and finishes at f₁ = 2 + 2 = 4. The second robot starts moving 1 seconds after the start, f₂ = 1 + 3 = 4. The third robot starts moving immediately at the start, f₃ = 0 + 5 = 5. Robots 1 and 2 share the first place, while robot 3 takes the third place. If all three devices work correctly, robots finish with times f₁ = 2, f₂ = 3, f₃ = 5. Robot 1 has the first place, robot 2 the second place, and robot 3 the third place.

As you can see from the example, the leaderboard depends on which devices are active. You will be asked to answer one of two possible questions:

1. For each robot, determine the minimum place it can get.
2. For each robot, determine the maximum place it can get.

Your task is to write a program that, given the times a_i and the type of the request, determines the corresponding best/worst place each robot can take.

The subtask 3 includes 30 tests, each independently scored 1 point if correct. You get 0 points for them anyway if you don't get the full score in subtask 1.

The subtask 4 includes 50 tests, each independently scored 1 point if correct. You get 0 points for them anyway if you don't get the full score in subtask 2.

The values of n for all tests in subtask 3 are shown in the following table.

The values of n for all tests in subtask 4 are shown in the following table.