Problem 2312: kinder

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 $t_1 < t_2$ , atunci un ou de tipul $t_1$ va fi mai gustos decât un ou de tipul $t_2$ ).
Miruna va efectua operaţii de următoarele $3$ tipuri:

Tip	Nume	Format	Efect
1	Update	$c \ t \ p \ nr$	Copilul $c$ primeşte nr ouă de tip $t$ şi culoare $p$
2	Update	$c \ t$	Copilul $c$ ia fiecare ou de tipul $t$ care este al său şi îl vopseşte în culoarea opusă (din $0$ în $1$ sau din $1$ în $0$ )
3	Query	$a \ b \ p \ x$	Miruna se uită la ouăle de culoare $p$ care aparţin copiilor din intervalul $[a, b]$ şi vrea să afle tipul celui de-al $x$ -lea cel mai gustos ou.

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 și precizări

$1 \leq N \leq 50 \ 000$
$1 \leq M \leq 50 \ 000$
$1 \leq T \leq 50 \ 000$
Pentru operaţii de tipul $1$ : $1 \leq c \leq N, 1 \leq t \leq M, 0 \leq p \leq 1, 1 \leq nr \leq 1 \ 000$
Pentru operatii de tipul $2$ : $1 \leq c \leq N, 1 \leq t \leq M$
Se garantează că nepotul $c$ are cel puţin un ou de tip $t$
Pentru operaţii de tipul $3$ : $1 \leq a \leq b \leq N, 0 \leq p \leq 1$
$1 \leq x \leq$ 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$ .

Exemplu

kinder.in

5 100 3
1 2 68 0 100
2 2 68
3 1 5 1 99

kinder.out

Explicație

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$

kinder