Universal Cup Judging System

Universal Cup

حد الوقت: 4.0 s حد الذاكرة: 1024 MB مجموع النقاط: 100 قابلة للهجوم ✓
الإحصائيات

Little L ha una griglia triangolare regolare, in cui ogni linea della griglia è un segmento che collega i corrispondenti $n$ punti di suddivisione dei lati adiacenti. Queste linee dividono il triangolo equilatero in diversi triangoli equilateri più piccoli e congruenti.

Ogni punto di intersezione delle linee della griglia nella figura è rappresentato da una coordinata $(x, y)$. La coordinata $x$ dall'alto verso il basso varia da $1$ a $n + 1$. $x = 1$ rappresenta il punto più in alto, mentre $x = n + 1$ rappresenta la linea di base. Per la $i$-esima riga, le coordinate $y$ dei punti della griglia da sinistra a destra variano da $1$ a $i$.

Nella griglia triangolare ci sono diversi triangoli equilateri, che possono essere orientati dritti (con la punta verso l'alto) o capovolti (con la punta verso il basso). Per ciascun orientamento del triangolo, lo rappresentiamo con tre numeri $x, y, d$. Qui $(x, y)$ rappresenta le coordinate del vertice opposto al lato parallelo alla linea di base della griglia, e $d$ rappresenta la lunghezza del suo lato (la lunghezza del segmento).

Ad esempio, nella figura sottostante, il triangolo equilatero blu è un triangolo dritto, con $(x, y, d) = (4, 2, 3)$. Il triangolo equilatero giallo è un triangolo capovolto, con $(x, y, d) = (6, 3, 2)$.

Ora, su ciascuna cella triangolare equilatera unitaria (un triangolo equilatero con lato di lunghezza $1$, indipendentemente dall'orientamento) è scritto un numero. Inizialmente, tutti i numeri sulle celle sono $0$. Little L eseguirà le seguenti operazioni:

  • Scegliere un triangolo equilatero e aggiungere $w$ a tutti i numeri sulle celle al suo interno.
  • Scegliere un triangolo equilatero e chiedere la somma di tutti i numeri sulle celle al suo interno.

Spera che tu possa calcolare la risposta per ciascuna operazione di query. Poiché a Little L non piacciono i numeri grandi, devi solo stampare il risultato della risposta modulo $2^{32}$.

Input

La prima riga dell'input contiene due interi $n, q$ ($2 \le n \le 10^5, 1 \le q \le 10^5$).

Le successive $q$ righe rappresentano ciascuna un'operazione.

Ogni riga inizia con cinque numeri $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$ rappresenta il tipo di operazione, dove $opt = 1$ è un'operazione di modifica e $opt = 2$ è un'operazione di query. $type$ indica il tipo di triangolo per questa operazione, dove $type = 0$ indica un triangolo dritto e $type = 1$ indica un triangolo capovolto. $x, y, d$ descrivono questo triangolo. Se $opt = 1$, c'è un numero aggiuntivo $w$ ($0 \le w < 2^{32}$) che indica il valore aggiunto durante questa operazione di modifica.

È garantito che tutti i triangoli in input abbiano area non nulla e siano triangoli validi completamente contenuti all'interno del triangolo più grande.

Output

Per ogni query con $opt = 2$, stampa un singolo numero su una nuova riga, che rappresenta la somma all'interno dell'area modulo $2^{32}$.

Esempi

Input 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

Output 1

20
11
3

Input 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

Output 2

0
2
12
0

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.