Оля та площина

Дівчинка Оля — яскравий приклад ідеальної людини: вона щодня розв'язує задачі. Проте займатися вдома майже неможливо, адже там живе її кіт-бешкетник Костянтин, який за будь-якої нагоди щось та натворить. Тож коли Олі подарували на день народження величезний шматок білої декартової площини для нотаток, Костянтин відразу замислив зіпсувати чудовий подарунок.

Площина має вигляд білого квадрату, лівий нижній кут якої має координати $(0,0)$, а верхній правий — $(N,N)$. Для зручності дівчинка поставила у кожен кут площини (тобто у точки $(0,0)$, $(N,0)$, $(0,N)$, $(N,N)$) по плящці з чорнилами та сіла писати складний контест.

Поки Оля пише чергову задачу, Костянтин може підійти та «випадково» перекинути будь-яку пляшку з чорнилами, і прямокутна ділянка, протилежні кути якої знаходяться у точці де стоїть пляшка та точці $(x,y)$ на площині, буде безнадійно зіпсована і вся перефарбується в чорний колір. Оля, звісно, трохи покричить, але що робити — доведеться знову наповнити пляшку з чорнилами і продовжувати писати змагання. При цьому Костянтин знову зможе перекинути чорнила, пофарбувавши уже іншу ділянку площини.

Іноді, коли Оля зустрічає особливо складну задачу, вона вирішує занотувати свої думки стосовно неї на деякій частині своєї площини. Для нотування вона завжди обирає ділянку, що являє собою прямокутник, паралельний осям координат. Звісно, Олі необхідна інформація про те, яка площа обраної ділянки вкрита чорнилами. Оскільки дівчинка дуже зайнята розв'язуванням задач на контесті, Вам доведеться допомогти їй.

Завдання

Напишіть програму, яка за інформацією про події, що вібулись під час контесту, буде допомагати Олі знаходити площу зафарбованої частини площини.

Input

У першому рядку вхідного файлу містяться два числа цілих $N$ та $Q$ ($1\le N,Q\le 10^5$), які задають розмір площини та кількість подій, що відбулись під час контесту відповідно.

Далі йдуть $Q$ рядків, що описують події. Кожен рядок починається числом $t$, яке описує тип події. Якщо $1\le t\le 4$, це означає що Костянтин перекинув відповідну пляшку з чорнилами. У такому випадку далі йдуть два числа $x$ та $y$ ($0\le x,y\le N$), які задають протилежний кут ділянки, котра буде перефарбована в чорний колір.

Перша пляшка з чорнилами знаходиться в лівому нижньому, друга — в правому нижньому, третя — в лівому верхньому, а четверта пляшка — в правому верхньому кутах.

Якщо ж $t$ дорівнює $0$,далі йдуть $4$ цілих числа $x_1$, $y_1$, $x_2$, $y_2$ ($0\le x_1<x_2\le N$,$0\le y_1<y_2\le N$) — Оля обирає прямокутну ділянку, паралельну осям координат з протилежними кутами в точках $(x_1,y_1)$ та $(x_2,y_2)$.

Гарантується, що у вхідному файлі міститься хоча б одна подія типу $0$, а кіт фарбує прямокутники з ненульовою площею.

Output

У вихідний файл для кожного запиту типу $0$ виведіть у окремому рядку єдине ціле число - площу зіпсованої котом частини відповідної ділянки площини. Відповіді на запити виведіть у тому ж порядку, в якому вони задані у вхідних даних.

Examples

Note

Нижче зображення частини площини у першому прикладi. Чорний прямокутник це зіпсована котом частина площини, сiрим видiлена дiлянка, яку обрала Оля для нотаток.

Scoring

1. ($5$ балів): $1\le N,Q\le 100$

2. ($6$ балів): $1\le N,Q\le 1000$; $t\in \{0,1,2\}$

3. ($8$ балів): $1\le N,Q\le 1000$

4. ($14$ балів): $1\le N,Q\le 50000$; кiлькiсть запитiв нульового типу не бiльше 20

5. ($12$ балів): $1\le N,Q\le 50000$; $t\in \{0,1\}$; для усіх запитів першого типу виконується умова: якщо запит $a$ йде пізніше запиту $b$, то $x_a\le x_b$; $y_a\ge y_b$;

6. ($8$ балів): $1\le N,Q\le 50000$; $t\in \{0,1\}$

7. ($10$ балів): $1\le N,Q\le 50000$; $t\in \{0,1,2\}$

8. ($13$ балів): $1\le N,Q\le 50000$

9. ($9$ балів): $t\in \{0,1\}$

10. ($8$ балів): $t\in \{0,1,2\}$

11. ($7$ балів): Без додаткових обмежень