Волшебный чемодан
ограничение по времени на тест
1.5 секунд
ограничение по памяти на тест
64 мегабайта
ввод
array.in
вывод
array.out

В чемодане Ньюта Саламандера находится n волшебных животных и столько же отделений для них. Отделения пронумерованы от 1 до n. В каждое отделение помещается ровно одно животное. У каждого существа есть уровень опасности t. Как известно, животные весьма активны. Они не любят находиться в одном месте и поэтому постоянно меняются местами внутри чемодана.

Назовём группу подряд идущих животных, которые находятся в отделениях с l по r, отрезком.

В течение m минут происходило два типа событий:

  1. Два непересекающихся равных по размеру отрезка животных меняются местами. Отрезок с l1 по r1 меняется с отрезком с l2 по r2. Формально, животное в ячейки i меняется местом с животным в ячейке i - l1 + l2, где i от l1 до r1.

  2. Зоолог спрашивает количество животных на отрезке с l по r, у которых сила t не меньше, чем a и не больше, чем b.

Вы узнали, какие события происходили в чемодане, а также начальное положение животных. Найдите ответы на вопросы учёного.

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

В первой строке задано число n и m — количество клеток и количество запросов (1 ≤ n ≤ 106; 1 ≤ m ≤ 2·103).

Во второй строке задана последовательность чисел ti длины n — силы животных (1 ≤ ti ≤ 109).

Далее следует m строк. В каждой записаны числа type — тип запроса (1 ≤ type ≤ 2).

Если type = 1, то далее следуют числа l1, r1, l2, r2 — запрос обмена местами животных. Гарантируется, что отрезки не пересекаются и имеют равную длину (1 ≤ l1 ≤ r1 ≤ n, 1 ≤ l2 ≤ r2 ≤ n).

Если type = 2, то далее следуют числа l, r, a, b — запрос зоолога (1 ≤ l ≤ r ≤ n, 1 ≤ a ≤ b ≤ 109).

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

Для каждого запроса второго типа вывести количество подходящих животных.

Примеры

Входные данные
3 2
1 2 3
1 1 1 3 3
2 2 3 1 2
Выходные данные
2
Входные данные
6 5
1 2 3 4 5 6
1 1 3 4 6
1 2 3 5 6
2 3 6 2 5
1 1 1 5 5
2 2 5 2 6
Выходные данные
2
3