p=. !problema/bfs2?gang1.jpg!

Stâlpul e în poziţie verticală (înclinare $0$). Fiecare jucător are o anumită forţă ($B[i]$ - forţa băiatului $i$, $F[i]$ - forţa fetei $i$). Jocul decurge astfel: la fiecare pas, fie băiatul cel mai apropiat de stâlp, fie fata cea mai apropiată de stâlp, va arunca mingea spre stâlp (băiatul spre dreapta, fata spre stânga), după care va ieşi din joc. După orice aruncare, stâlpul se va înclina suplimentar în partea opusă aruncătorului cu o valoare egală cu forţa acestuia. Bineînţeles, cu cât forţa aruncătorului este mai mare, cu atât stâlpul se va înclina mai mult. Mai mult, *stâlpul nu va reveni la înclinarea iniţială după aruncare.*

Stâlpul e în poziţie verticală (înclinare $0$). Fiecare jucător are o anumită forţă ( $B[i]$ - forţa băiatului $i$, $F[i]$ - forţa fetei $i$). Jocul decurge astfel: la fiecare pas, fie băiatul cel mai apropiat de stâlp, fie fata cea mai apropiată de stâlp, va arunca mingea spre stâlp (băiatul spre dreapta, fata spre stânga), după care va ieşi din joc. După orice aruncare, stâlpul se va înclina suplimentar în partea opusă aruncătorului cu o valoare egală cu forţa acestuia. Bineînţeles, cu cât forţa aruncătorului este mai mare, cu atât stâlpul se va înclina mai mult. Mai mult, *stâlpul nu va reveni la înclinarea iniţială după aruncare.*

p=. !problema/bfs2?gang2.jpg!

* $1 ≤ B[i], F[i], S ≤ 10^9^,$ pentru orice $i$
* Pentru fiecare schimbare se garantează că $|x - y| = 1$
* *Se garantează că, înainte de efectuarea primei interschimbări, jocul se poate termina cu succes.*

* Pentru teste în valoare de $10$ puncte $N, M ≤ 100$ şi  $Q ≤ 250$
* Pentru alte teste în valoare de $20$ puncte $N,M ≤ 2500$ şi  $Q ≤ 6000$
* Pentru alte teste în valoare de $65$ puncte $N,M ≤ 100000$ şi  $Q ≤ 35000$

* Pentru teste în valoare de $10$ puncte $N, M ≤ 100$ şi $Q ≤ 250$
* Pentru alte teste în valoare de $20$ puncte $N,M ≤ 2500$ şi $Q ≤ 6000$
* Pentru alte teste în valoare de $65$ puncte $N,M ≤ 100000$ şi $Q ≤ 35000$

h2. Exemplu