В чемодане Ньюта Саламандера находится n волшебных животных и столько же отделений для них. Отделения пронумерованы от 1 до n. В каждое отделение помещается ровно одно животное. У каждого существа есть уровень опасности t. Как известно, животные весьма активны. Они не любят находиться в одном месте и поэтому постоянно меняются местами внутри чемодана.
Назовём группу подряд идущих животных, которые находятся в отделениях с l по r, отрезком.
В течение m минут происходило два типа событий:
Вы узнали, какие события происходили в чемодане, а также начальное положение животных. Найдите ответы на вопросы учёного.
В первой строке задано число 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