Universal Cup Judging System

Universal Cup

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

Кішкентай 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.