Little Cyan Fish on unohtanut alkuluvun $P$. Hän muistaa, että $9 \times 10^{17} \le P \le 10^{18}$.
Ennen kuin hän unohti luvun $P$, hän kirjoitti muistiin $n$ kokonaislukua $a_1, a_2, \dots, a_n$. Hän kirjoitti muistiin myös kunkin kokonaisluvun multiplikatiivisen käänteisalkion modulo $P$, ja sekoitti sitten nämä käänteisalkiot saadakseen luvut $b_1, b_2, \dots, b_n$. Kokonaisluvun $x$ multiplikatiivinen käänteisalkio modulo $P$ on se yksikäsitteinen kokonaisluku $y$, jolle pätee $1 \le y < P$ ja $xy \equiv 1 \pmod P$.
Auta Little Cyan Fishiä löytämään alkuluku, joka on yhteensopiva hänen kahden listansa kanssa. Täsmällisemmin sanottuna etsi alkuluku $Q$, jolle $9 \times 10^{17} \le Q \le 10^{18}$, jokainen kahden listan kokonaisluku on pienempi kuin $Q$, ja on olemassa lukujen $1, 2, \dots, n$ permutaatio $\pi$, joka toteuttaa ehdon $a_i b_{\pi_i} \equiv 1 \pmod Q$ kaikilla $1 \le i \le n$.
Syöte on luotu seuraavasti. Alkuluku $P$ valitaan tasajakautuneesti satunnaisesti kaikkien välillä $[9 \times 10^{17}, 10^{18}]$ olevien alkulukujen joukosta. Tällöin $n = 10^5$, ja jokainen $a_i$ valitaan riippumattomasti ja tasajakautuneesti satunnaisesti väliltä $[1, P - 1]$. Lopuksi käänteisalkiot sekoitetaan tasajakautuneesti satunnaisesti. Eri testitiedostot luodaan toisistaan riippumattomasti.
Testitiedostoja on enintään $20$.
Syöte
Syötteen ensimmäinen rivi sisältää yhden kokonaisluvun $n$ ($n = 10^5$).
Toinen rivi sisältää $n$ kokonaislukua $a_1, a_2, \dots, a_n$ ($1 \le a_i < 10^{18}$). Kolmas rivi sisältää $n$ kokonaislukua $b_1, b_2, \dots, b_n$ ($1 \le b_i < 10^{18}$).
On taattu, että nämä kaksi listaa toteuttavat yllä kuvatut ehdot vähintään yhdelle alkuluvulle $P$.
Tuloste
Tulosta yksi rivi, joka sisältää yhden kokonaisluvun $Q$, joka ilmaisee kahden listan kanssa yhteensopivan alkuluvun. Jos kelvollisia vastauksia on useita, tulosta mikä tahansa niistä.
Esimerkit
Syöte 1
1 2 499999999999999995
Tuloste 1
999999999999999989
Huomautus
Esimerkki ei täytä syötteen rajoituksia. Se on annettu vain syöte- ja tulostemuotojen havainnollistamiseksi. Ohjelmasi ei tarvitse läpäistä esimerkkiä.
Esimerkissä $P = 999999999999999989$. Esimerkiksi $2 \times 499999999999999995 = P + 1$.