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

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

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