Se consideră următoarea piramidă bidimensională:

             1
         1   1   1
     1   2   3   2   1
 1   3   6   7   6   3   1
............................

Se consideră că prima linie (cea cu un singur 1) este numerotată cu 1, a doua linie (cea cu 3 valori) este linia 2 ş.a.m.d.

Cerinţă

Deduceţi modul în care se formează piramida şi răspundeţi la Q întrebări de forma "Care este paritatea celui de-al C-lea număr de pe linia L?"

Date de intrare

Fişierul de intrare qtri.in conţine pe prima linie un număr natural Q reprezentând numărul de întrebări. Pe următoarele Q linii se găsesc câte două numere naturale L C reprezentând câte o întrebare de forma "Care este paritatea celui de-al C-lea număr de pe linia L?".

Date de ieşire

Fişierul de ieşire qtri.out va conţine exact Q linii. Pe linia i (1 <= i <= Q) din fişier se află un singur număr natural T reprezentând răspunsul la întrebarea cu numărul i. Dacă răspunsul este un număr par, atunci T=0, iar dacă răspunsul este impar, atunci T=1.

Restricţii

• Pentru orice întrebare, 1<= L <= 100 000 şi 1 <= C <= 2 * L - 1
• 1<= Q <= 2000

Exemplu

qtri.in	qtri.out	Explicaţii
3 2 2 3 4 4 6	1 0 1	Sunt 3 întrebări. Al doilea număr de pe linia 2 este 1, deci răspunsul la prima întrebare este 1 (număr impar). Al patrulea număr de pe linia 3 este 2 (par), deci răspunsul la a doua întrebare este 0. Al şaselea număr de pe linia 4 este 3 (impar), deci răspunsul la a treia întrebare este 1.

prof. Dan Pracsiu

Grupul Scolar "Stefan Procopiu" Vaslui

dpracsiu@yahoo.com