Problem 4282: Chițooc

Ești antrenorul echipei ZOMVS și te afli în satul Chițooc la finala turneului de fotbal. Este minutul 90' și echipa ta are avantaj, când deodată niște vaci invadează terenul!

Terenul este împărțit în $N$ zone de lungime egală, iar numărul de vaci din fiecare zonă este cunoscut (zonele terenului pot fi reprezentate ca un vector de $N$ elemente).

Fiindcă ai prevăzut situația aceasta, fiecare dintre jucătorii echipei tale are un lasou cu care poate face următoarea mișcare cel mult o singură dată:

Dacă jucătorul $i$ se află pe poziția $pos_i$ , el poate să adune toate vacile dintr-o zonă $j$ în zona $pos_i$ , cu condiția ca $j < pos_i$ .
Totuși, această mișcare consumă energia jucătorului respectiv. Dacă coeficientul energiei jucătorului este $coef_i$ , mișcarea va consuma ${coef_i} \cdot (pos_i - j)$ unități de energie.

Cerință

Fiindcă tu ești antrenorul lor, primești $Q$ întrebări de la jucători. Pentru fiecare întrebare primești două valori $l$ , $r$ și te întreabă care este numărul maxim de vaci care pot fi strânse într-o zonă și care este energia totală minimă necesară pentru a atinge acest număr folosind doar zone din intervalul $[l, r]$ .

Generarea datelor

Pentru a evita citirea unui volum foarte mare de date, doar primele $M$ întrebări vor fi citite din fișierul de intrare (unde $M \leq 10 \ 000$ ). Restul întrebărilor, de la $M+1$ până la $Q$ , se vor genera în programul vostru folosind următorul algoritm:

pentru i ← M + 1, Q execută
	l[i] ← ((l[i-1] ^ (a * l[i-M])) mod N) + 1
	r[i] ← ((r[i-1] ^ (b * r[i-M])) mod N) + 1
	dacă l[i] > r[i] atunci
		interschimbă l[i] cu r[i]
	sfârșit dacă
sfârșit pentru

Notă: Operația logică pe biți „XOR / SAU exclusiv” este reprezentată de simbolul ^ și se efectuează în C/C++ prin operatorul ^. Calculele intermediare din algoritmul de generare a datelor pot depăși capacitatea de reprezentare a tipurilor întregi pe 32 de biți (de exemplu int sau unsigned int). Se recomandă utilizarea tipurilor de date pe 64 de biți (de exemplu long long) unde este cazul.

Date de intrare

Pe prima linie a fișierului de intrare chitooc.in se dă $N$ (numărul de zone) și $K$ (numărul de jucători). Pe următoarea linie se află $N$ numere reprezentând numărul de vaci de pe fiecare zonă. Pe următoarele $K$ linii se află două valori: $pos$ și $coef$ , reprezentând poziția jucătorului și coeficientul de energie pentru aruncarea de lasou. Pe următoarea linie se vor afla 4 numere: $Q$ , $M$ , $a$ și $b$ , separate prin spații. Urmează $M$ linii conținând perechi $l, r$ reprezentând intervalele pentru primele $M$ întrebări citite direct din fișier.

Date de ieșire

În fișierul de ieșire chitooc.out, pentru fiecare $i \in [1, M]$ , pe linia $i$ se va afla răspunsul la a $i$ -a întrebare, adică numărul maxim de vaci care se pot strânge pe o zonă și energia totală minimă necesară, folosind doar zone din intervalul $[l_i, r_i]$ .

Iar pe următoarele linii se va afișa suma XOR a următoarelor interogări, grupate câte 100 (numărul de vaci se XOR-ează între ele, iar costurile se XOR-ează între ele).

De exemplu, dacă $M = 50$ și $Q = 400$ , se va afișa individual răspunsul la primele 50 de interogări, apoi câte o pereche de răspunsuri pentru query-urile din intervalele $[51, 150]$ , $[151, 250]$ , $[251, 350]$ , $[351, 400]$ .

Practic, dacă răspunsurile normale ar fi formate din perechile $(val_i, cost_i)$ , unde $i \in [1, Q]$ , $val_i$ este numărul maxim de vaci, iar $cost_i$ este energia minimă necesară (calculată pe baza coeficienților), atunci:

pentru $i \in [1, M]$ , se vor afișa $(val_i, cost_i)$ pe fiecare linie;
pentru restul întrebărilor se vor calcula și afișa perechile $(\text{sum\_xor\_val}_p, \text{sum\_xor\_cost}_p)$ , cu $p \geq 1$ , astfel încât:

\text{sum\_xor\_val}_p = \bigoplus_{i = M + (p-1)\cdot 100 + 1}^{\min(M + p \cdot 100,\, Q)} val_i

\text{sum\_xor\_cost}_p = \bigoplus_{i = M + (p-1)\cdot 100 + 1}^{\min(M + p \cdot 100,\, Q)} cost_i

Restricții și precizări

$1 \leq K \leq N \leq 3 \cdot 10^5$
$1 \leq Q \leq 8 \cdot 10^6$
$1 \leq M \leq \min(Q, 10~000)$
$0 \leq a, b \leq 1~000~000~000$
$0 \leq A_i \leq 10^9$
$1 \leq pos_1 < pos_2 < \dots < pos_{K} \leq N$
$0 \leq coef_i \leq 10^9$ , pentru $i=1, \dots, K$ .
$1 \leq l \leq r \leq N$

#	Punctaj	Restricții
1	7	$N, Q \leq 200$
2	24	$N \cdot Q \leq 10^6$
3	5	$K \cdot Q \leq 10^6$
4	45	$N, Q \leq 10^5$
5	19	Fără alte restricții

Exemplul 1

chitooc.in

9 4
2 8 3 0 1 1 4 9 10
1 2
3 3
6 1
7 5
3 3 1 1
1 9
4 7
8 9

chitooc.out

16 11
6 6
10 0

Explicație

Pentru primul exemplu: pentru a obține valoarea maximă și costul minim o să avem următoarele acțiuni:

Pentru prima întrebare:

jucătorul 2 trage vacile de pe poziția 2;
jucătorul 3 trage vacile de pe poziția 3;
jucătorul 4 trage vacile de pe poziția 6.

Pentru a doua întrebare:

jucătorul 3 trage vacile de pe poziția 5;
jucătorul 4 trage vacile de pe poziția 6.

Pentru a treia întrebare:

jucătorii nu o să facă nimic, iar numărul maxim de vaci o să fie 10.

Exemplul 2