== include(page="template/taskheader" task_id="aiacuhexagoane") ==

Poveste şi cerinţă...

Un plan se poate pava folosind hexagoane regulate de aceeaşi dimensiune. O furnică poate trece dintr-un hexagon în altul numai dacă cele două hexagoane sunt unite printr-o latură a unui hexagon vecin comun, ca în figură (ex: din hexagonul 1 poate ajunge în hexagonul 5, deoarece ele sunt legate printr-o latură a hexagonului 2, vecin cu hexagoanele 1 şi 5).
 
!problema/aiacuhexagoane?hexagoane1.png!
 
O parte a planului este preluată şi se formează un grid hexagonal. Grid-ul hexagonal va avea $N$ linii. Liniile impare conţin câte $M$ hexagoane fiecare, iar liniile pare conţin câte $M-1$ hexagoane fiecare. Hexagoanele din grid se numerotează ca în figura alăturată. Fiind date $Q$ perechi de hexagoane $(h1, h2)$, se cere să se determine dacă furnica, pornind din $h1$, poate ajunge în $h2$, eventual trecând prin alte hexagoane intermediare pentru a forma un drum.
 
!problema/aiacuhexagoane?hexagoane2.png!

h2. Date de intrare

Fişierul de intrare $aiacuhexagoane.in$ ...

Fişierul de intrare $aiacuhexagoane.in$ conţine pe prima linie două numere naturale $N$ şi $M$, reprezentând numărul de linii, respectiv numărul de hexagoane aflate pe prima linie. Următoarea linie conţine un număr natural $Q$, reprezentând numărul de întrebări, iar fiecare din următoarele $Q$ linii conţine câte două numere separate prin spaţiu, reprezentând valorile $h1$ şi $h2$ din enunţ.
 

h2. Date de ieşire

În fişierul de ieşire $aiacuhexagoane.out$ ...

În fişierul de ieşire $aiacuhexagoane.out$ conţine $Q$ linii, corespunzătoare celor $Q$ perechi de hexagoane. Pentru fiecare pereche se va afişa $da$, în cazul în care există drum între hexagoanele perechii respective, sau $nu$, în caz contrar.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 10^9^; 2 ≤ M ≤ 10^9^; 1 ≤ Q ≤ 10^5^$.
* Pentru teste in valoare de 20 de puncte $N, M ≤ 15$.
* Pentru teste in valoare de 65 de puncte $N, M ≤ 800$.
* Problema va fi evaluată pe teste în valoare de 90 de puncte.
* Exemplele vor reprezenta teste în valoare de 10 ("puncte din oficiu") şi vor fi cu feedback.
* Cele $Q$ perechi de hexagoane vor fi unice. Atenţie: perechea de hexagoane $h1$ şi $h2$ este diferită de $h2$ şi $h1$.
* $h1 ≠ h2$

h2. Exemplu
table(example). |_. aiacuhexagoane.in |_. aiacuhexagoane.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 2 3
3
1 5
1 2
3 4
| da
nu
da

|
h3. Explicaţie

...

Între hexagonul 1 şi hexagonul 5 există un drum pe latura hexagonului 2.
Între hexagonul 1 şi hexagonul 2 nu există drum, hexagonul 2 fiind izolat de toate celelalte.
Între hexagonul 3 şi hexagonul 4 există un drum pe latura hexagonului 2.
 
!problema/aiacuhexagoane?hexagoane3.png!
 

== include(page="template/taskfooter" task_id="aiacuhexagoane") ==
 

== include(page="template/taskfooter" task_id="aiacuhexagoane") ==