Юрик — очень занятой человек, поэтому он не успевает выполнять все необходимые дела вовремя. К концу недели у него скопилось $$$n$$$ невыполненных дел. Для удобства пронумеруем их целыми числами от $$$1$$$ до $$$n$$$. Сначала Юрик решил, что на выходных будет выполнять дела в порядке их нумерации. Однако, он быстро понял, что некоторые дела важнее других, поэтому решил изменить порядок их выполнения.
У Юрика есть любимая перестановка $$$p_1, p_2, \ldots, p_n$$$, и он решил воспользоваться ей, чтобы изменить порядок выполнения дел. Помимо того, что Юрик очень занятой человек, он также очень непостоянный, поэтому он решил изменить порядок выполнения дел $$$q$$$ раз.
Изначально Юрик записал на лист бумаги дела в том порядке, в котором он их будет выполнять: $$$1, 2, 3, \ldots, n$$$. После этого он $$$q$$$ раз выберет некоторые два числа $$$l$$$ и $$$r$$$ ($$$1 \le l \le r \le n$$$), после чего изменит порядок дел, которые на данный момент находятся в списке на позициях с номерами от $$$l$$$ до $$$r$$$.
Изменение порядка выполнения дел происходит следующим образом. Сначала Юрик назначает делам, которые находятся в списке на позициях с номерами от $$$l$$$ до $$$r$$$ приоритеты. Делу на позиции $$$l$$$ будет назначен приоритет $$$p_1$$$, делу на позиции $$$l + 1$$$ — приоритет $$$p_2$$$, и так далее. Таким образом, делу на позиции $$$r$$$ будет назначен приоритет $$$p_{r - l + 1}$$$. После этого Юрик переупорядочит данные дела в порядке возрастания их приоритетов. Для лучшего понимания процесса обратите внимание на пояснение к примерам.
После того, как Юрик изменил порядок выполнения дел целых $$$q$$$ раз, он окончательно запутался, и теперь хочет понять, какое дело он выполнит $$$k$$$-м по очереди. Помогите ему это выяснить.
Напомним, что перестановкой $$$p_1, p_2, \ldots, p_n$$$ называется массив попарно различных чисел от $$$1$$$ до $$$n$$$.
Первая строка содержит три целых числа $$$n$$$, $$$q$$$ и $$$k$$$ ($$$1 \le n \le 100\,000$$$; $$$1 \le q \le 100\,000$$$; $$$1 \le k \le n$$$).
Вторая строка содержит $$$n$$$ целых чисел $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$) — любимую перестановку Юрика.
Каждая из следующих $$$q$$$ строк содержит два целых числа $$$l_i$$$ и $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$) — начало и конец отрезка дел, порядок которых Юрик изменит в $$$i$$$-й раз.
Выведите одно целое число $$$t$$$ ($$$1 \le t \le n$$$) — номер дела, которое Юрик выполнит $$$k$$$-м по счету после всех изменений порядка выполнения дел.
8 6 31 5 2 8 7 4 3 61 82 47 81 11 32 7
7
Рассмотрим первый пример. Изначально Юрик планировал выполнять дела в следующем порядке: $$$1, 2, 3, 4, 5, 6, 7, 8$$$. Однако, он решил изменить порядок выполнения дел $$$6$$$ раз.
В первый раз Юрик выбрал дела, находящиеся в списке на позициях от $$$1$$$ до $$$8$$$ (то есть все имеющиеся у него дела). Первому делу будет назначен приоритет $$$1$$$, второму делу — приоритет $$$5$$$, третьему делу — приоритет $$$2$$$, и так далее. После этого Юрик упорядочит дела в порядке возрастания приоритетов, поэтому получится последовательность: $$$1, 3, 7, 6, 2, 8, 5, 4$$$.
Во второй раз Юрик выбрал дела, находящиеся в списке на позициях от $$$2$$$ до $$$4$$$: $$$3, 7$$$ и $$$6$$$. Делу с номером $$$3$$$ был назначен приоритет $$$1$$$, делу с номером $$$7$$$ — приоритет $$$5$$$, а делу с номером $$$6$$$ — приоритет $$$2$$$. После того, как Юрик упорядочит дела в порядке возрастания приоритетов, получится последовательность $$$1, 3, 6, 7, 2, 8, 5, 4$$$.
В третий раз Юрик выбрал последние два дела в текущем порядке: $$$5$$$ и $$$4$$$. Первому из них был назначен приоритет $$$1$$$, а второму — приоритет $$$5$$$, поэтому порядок их выполнения не изменился.
В четвертый раз было выбрано одно первое дело.
В пятый раз были выбраны первые три дела в текущем порядке, и после назначения приоритетов дела $$$3$$$ и $$$6$$$ поменялись местами.
Наконец, в шестой раз были выбраны все дела, кроме первого и последнего. Итоговый порядок выполнения дел выглядит следующим образом: $$$1, 6, 7, 5, 3, 8, 2, 4$$$.
