Серега любит веселье. Только веселятся все по-разному. Серега веселится, решая задачи на запросы. Как-то Федя придумал такую задачу.
Задан массив a, состоящий n целых положительных чисел, и запросы к нему. Запросы бывают двух типов:
Федя побежал обрадовать Серегу новой задачей. Серега очень быстро справился с ней. Посмотрим, как справитесь вы?
В первой строке записано целое число n (1 ≤ n ≤ 105) — количество элементов массива. Во второй строке записаны n целых чисел a[1], a[2], ..., a[n] (1 ≤ a[i] ≤ n) — элементы массива.
В третьей строке записано целое число q (1 ≤ q ≤ 105) — количество запросов. В следующих q строках заданы запросы.
Так как отвечать на запросы вы должны по мере их поступления, запросы будут закодированы. Запросы первого типа во входных данных заданы в формате: 1 l'i r'i. Запросы второго типа во входных данных заданы в формате: 2 l'i r'i k'i. Все заданные числа целые и удовлетворяют ограничениям: 1 ≤ l'i, r'i, k'i ≤ n.
Чтобы из закодированных входных данных получить данные для запроса, нужно выполнить преобразования:
Здесь lastans обозначает последний ответ на запрос 2-го типа (изначально lastans равно 0). Если значение li получилось больше ri, то их нужно обменять местами.
Для каждого запроса 2-го типа выведите ответ в отдельной строке.
7 6 6 2 7 4 2 5 7 1 3 6 2 2 4 2 2 2 4 7 2 2 2 5 1 2 6 1 1 4 2 1 7 3
2 1 0 0
8 8 4 2 2 7 7 8 8 8 1 8 8 2 8 1 7 1 8 1 1 7 3 2 8 8 3 1 1 4 1 2 7 1 4 5
2 0
4000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач