Fiecare cristal $i$ trebuie setat la o valoare întreagă $a{~i~}$, aleasă astfel încât $l{~i~} ≤ a{~i~} ≤ r{~i~}$.
Dacă energia aleasă este prea mică, cristalul rămâne inert. Dacă este prea mare, riscă să se frângă — exact ca unele cristale din episodul unde Finn este capturat.

Pentru ca ritualul să fie stabil şi uniform, Prinţesa Gumiţă vrea ca toate cristalele să împărtăşească un divizor comun cât mai mare — adică vrea să maximizeze: gcd(a{~1~}, a{~2~}, ..., a{~N~})

Pentru ca ritualul să fie stabil şi uniform, Prinţesa Gumiţă vrea ca toate cristalele să împărtăşească un divizor comun cât mai mare — adică vrea să maximizeze: $gcd(a{~1~}, a{~2~}, ..., a{~N~})$

unde gcd(x{~1~}, x{~2~}, ..., x{~k~}) este cel mai mare număr $d$ care divide toate valorile $x{~1~}, x{~2~}, ..., x{~k~}$.

unde $gcd(x{~1~}, x{~2~}, ..., x{~k~})$ este cel mai mare număr $d$ care divide toate valorile $x{~1~}, x{~2~}, ..., x{~k~}$.

Misiunea ta, ca asistent inteligent al Prinţesei, este să determini valoarea maximă posibilă a acestui divizor comun, fără să fie necesar să specifici valorile exacte a{~i~}, ci doar rezultatul optim al gcd-ului.

Misiunea ta, ca asistent inteligent al Prinţesei, este să determini valoarea maximă posibilă a acestui divizor comun, fără să fie necesar să specifici valorile exacte $a{~i~}$, ci doar rezultatul optim al gcd-ului.

h2. Date de intrare
Fişierul $cristalegcd.in$ conţine:

* Pe prima linie: un număr întreg $n$ — numărul cristalelor.
* Urmează $n$ linii, fiecare conţinând doi întregi l{~i~} şi r{~i~} — intervalul permis pentru energia cristalului $i$.

* Pe prima linie: un număr întreg $N$ — numărul cristalelor.
* Urmează $N$ linii, fiecare conţinând doi întregi $l{~i~}$ şi $r{~i~}$ — intervalul permis pentru energia cristalului $i$.

h2. Date de ieşire
Fişierul $cristalegcd.out$ va conţine un singur număr întreg:

valoarea maximă a divizorului comun gcd(a{~1~}, a{~2~}, ..., a{~N~}) ce poate fi obţinută respectând toate intervalele l{~i~} ≤ a{~i~} ≤ r{~i~}

valoarea maximă a divizorului comun $gcd(a{~1~}, a{~2~}, ..., a{~N~})$ ce poate fi obţinută respectând toate intervalele $l{~i~} ≤ a{~i~} ≤ r{~i~}$

h2. Restricţii

|_. #  |_. Punctaj |_. Restricţii |
| 1 | 12 | $N, V ≤ 1 000$|
| 2 | 14 | Oricare două intervale $[l{~i~}, r{~i~}]$ sunt disjuncte|

| 3 | 22 | $N, V ≤ 100 000$ |
| 4 | 16 | $r{~i~} - l{~i~} = r{~j~} - l{~j~}$ pentru fiecare $1 ≤ i ≤ j ≤ N$|

| 3 | 21 | $N, V ≤ 100 000$ |
| 4 | 17 | $r{~i~} - l{~i~} = r{~j~} - l{~j~}$ pentru fiecare $1 ≤ i ≤ j ≤ N$|

| 5 | 36 | Fără alte restricţii |

!>problema/cristalegcd?cristale4.png!
 

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