| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 16 | 13 | 10 | 90.909% |
У хозяйки Макса Кэти очень много дел. Для удобства она решила пронумеровать все дела целыми неотрицательными числами в порядке убывания их важности (в частности дело с номером 0 самое важное).
Сейчас в распоряжении Кэти находятся $n$ дней, в каждом из которых она выделила $m$ моментов времени (по привычке дни и моменты Кэти также пронумеровала с нуля). Чтобы все успевать и при этом избегать рутины, девушка составила расписание, в котором решила придерживаться следующего правила. В $i$-ый день в момент времени $j$ Кэти выбирает самое важное (минимальное по номеру) дело такое, которое она не делала в этот день ранее (то есть в моменты от 0 до $j-1$) и в прежние дни в $j$-ые моменты времени (в частности в нулевой день в нулевой момент Кэти будет занята делом 0).
Очень скоро Кэти поняла, что дела в таком расписании будут распределены единственным образом, а значит она сможет с легкостью узнавать, что ей необходимо сделать в каждый конкретный момент времени. Помогите ей в этом.
В первой строке входного файла заданo одно натуральное число $k$ --- количество запросов (1ドル \le k \le 10^5$).
В следующих $k$ строках следуют сами запросы, каждый запрос --- пара целых неотрицательных чисел $(i, j),ドル где $i$ --- номер дня и $j$ --- номер момента (0ドル \le i, j \le 10^9$).
Для каждого запроса в отдельной строке выведите одно число --- номер дела, которое необходимо выполнить в заданный момент времени.
6 1 1 2 9 3 2 3 6 5 4 8 8
0 11 1 5 1 0
4 25 36 59 78 87 103 100 243
61 117 48 151