У Маленького 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