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

!>problema/cristalegcd?cristale3.png!

Î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 Gummy.

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

Fiecare cristal $i$ trebuie setat la o valoare întreagă $a_i$, aleasă astfel încât $l{~i~} \leq a{~i~} \leq 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~})$
 
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~}$.

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

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

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

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

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

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 |

| 3
6 7
15 19
1 10
| 6

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

|
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") ==