この問題はインタラクティブな問題です。
問題
重複を許す集合$ \ S \ $があります。$S \ $は初め空です。
$N \ $回にわたって整数$ \ x,k \ $が与えられます。各$ \ x,k \ $について、次の処理を行ってください。
- $S \ $に$ \ x \ $を追加する
- $S \ $の要素を昇順に並べたときの$ \ k \ $番目の値を出力する
入出力
最初に整数$ \ N \ $が与えられます。その後、整数$ \ x,k \ $が$ \ N \ $回にわたって与えられますが、$1 \ $回目以外は前回の入力に対する答えを出力した後与えられます。
また、出力後は必ず標準出力を flush してください。
制約
全ての入出力ケースについて以下を満たす。
- $1 \leq N \leq 10^5$
- $1 \leq x \leq 10^9$
- $1 \leq k \leq N$
- $k \ $は$ \ S \ $の要素の数以下である
- 入力は全て整数
入出力例
| input | output | 解説 |
|---|---|---|
| 5 | ||
| 1 1 | ||
| 1 | $S = \{1\} \ $となります | |
| 3 2 | ||
| 3 | $S = \{1,3\} \ $となります | |
| 5 1 | ||
| 1 | $S = \{1,3,5\} \ $となります | |
| 3 3 | ||
| 3 | $S = \{1,3,3,5\} \ $となります | |
| 4 1 | ||
| 1 | $S = \{1,3,3,4,5\} \ $となります |