D. Серега и веселье
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Серега любит веселье. Только веселятся все по-разному. Серега веселится, решая задачи на запросы. Как-то Федя придумал такую задачу.

Задан массив a, состоящий n целых положительных чисел, и запросы к нему. Запросы бывают двух типов:

  1. Cделать единичный циклический сдвиг вправо на отрезке от l до r (обе границы включительно). Другими словами, переставить элементы массива следующим образом:
    a[l], a[l + 1], ..., a[r - 1], a[r] → a[r], a[l], a[l + 1], ..., a[r - 1].
  2. Посчитать количество чисел, равных k, на отрезке от l до r (обе границы включительно).

Федя побежал обрадовать Серегу новой задачей. Серега очень быстро справился с ней. Посмотрим, как справитесь вы?

Входные данные

В первой строке записано целое число 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.

Чтобы из закодированных входных данных получить данные для запроса, нужно выполнить преобразования:

li = ((l'i + lastans - 1) mod n) + 1; ri = ((r'i + lastans - 1) mod n) + 1; ki = ((k'i + lastans - 1) mod n) + 1.

Здесь 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