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

În laboratorul ei secret, Prinţesa Gumiţă a descoperit o colecţie de $n$ \textbf{cristale magice}, fiecare cu capacitatea de a stoca puteri extraordinare. Inspirată de întâmplările din Dimensiunea Cristalină, unde eroismul, non-violenţa şi fragilitatea se împletesc, ea doreşte să construiască un ritual de protecţie supremă pentru Regatul Gummy.

!>problema/cristalegcd?cristale3.png!

Fiecare cristal $i$ trebuie setat la o valoare întreagă $a_i$, aleasă astfel încât $l_i \leq a_i \leq r_i$.

În laboratorul ei secret, Prinţesa Gumiţă a descoperit o colecţie de $N$ cristale magice, fiecare cu capacitatea de a stoca puteri extraordinare. Inspirată de întâmplările din Dimensiunea Cristalină, unde eroismul, non-violenţa şi fragilitatea se împletesc, ea doreşte să construiască un ritual de protecţie supremă pentru Regatul Dulciurilor.
 
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 \textbf{factor comun} cât mai mare — adică vrea să maximizeze:
\[
\gcd(a_1, a_2, \dots, a_n),
\]
unde $\gcd(x_1, x_2, \dots, x_k)$ este cel mai mare număr $d$ care divide toate valorile $x_1, x_2, \dots, x_k$.

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~}$.

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 de intrare $cristalegcd.in$ ...

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$.

h2. Date de ieşire

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

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~}$

h2. Restricţii

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

* $N ≤ 200 000$
* $1 ≤ l{~i~} ≤ r{~i~} ≤ 1 000 000$
* Vom nota cu $V$ valoarea maximă a $r{~i~} (1 ≤ i ≤ N)$
 
|_. #  |_. Punctaj |_. Restricţii |
| 1 | 12 | $N, V ≤ 1 000$|
| 2 | 14 | Oricare două intervale $[l{~i~}, r{~i~}]$ sunt disjuncte|
| 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 |

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

| 3
6 7
15 19
1 10
| 6

|
h3. Explicaţie

...

Se poate alege $a{~1~} = 6, a{~2~} = 18, a{~3~} = 6$. Astfel, gcd-ul este $6$. Se observă că nu se poate obţine un gcd mai mare.

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