Problem description

Pamiętacie zadanie “Plakatowanie” z OI? Krzysztof jest w trakcie przygotowywania trudniejszej wersji tego zadania pod sparing. W zadaniu mamy dane N budynków stojących w szeregu jeden przy drugim, i–ty budynek jest reprezentowany przez prostokąt o szerokości W_i i wysokości H_i. Razem tworzą one długą ścianę, którą należy pokrywać plakatami. Plakaty są prostokątami, których boki są pionowe i poziome. Plakatów nie można ciąć, zginać, ani obracać; mogą one natomiast przybierać dowolne wymiary. Plakatowaniem nazwiemy całkowite pokrycie ściany plakatami, tak aby żaden plakat nie nachodził na siebie, ani nie wychodził poza obrys ściany. Należy szybko odpowiadać na zapytania o plakatowanie składające się z minimalnej liczby plakatów na segmencie ściany składającej się tylko i wyłącznie z budynków od L_i–tego do R_i–tego.

Aby zadanie nie było za łatwe, Krzysztof postanowił w niektórych testach wymusić odpowiadanie na zapytania w podanej na wejściu kolejności, poprzez szyfrowanie zapytań. Zamiast liczb L_i, R_i, na wejściu będą podane liczby K, A_i, B_i. Aby odzyskać wartości L_i, R_i należy użyć następujących wzorów:
L_i = ((K⋅Ans_i − 1)⊕A_i) R_i = ((K⋅Ans_i − 1)⊕B_i) gdzie ⊕ oznacza operację XOR, a Ans_i odpowiedź na i–te zapytanie. Uznajemy, że Ans₀ = 0.

Pomóż Krzysztofowi z testowaniem poprzez napisanie rozwiązania do opisanego powyżej zadania.

Wejście

W pierwszym wierszu wejścia znajdują się trzy liczby naturalne N, Q, K opisujące odpowiednio liczbę budynków, liczbę zapytań oraz parametr służący do odszyfrowywania zapytań. W następnych N wierszach znajdują się opisy budynków, gdzie i–ty z nich zawiera liczby naturalne W_i, H_i oznaczające odpowiednio szerokość oraz wysokość i–tego budynku. W następnych Q wierszach znajdują się opisy zapytań, gdzie i–ty z nich zawiera liczby naturalne A_i, B_i, które po odszyfrowaniu oznaczają zapytanie na przedziale [L_i,R_i].

Wyjście

Należy wypisać Q wierszy. W i–tym z nich ma się znaleźć odpowiedź na i–te zapytanie.

Ograniczenia

1 ≤ N, Q ≤ 500 000, 0 ≤ K ≤ 1, 1 ≤ W_i, H_i ≤ 10⁹, 1 ≤ L_i, R_i ≤ N, 1 ≤ A_i, B_i ≤ 2 ⋅ N.

Podzadania

Przykład

4 2 0
2 2
1 3
2 4
3 2
1 4
2 3

3
2