Universal Cup Judging System

Universal Cup

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

Little 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$입니다. Little L은 다음 연산들을 수행합니다:

  • 정삼각형을 하나 선택하여 그 안에 있는 모든 격자의 수에 $w$를 더합니다.
  • 정삼각형을 하나 선택하여 그 안에 있는 모든 격자의 수의 합을 질의합니다.

그는 여러분이 각 질의 연산에 대한 답을 계산해 주기를 바랍니다. Little 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}$)가 주어집니다.

입력으로 주어지는 모든 삼각형은 넓이가 $0$이 아니며 큰 삼각형 내부에 완전히 포함되는 유효한 삼각형임이 보장됩니다.

출력

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