RoAlgo PreOJI 2026 X | OrQueries

Cerință

Se considera axa $Ox$. Putem face urmatoarele operatii:

• $1$: Adaugam punctul $x$, la pozitia $\frac{a}{b}$ pe axa, cu ponderele $c$, unde $a, b, c \in \Z$.
• $2$: Consideram toate punctele intre $\frac{a_1}{b_1}$ si $\frac{a_2}{b_2}$ inclusiv, unde $a_1, b_1, a_2, b_2 \in \Z$. Sa se afle SAU-ul pe biti al lor.

Date de intrare

Pe prima linie a fișierului de intrare orqueries.in se găseste numarul natural $Q$, reprezentand numarul de operatii pe care le efectuam.

Pe urmatoarele $Q$ linii se vor afla tuple de forma $1\ a\ b\ c$, sau $2\ a_1\ b_1\ a_2\ b_2$, in functie de tipul operatiei efectuate.

Atentie! Initial, vom considera $L = 0$. Pentru fiecare operatie, vom XOR-a $a$, $b$ sau $a_1$, $b_1$, $a_2$, $b_2$ in functie de operatie cu $L$ pentru a afla valoarea adevarata a variabilei. Ulterior, $L$ va fi egal cu rezultatul ultimei operatii de tip $2$.

Date de ieșire

Pentru fiecare operatie de tip $2$, se va afisa rezultatul SAU-ului pe biti al punctelor intre $\frac{a_1}{b_1}$ si $\frac{a_2}{b_2}$ pe cate o linie in fisierul orqueries.out.

Restricții și precizări

• $1 \leq Q \leq 100\ 000$
• $0 \leq c_i < 2^{31}$
• $1 \leq a \oplus L, b \oplus L, a_1 \oplus L, b_1 \oplus L, a_2 \oplus L, b_2 \oplus L \leq 1\ 000\ 000\ 000$, la orice moment, unde notam operatia XOR cu $\oplus$.
• Atentie! Pot exista mai multe puncte in aceeasi coordonata.
• Pentru teste in valoare de $30$ de puncte, $Q \leq 1000$.
• Pentru alte teste in valoare de $15$ puncte, $\frac{a \oplus L}{b \oplus L}, \frac{a_1 \oplus L}{b_1 \oplus L}, \frac{a_2 \oplus L}{b_2 \oplus L} \in \Z; 1 \leq \frac{a \oplus L}{b \oplus L}, \frac{a_1 \oplus L}{b_1 \oplus L}, \frac{a_2 \oplus L}{b_2 \oplus L} \leq 100\ 000$, $\frac{a_1 \oplus L}{b_1 \oplus L} = \frac{a_2 \oplus L}{b_2 \oplus L}$
• Pentru alte teste in valoare de $15$ puncte, $\frac{a \oplus L}{b \oplus L}, \frac{a_1 \oplus L}{b_1 \oplus L}, \frac{a_2 \oplus L}{b_2 \oplus L} \in \Z; 1 \leq \frac{a \oplus L}{b \oplus L}, \frac{a_1 \oplus L}{b_1 \oplus L}, \frac{a_2 \oplus L}{b_2 \oplus L} \leq 100\ 000$
• Pentru alte teste in valoare de $20$ de puncte, $0 \leq c_i \leq 1$.
• Pentru alte teste in valoare de $20$ de puncte, nicio restrictie suplimentara.

Exemplul 1

orqueries.in

5
1 1 2 5
1 3 4 3
2 1 3 1 1
2 3 2 4 2
1 2 2 8

orqueries.out

7
3

Explicație

Initial, $L = 0$.

Primele doua operatii insereaza punctele $\frac{1 \oplus L = 1}{2 \oplus L = 2} = 0.5$ cu ponderele $5$ si $\frac{3 \oplus L = 3}{4 \oplus L = 3} = 0.75$ cu ponderele $3$.

A treia operatie face query intre punctele $\frac{1 \oplus L = 1}{3 \oplus L = 3} = 0.(3)$ si $\frac{1 \oplus L = 1}{1 \oplus L = 1} = 1$. Toate punctele sunt incluse, asadar rezultatul este $5 \vert 3 = 7$, unde notam operatia OR cu $\vert$.

Dupa a treia operatie, $L = 7$.

A patra operatie face query intre punctele $\frac{3 \oplus L = 4}{2 \oplus L = 5} = 0.8$ si $\frac{4 \oplus L = 3}{2 \oplus L = 5} = 0.6$. Doar punctul $\frac{3}{4} = 0.75$ cu ponderele $3$ este inclus, asadar rezultatul este $3$.

Dupa a patra operatie, $L = 3$.

A cincea operatie insereaza punctul $\frac{2 \oplus 3 = 1}{2 \oplus 3 = 1} = 1$ cu ponderele $8$.

Exemplul 2

orqueries.in

4
1 5 2 1
1 2 5 2
2 1 2 4 5
2 2 5 5 2

orqueries.out

0
3

Explicație

Initial, $L = 0$.

Primele doua operatii insereaza punctele $\frac{5 \oplus L = 5}{2 \oplus L = 2} = 2.5$ cu ponderele $1$ si $\frac{2 \oplus L = 2}{5 \oplus L = 5} = 0.4$ cu ponderele $2$.

A treia operatie face query intre punctele $\frac{1 \oplus L = 1}{2 \oplus L = 2} = 0.5$ si $\frac{4 \oplus L = 4}{5 \oplus L = 5} = 0.8$. Cum nu exista niciun punct intre aceste coordonate, rezultatul este $0$.

Dupa a treia operatie, $L = 0$.

A patra operatie face query intre punctele $\frac{2 \oplus L = 2}{5 \oplus L = 5} = 0.4$ si $\frac{5 \oplus L = 5}{2 \oplus L = 2} = 2.5$. Cum toate punctele sunt incluse, rezultatul este $1 \vert 2 = 3$.

Dupa a patra operatie, $L = 3$.