Mały L ma siatkę w kształcie trójkąta równobocznego, w której każda linia siatki jest odcinkiem łączącym odpowiednie punkty podziału sąsiednich boków na $n$ równych części. Linie te dzielą trójkąt równoboczny na pewną liczbę przystających mniejszych trójkątów równobocznych.
Każdy punkt przecięcia linii siatki na rysunku oznaczamy współrzędnymi $(x, y)$. Współrzędna $x$ od góry do dołu przyjmuje wartości od $1$ do $n + 1$. $x = 1$ oznacza najwyższy punkt, natomiast $x = n + 1$ oznacza dolną linię. W $i$-tym wierszu współrzędne $y$ punktów siatki od lewej do prawej przyjmują wartości od $1$ do $i$.
W trójkątnej siatce znajduje się pewna liczba trójkątów równobocznych, które mogą być skierowane wierzchołkiem w górę (proste) lub w dół (odwrócone). Niezależnie od orientacji, trójkąt opisujemy trzema liczbami $x, y, d$. Tutaj $(x, y)$ oznacza współrzędne wierzchołka przeciwległego do jego boku równoległego do dolnej linii siatki, natomiast $d$ oznacza długość jego boku (długość odcinka).
Na przykład na poniższym rysunku niebieski trójkąt równoboczny jest trójkątem prostym o parametrach $(x, y, d) = (4, 2, 3)$. Żółty trójkąt równoboczny jest trójkątem odwróconym o parametrach $(x, y, d) = (6, 3, 2)$.

Teraz na każdym jednostkowym małym trójkącie równobocznym siatki (trójkącie równobocznym o długości boku $1$, niezależnie od orientacji) zapisana jest liczba. Początkowo wszystkie liczby na polach siatki są równe $0$. Mały L wykona następujące operacje:
- Wybierz trójkąt równoboczny i dodaj $w$ do wszystkich liczb na polach siatki wewnątrz niego.
- Wybierz trójkąt równoboczny i zapytaj o sumę wszystkich liczb na polach siatki wewnątrz niego.
Ma on nadzieję, że obliczysz odpowiedź dla każdej operacji zapytania. Ponieważ Mały L nie lubi dużych liczb, wystarczy wypisać wynik odpowiedzi modulo $2^{32}$.
Wejście
Pierwszy wiersz wejścia zawiera dwie liczby całkowite $n, q$ ($2 \le n \le 10^5, 1 \le q \le 10^5$).
Kolejne $q$ wierszy opisuje poszczególne operacje.
Każdy wiersz zaczyna się od pięciu liczb $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$ oznacza typ operacji, gdzie $opt = 1$ to operacja modyfikacji, a $opt = 2$ to operacja zapytania. $type$ określa typ trójkąta w tej operacji, gdzie $type = 0$ oznacza trójkąt prosty, a $type = 1$ oznacza trójkąt odwrócony. Liczby $x, y, d$ opisują ten trójkąt. Jeśli $opt = 1$, w wierszu znajduje się dodatkowa liczba $w$ ($0 \le w < 2^{32}$), oznaczająca wartość dodawaną podczas tej operacji modyfikacji.
Gwarantowane jest, że wszystkie trójkąty na wejściu mają niezerowe pole i są poprawnymi trójkątami całkowicie zawartymi wewnątrz dużego trójkąta.
Wyjście
Dla każdego zapytania z $opt = 2$ wypisz w nowym wierszu jedną liczbę oznaczającą sumę w danym obszarze modulo $2^{32}$.
Przykład
Wejście 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
Wyjście 1
20 11 3
Wejście 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
Wyjście 2
0 2 12 0