Whiteking zamierza zagrać w lokalną grę dekoratorską. Obszar, który chce udekorować, ma formę siatki $N \times N$, w której pojedyncze pole reprezentowane jest przez kafelki $1 \times 1$. Współrzędne lewego górnego kafelka to $(1, 1)$, a prawego dolnego to $(N, N)$. Zatem współrzędne kafelka odnoszą się do współrzędnych jego prawego dolnego rogu. Wynika z tego, że kafelek znajdujący się w $(x, y)$ zajmuje obszar kwadratowy odpowiadający $[x - 1, x] \times [y - 1, y]$. Każdy kafelek ma swoją wartość piękna; początkowo wszystkie kafelki mają wartość piękna równą 0.

Gra dekoratorska polega na zdobywaniu punktów poprzez wykonywanie następujących trzech akcji:

• Podział siatki na różne strefy poprzez rysowanie linii prostych w poziomie lub w pionie. Początkowo istnieje tylko jeden obszar o rozmiarze $N \times N$. Linie są nieskończone w obu kierunkach: na przykład, jeśli narysujesz linię prostą poziomo i drugą pionowo, początkowy obszar zostanie podzielony na łącznie cztery obszary.
• Wybór kafelka i udekorowanie obszaru, do którego on należy. W rezultacie piękno wszystkich kafelków w udekorowanym obszarze zwiększa się o podaną wartość.
• Wybór prostokąta na siatce i zdobycie punktów równych pięknu najpiękniejszego kafelka w jego obrębie.

Whiteking chce z wyprzedzeniem wiedzieć, ile punktów zdobędzie za każdą akcję trzeciego typu. W tym celu przedstawi Ci uporządkowaną listę akcji, które zamierza wykonać. Akcje będą podane w następującym formacie:

• „1 a b”: Jeśli $a$ wynosi 0, narysuj linię prostą $x = b$, a jeśli $a$ wynosi 1, narysuj linię $y = b$.
• „2 a b X”: Wybierz kafelek znajdujący się w $(a, b)$, udekoruj obszar, do którego on należy, zwiększając piękno wszystkich kafelków w nim o $X$.
• „3 a b c d”: Wybierz prostokąt z lewym górnym kafelkiem w $(a, b)$ oraz prawym dolnym kafelkiem w $(c, d)$ i zdobądź punkty równe pięknu najpiękniejszego kafelka w nim.

Pomóż Whitekingowi ustalić, jaki będzie wynik dla każdej akcji trzeciego typu.

Wejście

Pierwsza linia zawiera dwie liczby całkowite $N$ oraz $Q$ ($1 \le N \le 10^5$, $1 \le Q \le 3 \cdot 10^5$).

Każda z kolejnych $Q$ linii opisuje akcję w formacie przedstawionym w treści zadania.

Dla akcji typu 1: $0 \le a \le 1$ oraz $1 \le b \le N - 1$.

Dla akcji typu 2: $1 \le a, b \le N$ oraz $-10^9 \le X \le 10^9$.

Dla akcji typu 3: $1 \le a \le c \le N$ oraz $1 \le b \le d \le N$.

Występuje co najwyżej 25 000 akcji typu 2 oraz co najmniej 1 akcja typu 3.

Wyjście

Dla każdej akcji trzeciego typu wypisz wynik, jaki Whiteking otrzyma za tę akcję.

Przykład

Wejście 1

3 7
3 1 1 3 3
2 1 3 -3
3 1 1 3 3
1 0 1
2 1 1 4
3 2 2 3 3
3 1 1 3 3

Wyjście 1

0
-3
-3
1