Серега любит веселье. Только веселятся все по-разному. Серега веселится, решая задачи на запросы. Как-то Федя придумал такую задачу.
Задан массив a, состоящий n целых положительных чисел, и запросы к нему. Запросы бывают двух типов:
- Cделать единичный циклический сдвиг вправо на отрезке от l до r (обе границы включительно). Другими словами, переставить элементы массива следующим образом:a[l], a[l + 1], ..., a[r - 1], a[r] → a[r], a[l], a[l + 1], ..., a[r - 1].
- Посчитать количество чисел, равных k, на отрезке от l до r (обе границы включительно).
Федя побежал обрадовать Серегу новой задачей. Серега очень быстро справился с ней. Посмотрим, как справитесь вы?
Выходные данные
Для каждого запроса 2-го типа выведите ответ в отдельной строке.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|
|
2
|
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
|