Universal Cup Judging System

Universal Cup

시간 제한: 4.0 s 메모리 제한: 1024 MB 총점: 100 해킹 가능 ✓
통계

Little L hat ein regelmäßiges Dreiecksgitter, in dem jede Gitterlinie eine Strecke ist, die die entsprechenden $n$ Teilungspunkte benachbarter Seiten verbindet. Diese Gitterlinien unterteilen das gleichseitige Dreieck in mehrere kongruente kleinere gleichseitige Dreiecke.

Jeden Schnittpunkt der Gitterlinien in der Abbildung stellen wir durch eine Koordinate $(x, y)$ dar. Die $x$-Koordinate verläuft von oben nach unten von $1$ bis $n + 1$. Dabei steht $x = 1$ für den obersten Punkt, während $x = n + 1$ die unterste Linie bezeichnet. In der $i$-ten Zeile reichen die $y$-Koordinaten der Gitterpunkte von links nach rechts von $1$ bis $i$.

Im Dreiecksgitter gibt es mehrere gleichseitige Dreiecke, die aufrecht oder umgekehrt (auf dem Kopf stehend) orientiert sein können. Für jede Orientierung des Dreiecks beschreiben wir es durch drei Zahlen $x, y, d$. Hierbei bezeichnet $(x, y)$ die Koordinaten der Ecke, die der zur Grundlinie des Gitters parallelen Seite gegenüberliegt, und $d$ bezeichnet seine Seitenlänge (die Länge der Strecke).

In der Abbildung unten ist beispielsweise das blaue gleichseitige Dreieck ein aufrechtes Dreieck mit $(x, y, d) = (4, 2, 3)$. Das gelbe gleichseitige Dreieck ist ein umgekehrtes Dreieck mit $(x, y, d) = (6, 3, 2)$.

Nun steht in jedem kleinen Einheits-Dreiecksfeld (einem gleichseitigen Dreieck der Seitenlänge $1$, unabhängig von seiner Orientierung) eine Zahl. Zu Beginn sind alle Zahlen in den Feldern gleich $0$. Little L führt die folgenden Operationen aus:

  • Wähle ein gleichseitiges Dreieck und addiere $w$ zu allen Zahlen in den darin liegenden Feldern.
  • Wähle ein gleichseitiges Dreieck und frage die Summe aller Zahlen in den darin liegenden Feldern ab.

Er hofft, dass du die Antwort für jede Abfrageoperation berechnen kannst. Da Little L keine großen Zahlen mag, musst du das Ergebnis der Antwort nur modulo $2^{32}$ ausgeben.

Eingabe

Die erste Zeile der Eingabe enthält zwei ganze Zahlen $n, q$ ($2 \le n \le 10^5, 1 \le q \le 10^5$).

Die nächsten $q$ Zeilen stellen jeweils eine Operation dar.

Jede Zeile beginnt mit fünf Zahlen $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$ gibt die Art der Operation an, wobei $opt = 1$ eine Änderungsoperation und $opt = 2$ eine Abfrageoperation ist. $type$ gibt den Typ des Dreiecks für diese Operation an, wobei $type = 0$ für ein aufrechtes Dreieck und $type = 1$ für ein umgekehrtes Dreieck steht. $x, y, d$ beschreiben dieses Dreieck. Falls $opt = 1$ gilt, folgt eine zusätzliche Zahl $w$ ($0 \le w < 2^{32}$), die den bei dieser Änderungsoperation addierten Wert angibt.

Es wird garantiert, dass alle eingegebenen Dreiecke einen Flächeninhalt ungleich null haben und gültige Dreiecke sind, die vollständig im großen Dreieck enthalten sind.

Ausgabe

Gib für jede Abfrage mit $opt = 2$ eine einzelne Zahl in einer neuen Zeile aus, die die Summe innerhalb des Bereichs modulo $2^{32}$ darstellt.

Beispiele

Eingabe 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

Ausgabe 1

20
11
3

Eingabe 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

Ausgabe 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.