Во время тренировочных сборов перед BJOI, EI услышал о задачах на блоки (декомпозицию) множеств. Он был очень слаб (и остается таким до сих пор), его алгоритмы всегда были на один $\log$ медленнее, чем у других. Единственным решением, которое он придумал, было изменение размера блока, чтобы уложить сложность в $\Theta(n \sqrt{n\log n})$, но когда он увидел модифицированную задачу, он снова не смог её решить:

Имеется $n$ множеств $S_i$, изначально пустых. Далее выполняется $q$ операций:

1. Вставить элемент $x$ в множества с $l$-го по $r$-е, то есть для всех $l \le i \le r$, $S_i \leftarrow S_i \cup \{x\}$.
2. Запросить размер пересечения множеств с $l$-го по $r$-е, то есть $$\left| \bigcap_{i = l}^r S_i \right|$$

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

В первой строке вводятся целые числа $n, q$.

Далее следуют $q$ строк, в каждой из которых первое число $op$ определяет тип операции.

Соответствующий формат ввода: 1 $l\ r\ x$ или 2 $l\ r$.

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

Для каждой операции типа 2 (запрос) выведите одно целое число на новой строке, представляющее ответ.

Примеры

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

3 4
1 1 2 2
1 2 3 1
2 1 2
2 2 2

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

1
2

Примечание

Состояние множеств после операций: $[\{2\},\{1,2\},\{1\}]$

Таким образом, для первого запроса $\{2\} \cap \{1, 2\} = \{2\}$.

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

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

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

1

Ограничения

$1\le n, q \le 3 \times 10^5$, $1\le x \le q$, $1 \le l \le r \le n$

Подзадача 1 (12 баллов), $1\le n, q \le 500$, количество вставленных элементов $|S| \le 10^5$

Подзадача 2 (18 баллов), $1 \le n, q \le 5 \times 10^3$, количество вставленных элементов $|S| \le 10^5$

Подзадача 3 (20 баллов), $1\le n, q \le 10^5$, количество вставленных элементов $|S| \le 10^5$

Подзадача 4 (28 баллов), $1\le n, q \le 10^5$

Подзадача 5 (22 балла), $1 \le n, q \le 3 \times 10^5$

Подзадача $+\infty$ (0 баллов), вам необходимо вычислить сумму ответов для каждого подотрезка данного отрезка.