Universal Cup Judging System

Universal Cup

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

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

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.