У Маленького L есть правильная треугольная сетка, где каждая линия сетки — это отрезок, соединяющий соответствующие точки деления смежных сторон на $n$ равных частей. Эти линии сетки делят правильный треугольник на несколько равных маленьких правильных треугольников.
Каждую точку пересечения линий сетки на рисунке мы обозначаем координатами $(x, y)$. Координата $x$ сверху вниз меняется от $1$ до $n + 1$. Значение $x = 1$ соответствует самой верхней точке, а $x = n + 1$ — нижней линии. В $i$-й строке координаты $y$ узлов сетки слева направо меняются от $1$ до $i$.
В треугольной сетке можно выделить различные правильные треугольники, которые могут быть ориентированы прямо (вершиной вверх) или перевёрнуто (вершиной вниз). Для любой ориентации треугольник задаётся тремя числами $x, y, d$. Здесь $(x, y)$ — координаты вершины, противоположной его стороне, параллельной нижней линии сетки, а $d$ — длина его стороны (длина отрезка).
Например, на рисунке ниже синий правильный треугольник является прямым треугольником с параметрами $(x, y, d) = (4, 2, 3)$. Жёлтый правильный треугольник является перевёрнутым треугольником с параметрами $(x, y, d) = (6, 3, 2)$.

В каждой единичной маленькой правильной треугольной ячейке сетки (правильном треугольнике со стороной $1$, независимо от ориентации) записано число. Изначально все числа в ячейках равны $0$. Маленький L будет выполнять следующие операции:
- Выбрать правильный треугольник и прибавить $w$ ко всем числам в ячейках внутри него.
- Выбрать правильный треугольник и запросить сумму всех чисел в ячейках внутри него.
Он надеется, что вы сможете вычислить ответ для каждой операции запроса. Поскольку Маленький L не любит большие числа, вам нужно лишь вывести результат ответа по модулю $2^{32}$.
Входные данные
Первая строка входных данных содержит два целых числа $n, q$ ($2 \le n \le 10^5, 1 \le q \le 10^5$).
Следующие $q$ строк описывают операции.
Каждая строка начинается с пяти чисел $opt, type, x, y, d$ ($opt \in \{1, 2\}, type \in \{0, 1\}, 1 \le x \le n + 1, 1 \le y \le x, 1 \le d \le n$). $opt$ обозначает тип операции: $opt = 1$ — операция изменения, а $opt = 2$ — операция запроса. $type$ указывает тип треугольника в этой операции: $type = 0$ соответствует прямому треугольнику, а $type = 1$ — перевёрнутому треугольнику. Числа $x, y, d$ описывают этот треугольник. Если $opt = 1$, то далее следует ещё одно число $w$ ($0 \le w < 2^{32}$), указывающее величину, прибавляемую в ходе этой операции изменения.
Гарантируется, что все входные треугольники имеют ненулевую площадь и являются корректными треугольниками, полностью лежащими внутри большого треугольника.
Выходные данные
Для каждого запроса с $opt = 2$ выведите в новой строке одно число — сумму внутри области по модулю $2^{32}$.
Примеры
Входные данные 1
5 5 1 0 3 3 2 2 1 1 6 4 2 3 2 0 1 1 5 2 0 3 2 3 2 1 5 3 2
Выходные данные 1
20 11 3
Входные данные 2
10 10 1 0 1 1 5 2 1 1 3 2 1 6 1 1 6 4 2 1 2 0 10 3 1 2 1 5 2 1 2 1 6 4 2 1 0 7 7 1 7 1 1 9 3 1 3 1 0 9 5 2 4 2 0 6 1 2
Выходные данные 2
0 2 12 0