Новый сериал про жизнь программистов содержит \(n\) серий, пронумерованных от \(1\) до \(n\). Телекомпания Сириус ТВ планирует показывать серии по очереди от первой до последней в течение \(k\) дней, каждый день показывая блок из одной или нескольких подряд идущих серий. Каждая серия будет показана ровно один раз.

По результатам тестовых просмотров маркетологи компании составили рейтинг серий: \(i\)-й серии сопоставлено число \(a_i\) от \(1\) до \(n\), самая интересная серия получила рейтинг \(1\), а самая скучная — рейтинг \(n\). Рейтинги различных серий различны, поэтому числа \([a_1, a_2, \ldots, a_n]\) образуют перестановку.

Пусть принято решение о том, в какой день какие серии будут показаны. Для каждого дня определим рейтинг этого дня, равный рейтингу самой скучной серии этого дня. Иначе говоря, пусть в \(j\)-й день показываются серии с \(l_j\) по \(r_j\), тогда рейтинг этого дня \(b_j\) равен максимальному значению среди \([a_{l_j}, a_{l_j+1}, \ldots, a_{r_j}]\).

Чтобы показ сериала был удачным, необходимо вовлечь зрителей в просмотр. Среди всех возможных способов разбить серии на \(k\) блоков по дням необходимо выбрать тот, в котором рейтинг первого дня как можно лучше: \(b_1\) минимально. Среди этих способов в свою очередь необходимо минимизировать рейтинг второго дня \(b_2\), при выбранных значениях \(b_1\) и \(b_2\) — минимизировать \(b_3\), и так далее. Таким образом, необходимо разбить показ серий на \(k\) блоков таким образом, чтобы лексикографически минимизировать последовательность \([b_1, b_2, \ldots, b_k]\).

Вам необходимо ответить на \(q\) запросов, каждый из которых задаётся двумя числами: \(k\) и \(i\). В качестве ответа на запрос необходимо вывести значение \(b_i\) — рейтинг \(i\)-го дня для оптимального способа показать сериал за \(k\) дней.