King Bajtazar has decided to build a new palace. He has announced a competition for the best architectural design for the palace. To motivate architects to work quickly, he also announced that he would review the projects in the order they are submitted.

This commission carries great prestige, so architects from all over the world are sending their proposals to the royal office. A large number of projects are arriving, and Bajtazar does not have time to review them all. He has therefore given up on doing this himself and asked his chancellor to pre-screen the incoming projects according to the following rules:

• The chancellor must select $k$ projects, discarding the rest immediately — Bajtazar knows he will not be able to review more than $k$ projects anyway.
• The projects must be presented to Bajtazar in the order they were submitted — this is also the order in which Bajtazar will review them, as he announced.
• From all sequences of $k$ projects satisfying the above conditions, the chancellor must choose the best sequence, according to the following definition: We say that a sequence of projects $(p_1, p_2, \dots, p_k)$ is better than a sequence $(r_1, r_2, \dots, r_k)$ if, for some $l \ge 1$, the first $l-1$ projects in both sequences are equally good, and the $l$-th project in sequence $p$ is better than the $l$-th project in sequence $r$ (i.e., $p_i = r_i$ for $i < l$ and $p_l > r_l$).

Projects are arriving all the time, and it is unknown how long Bajtazar will order them to be accepted. The chancellor does not want to leave the choice of $k$ projects until the last moment, but he is very afraid of making a mistake and incurring the king's wrath. Therefore, he has asked you for help.

Interaction

Your program should not read anything from standard input or write anything to standard output. Instead, it will be compiled with an evaluation library. At the beginning of your program, include the directive:

#include "arc.h"

The library provides the following functions:

• int inicjuj() – returns an integer $k$ ($1 \le k \le 1\,000\,000$), specifying how many projects the result sequence should contain. It should be used exactly once, at the very beginning of the program's execution.
• int wczytaj() – the $i$-th call returns an integer $p_i$ ($1 \le p_i \le 1\,000\,000\,000$) representing the quality of the $i$-th project (the larger the number, the better the project), or $0$, which means there are no more projects. The number of projects is not known before reading the data, but you can assume that there are at least $k$ projects in total, and at most $15\,000\,000$. This function should be called until there are no more projects, and not a single time more.
• void wypisz(int jakoscProjektu) – use this function to output the qualities of the successive projects that the chancellor will present to the king. It should be used exactly $k$ times; in the $i$-th call, you must provide the quality of the $i$-th project in the sequence. The $k$-th call to this function will terminate your program.

Examples

Input 1

k = inicjuj(); // returns 3
wczytaj(); // returns 12
wczytaj(); // returns 5
wczytaj(); // returns 8
wczytaj(); // returns 3
wczytaj(); // returns 15
wczytaj(); // returns 8
wczytaj(); // returns 0
wypisz(12);
wypisz(15);
wypisz(8);

Implementation Details

In the "Files" section, you can find a sample library and a solution illustrating how to use them. The sample library reads a test scenario from standard input in the following format: The first line of input contains a single positive integer $k$. Subsequent lines of input contain one positive integer each; the $(i+1)$-th line contains the number $p_i$, representing the quality of the $i$-th submitted project. The last line of input contains the number $0$, representing the end of the project list. The sample library writes $k$ lines to standard output – the project qualities reported by the program.

To test your program, compile it with a command similar to the following (assuming your solution is in the file arc.cpp):

g++ -O2 -std=c++11 arc.cpp arczaw.c -o arc

This will create an executable file named arc.

Subtasks

The test set is divided into the following subtasks. Tests for each subtask consist of one or more separate test groups.

Recall that $n$ denotes the number of projects.

| :---: | :---: | :---: | | Subtask | Conditions | Points | | 1 | $n \le 30$ | 10 | | 2 | $n \le 2\,000\,000$ | 30 | | 3 | $n \le 15\,000\,000$ | 60 |