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