Задача №115300. Юрик и важные дела
Юрик — очень занятой человек, поэтому он не успевает выполнять все необходимые дела вовремя. К концу недели у него скопилось \(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\)-м по счету после всех изменений порядка выполнения дел.
Рассмотрим первый пример. Изначально Юрик планировал выполнять дела в следующем порядке: \(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\).
8 6 3 1 5 2 8 7 4 3 6 1 8 2 4 7 8 1 1 1 3 2 7
7