Sergei collects multi-stage rockets. For greater accuracy in measuring flight parameters at each stage of the rocket, he wrote down its power.
But he completely forgot that the power of the stages of any rocket must be strictly increased. For example, the power of rocket stages can take on the values 1 4 7, and 3 2 4 — can't.
Seryozha does not want to assemble a new rocket, but he can pull out some stages without changing the order of the remaining ones. For example, from a rocket with stage powers 1 8 3 4 you can get a rocket 1 3 4 (by pulling out a stage with a power of 8), and rockets 1 4 3 (the order of stages with powers 4 and 3 has been changed) and 1 8 3 (stage powers are not increase) cannot be obtained.
Help Sergey pull out the minimum number of stages so that the power of the remaining stages
strictly increases.
Sergei has four missiles. In the table below, for each rocket, the power sequence of its stages is given.
| Rocket number |
Power Sequence |
| 1 |
5 3 4 2 3 |
| 2 |
1 6 3 2 5 8 |
| 3 |
4 6 7 5 6 7 1 2 8 |
| 4 |
2 5 3 5 3 4 7 3 8 4 9 6 7 |
The answer to this problem is four sequences of integers: each of them — this is the power sequence of the remaining stages of the corresponding rocket. Write each sequence on the corresponding line. The numbers in the sequence must be separated by a space. Each sequence must be
strictly increasing and
as long as possible. If there are multiple answers, you can display any of them.
If you can't answer for one of the rockets, write the number 0 as the answer for that rocket.
Note
Consider an example. Let's say for some rocket the sequence of steps is 1 4 5 2 3.
There are two possible answers for this rocket. The sequence of numbers in the answer could be: 1 2 3. Or the sequence of numbers could be: 1 4 5.
In the answer, you must specify one, any of these sequences.