Universal Cup Judging System

Universal Cup

Time Limit: 4.0 s Memory Limit: 1024 MB Total points: 100 Hackable ✓
Statistics

Little L tiene una cuadrícula triangular regular, donde cada línea de la cuadrícula es un segmento que conecta los correspondientes $n$ puntos de división de los lados adyacentes. Estas líneas dividen el triángulo equilátero en varios triángulos equiláteros más pequeños y congruentes.

Cada punto de intersección de las líneas de la cuadrícula en la figura se representa mediante una coordenada $(x, y)$. La coordenada $x$ de arriba hacia abajo varía de $1$ a $n + 1$. $x = 1$ representa el punto más alto, mientras que $x = n + 1$ representa la línea inferior. Para la $i$-ésima fila, las coordenadas $y$ de los puntos de la cuadrícula de izquierda a derecha varían de $1$ a $i$.

En la cuadrícula triangular hay varios triángulos equiláteros, que pueden estar orientados hacia arriba (normales) o hacia abajo (invertidos). Para cada orientación del triángulo, lo representamos con tres números $x, y, d$. Aquí, $(x, y)$ representa las coordenadas del vértice opuesto a su lado paralelo a la línea inferior de la cuadrícula, y $d$ representa la longitud de su lado (la longitud del segmento).

Por ejemplo, en la siguiente figura, el triángulo equilátero azul es un triángulo orientado hacia arriba, con $(x, y, d) = (4, 2, 3)$. El triángulo equilátero amarillo es un triángulo invertido, con $(x, y, d) = (6, 3, 2)$.

Ahora, en cada celda triangular equilátera unitaria pequeña (un triángulo equilátero de lado $1$, sin importar su orientación), hay un número escrito. Inicialmente, todos los números en las celdas son $0$. Little L realizará las siguientes operaciones:

  • Elegir un triángulo equilátero y sumar $w$ a todos los números de las celdas dentro de él.
  • Elegir un triángulo equilátero y consultar la suma de todos los números de las celdas dentro de él.

Él espera que puedas calcular la respuesta para cada operación de consulta. Como a Little L no le gustan los números grandes, solo necesitas imprimir el resultado de la respuesta módulo $2^{32}$.

Entrada

La primera línea de la entrada contiene dos enteros $n, q$ ($2 \le n \le 10^5, 1 \le q \le 10^5$).

Las siguientes $q$ líneas representan cada una una operación.

Cada línea comienza con cinco números $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$ representa el tipo de operación, donde $opt = 1$ es una operación de modificación y $opt = 2$ es una operación de consulta. $type$ indica el tipo de triángulo para esta operación, donde $type = 0$ es para un triángulo orientado hacia arriba y $type = 1$ es para un triángulo invertido. $x, y, d$ describen este triángulo. Si $opt = 1$, hay un número adicional $w$ ($0 \le w < 2^{32}$) que indica el número sumado durante esta operación de modificación.

Se garantiza que todos los triángulos de entrada tienen un área distinta de cero y son triángulos válidos completamente contenidos dentro del triángulo mayor.

Salida

Para cada consulta con $opt = 2$, imprime un solo número en una nueva línea, que represente la suma dentro del área módulo $2^{32}$.

Ejemplos

Entrada 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

Salida 1

20
11
3

Entrada 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

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