Whiteking собирается сыграть в игру по украшению территории. Область, которую он хочет украсить, представляет собой сетку $N \times N$, в которой элементарная ячейка представлена плиткой размером $1 \times 1$. Координаты верхней левой плитки — $(1, 1)$, а координаты нижней правой плитки — $(N, N)$. Таким образом, координаты плитки соответствуют координатам её нижнего правого угла. Из этого следует, что плитка, расположенная в $(x, y)$, занимает квадратную область, соответствующую $[x - 1, x] \times [y - 1, y]$. Каждая плитка имеет своё значение красоты, изначально все плитки имеют значение красоты 0.

Игра по украшению территории — это игра, в которой игрок зарабатывает очки, выполняя следующие три действия:

• Разделение сетки на различные зоны путём проведения прямой линии горизонтально или вертикально. Изначально существует только одна область размером $N \times N$. Линии бесконечны в обоих направлениях: например, если провести одну горизонтальную и одну вертикальную линию, исходная область будет разделена в общей сложности на четыре зоны.
• Выбор плитки и украшение области, к которой она принадлежит. В результате значение красоты всех плиток в украшенной области увеличивается на заданную величину.
• Выбор прямоугольника на сетке и получение очков, равных значению красоты самой красивой плитки в нём.

Whiteking хочет заранее знать, сколько очков он заработает за каждое действие третьего типа. Поэтому он покажет вам упорядоченный список действий, которые собирается выполнить. Действия будут заданы в следующем формате:

• «1 a b»: Если $a = 0$, провести прямую линию $x = b$, а если $a = 1$, провести прямую линию $y = b$.
• «2 a b X»: Выбрать плитку, расположенную в $(a, b)$, и украсить область, к которой она принадлежит, увеличив значение красоты всех плиток в ней на $X$.
• «3 a b c d»: Выбрать прямоугольник с верхней левой плиткой $(a, b)$ и нижней правой плиткой $(c, d)$ и получить очки, равные значению красоты самой красивой плитки в нём.

Помогите Whiteking определить, каким будет счёт для каждого действия третьего типа.

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

Первая строка содержит два целых числа $N$ и $Q$ ($1 \le N \le 10^5$, $1 \le Q \le 3 \cdot 10^5$).

Каждая из следующих $Q$ строк описывает действие в формате, указанном в условии задачи.

Для действия типа 1: $0 \le a \le 1$ и $1 \le b \le N - 1$.

Для действия типа 2: $1 \le a, b \le N$ и $-10^9 \le X \le 10^9$.

Для действия типа 3: $1 \le a \le c \le N$ и $1 \le b \le d \le N$.

Всего существует не более 25 000 действий типа 2 и как минимум 1 действие типа 3.

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

Для каждого действия третьего типа выведите количество очков, которое получит Whiteking за это действие.

Примеры

Пример 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

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

0
-3
-3
1