Bunicuţa Miruna are N nepoţei care sunt aşezaţi în linie şi sunt numerotaţi de la stânga spre dreapta, în ordine, cu numere naturale distincte de la 1 la N. Deoarece se apropie Ziua Copilului, Miruna le-a cumpărat nepoţeilor mai multe ouă Kinder. Aceste ouă Kinder nu sunt toate la fel, ci sunt de M tipuri (numerotate de la 1 la M) şi două culori (0 - roşu şi 1 - albastru). Tipul oului precizează cât de gustos este oul (dacă tipul t1<t2, atunci un ou de tipul t1 va fi mai gustos decât un ou de tipul t2).
Miruna va efectua operaţii de următoarele 3 tipuri:
Cerinţă
Scrieţi un program care să efectueze în mod eficient toate operaţiile descrise.
Date de intrare
Fişierul de intrare kinder.in va conţine pe prima linie 3 numere naturale N M T, reprezentând numărul de nepoţei, numărul de tipuri de ouă, respectiv numărul de operaţii ce vor fi efectuate. Pe fiecare dintre următoarele T linii va fi descrisă câte o operaţie. Linia care descrie o operaţie începe cu un număr (1, 2 sau 3) care indică tipul operaţiei, urmat de 4, 2, respectiv 4 numere naturale conform formatului operaţiei. Valorile scrise pe aceeaşi linie sunt separate prin spaţiu.
Date de ieşire
Fişierul de ieşire kinder.out va conţine câte o linie pentru fiecare operaţie de tip 3 efectuată. Pe linia i se află răspunsul pentru cea de-a i-a operaţie de tip 3 din fişierul de intrare.
Restricţii
1 ≤ N ≤ 50000
1 ≤ M ≤ 50000
1 ≤ T ≤ 50000
Pentru operaţii de tipul 1: 1 ≤ c ≤ N, 1 ≤ t ≤ M, 0 ≤ p ≤ 1, 1 ≤ nr ≤ 1000
Pentru operatii de tipul 2: 1 ≤ c ≤ N, 1 ≤ t ≤ M
Se garantează că nepotul c are cel puţin un ou de tip t
Pentru operaţii de tipul 3: 1 ≤ a ≤ b ≤ N, 0 ≤ p ≤ 1 1 ≤ x ≤ Numărul total de ouă de culoare p pe care le deţin nepoţii din intervalul [a, b].
Se garantează că nepoţii din intervalul [a,b] deţin cel puţin un ou de culoare p.
Exemple
kinder.in
kinder.out
Explicaţii
5 100 3
1 2 68 0 100
2 2 68
3 1 5 1 99
68
Miruna are 5 nepoţi, ouă de 100 de tipuri şi efectuează 3 operaţii.
La prima operaţie nepotul 2 primeşte 100 de ouă de tip 68 şi culoare 0
La a doua operaţie nepotul 2 vopseşte cele 100 de ouă de tipul 68 pe care le are în culoarea 1
La a treia operatie Miruna vede că al 99-lea cel mai gustos ou de culoare 1 pentru nepoţii din intervalul [1, 5] are tipul 68
