Description

给定一个序列{ai | 1 <= ai <= 1000000000 且 1 <= i <= n 且 n <= 15000000}和一个整数 k (k <= n 且 k <= 1000000)，求出a的一个长度为k的子序列{a[bi]}满足： (1) 1 <= b1 <= b2 <= ... <= bk (2) 在满足(1)的情况下 {a[b1], a[b2], ... , a[bk]} 字典序最大。

Input

第一行一个数k，以下一行，为序列ai。以一个单独的0结束

Output

k行，每行一个数，其中第i行为a[bi]。

Samples

12
5 8 3 15 8 0

12
15
8

Limitation

按照这里：http://main.edu.pl/en/archive/oi/16/arc

来写交互式的程序，然后把这个东西：http://oi.edu.pl/static/attachment/20110704/oi16-etap2-arc.zip

解压后把etap2/arc/prog里的carclib.c的内容贴到自己的源码中的一大堆“include”之前。这样这个程序就从交互式程序变成普通的程序了，就可以AC了。

鸣谢vfleaking