EI podczas obozu przed BJOI usłyszał o zadaniach z blokową strukturą zbiorów. Jest on bardzo słaby (i nadal pozostaje słaby), a jego algorytmy są wolniejsze od innych o jeden czynnik $\log$. Jedynym rozwiązaniem, jakie wymyślił, była zmiana rozmiaru bloku, aby zamknąć złożoność w $\Theta(n \sqrt{n\log n})$. Jednak gdy zobaczył zmodyfikowaną wersję zadania, nie wiedział już, jak je rozwiązać:

Mamy $n$ zbiorów $S_i$, początkowo pustych. Następnie wykonujemy $q$ operacji:

1. Wstaw element $x$ do zbiorów od $l$ do $r$, czyli dla $l \le i \le r$, $S_i \leftarrow S_i \cup \{x\}$.
2. Zapytaj o rozmiar części wspólnej zbiorów od $l$ do $r$, czyli $$\left| \bigcap_{i = l}^r S_i \right|$$

Wejście

W pierwszej linii podano liczby całkowite $n, q$.

Następnie podano $q$ linii, z których każda zaczyna się od liczby $op$ określającej typ operacji.

Odpowiednie formaty wejścia to: 1 $l\ r\ x$ lub 2 $l\ r$.

Wyjście

Dla każdej operacji typu 2 (zapytanie) wypisz jedną liczbę całkowitą w nowej linii, oznaczającą wynik.

Przykład 1

Wejście 1

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

Wyjście 1

1
2

Uwagi

Zbiory po operacjach: $[\{2\},\{1,2\},\{1\}]$

Dla pierwszego zapytania: $\{2\} \cap \{1, 2\} = \{2\}$

Przykład 2

Wejście 2

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

Wyjście 2

1

Ograniczenia

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

Podzadanie 1 (12 pkt.): $1\le n, q \le 500$, liczba wstawionych elementów $|S| \le 10^5$

Podzadanie 2 (18 pkt.): $1 \le n, q \le 5 \times 10^3$, liczba wstawionych elementów $|S| \le 10^5$

Podzadanie 3 (20 pkt.): $1\le n, q \le 10^5$, liczba wstawionych elementów $|S| \le 10^5$

Podzadanie 4 (28 pkt.): $1\le n, q \le 10^5$

Podzadanie 5 (22 pkt.): $1 \le n, q \le 3 \times 10^5$

Podzadanie $+\infty$ (0 pkt.): musisz obliczyć sumę odpowiedzi dla każdego podprzedziału danego przedziału.