시간 제한메모리 제한제출정답맞힌 사람정답 비율
1.5 초 1024 MB133325.000%

문제

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

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

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

  1. Два непересекающихся равных по размеру отрезка животных меняются местами. Отрезок с $l_1$ по $r_1$ меняется с отрезком с $l_2$ по $r_2$. Формально, животное в ячейки $i$ меняется местом с животным в ячейке $i - l_1 + l_2$, где $i$ от $l_1$ до $r_1$.
  2. Зоолог спрашивает количество животных на отрезке с $l$ по $r$, у которых сила $t$ не меньше, чем $a$ и не больше, чем $b$.

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

입력

В первой строке задано число $n$ и $m$ --- количество клеток и количество запросов ($1 \le n \le 10^6$; $1 \le m \le 2 \cdot 10^3$).

Во второй строке задана последовательность чисел $t_i$ длины $n$ --- силы животных ($1 \le t_i \le 10^9$).

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

Если $type = 1$, то далее следуют числа $l_1$, $r_1$, $l_2$, $r_2$ --- запрос обмена местами животных. Гарантируется, что отрезки не пересекаются и имеют равную длину ($1 \le l_1 \le r_1 \le n$, $1 \le l_2 \le r_2 \le n$).

Если $type = 2$, то далее следуют числа $l$, $r$, $a$, $b$ --- запрос зоолога ($1 \le l \le r \le n$, $1 \le a \le b \le 10^9$).

출력

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

예제 입력 1

3 2
1 2 3
1 1 1 3 3
2 2 3 1 2

예제 출력 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

2
3