|$2$|Update|$c t$|Copilul $c$ ia fiecare ou de tipul $t$ care este al sau si il vopseste in culoarea opusa (din $0$ in $1$ si din $1$ in $0$)|
|$3$|Query|$a b p x$|Miruna se uita la ouale de culoare $p$ care apartin copiilor din intervalul $[a, b]$ si vrea sa afle tipul celui de-al $x$-lea cel mai gustos ou.|
Scrieti un program care sa efectueze in mod eficient toate operatiile descrise.
h2. Date de intrare
Fisierul de intrare $kinder.in$ ...
Fisierul de intrare $kinder.in$ va contine pe prima linie $3$ numere naturale $N M T$, reprezentand numarul de nepotei, numarul de tipuri de oua, respectiv numarul de operatii ce vor fi efectuate. Pe fiecare dintre urmatoarele $T$ linii va fi descrisa cate o operatie. Linia care descrie o operatie incepe cu un numar ( $1$, $2$ sau $3$) care indica tipul operatiei, urmat de $4$, $2$, respectiv $4$ numere naturale conform formatului operatiei. Valorile scrise pe aceeasi linie sunt separate prin spatiu.
h2. Date de iesire
In fisierul de iesire $kinder.out$ ...
Fisierul de iesire $kinder.out$ va contine cate o linie pentru fiecare operatie de tip $3$ efectuata. Pe linia $i$ se afla raspunsul pentru cea de a $i$-a operatie de tip $3$ din fisierul de intrare.
h2. Restrictii
* $... ≤ ... ≤ ...$
* $1 ≤ N, M, T ≤ 50000$
* Pentru operatii de tipul $1$: $1 ≤ c ≤ N, 1 ≤ t ≤ M, 0 ≤ p ≤ 1, 1 ≤ q ≤ 1000$
* Pentru operatii de tipul $2$: $1 ≤ c ≤ N, 1 ≤ t ≤ M$
Se garanteaza ca nepotul $c$ are cel putin un ou de tip $t$
* Pentru operatii de tipul $3$: $1 ≤ a ≤ b ≤ N, 0 ≤ p ≤ 1$
$1 ≤ x ≤$ Numarul total de oua de culoare $p$ pe care le detin nepotii din intervalul $[a, b]$
Se garanteaza ca nepotii din intervalul $[a,b]$ detin cel putin un ou de culoare $p$.
h2. Exemplu
table(example). |_. kinder.in |_. kinder.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|5 100 3
1 2 68 0 100
2 2 68
3 1 5 1 99
|68
|
h3. Explicatie
...
Miruna are $5$ nepoti, oua de $100$ de tipuri si efectueaza $3$ operatii. La prima operatie nepotul $2$ primeste $100$ de oua de tip $68$ si culoare $0$. La a doua operatie nepotul $2$ vopseste cele $100$ de oua de tipul $68$ pe care le are in culoarea $1$. La a treia operatie Miruna vede ca al $99$-lea cel mai gustos ou de culoare $1$ pentru nepotii din intervalul $[1, 5]$ are tipul $68$.
== include(page="template/taskfooter" task_id="kinder") ==
