Düşən portallar
Verilmişdir n dünya, hər birində portal var. Əvvəlcə dünya i (burada 1 ≤ i ≤ n) x koordinatında i və y koordinatında A[i] (1 ≤ A[i] ≤ 10^9) yerləşir. Həmçinin hər dünyada bir inək var. 0 zaman anında bütün y koordinatları fərqlidir və dünyalar düşməyə başlayır: dünya i fasiləsiz olaraq mənfi y istiqamətində saniyədə i vahid sürətlə hərəkət edir.
Hər hansı bir vaxtda, iki dünya eyni y koordinatında olduqda (mümkün olan qismən vaxtda), portallar "bərabərləşir". Bu o deməkdir ki, bir dünyadakı inək dərhal başqa bir dünyaya keçə bilər.
Hər bir i üçün dünya i-dəki inək Q[i] dünyasına (Q[i] ≠ i) getmək istəyir. Hər bir inəyə optimal hərəkət edərsə, onun yolunun nə qədər vaxt alacağını müəyyən etməyə kömək edin.
Hər bir sorğuya cavab a / b qismində olmalıdır, burada a və b müsbət və qarşılıqlı sadə tam ədədlərdir, ya da səyahət mümkün deyilsə -1 olmalıdır.
Giriş Məlumatları
Birinci sətir tək tam ədəd n (2 ≤ n ≤ 2 * 10^5) ehtiva edir. Növbəti sətir n tam ədəd A[1], A[2], ..., A[n] ehtiva edir. Növbəti sətir n tam ədəd Q[1], Q[2], ..., Q[n] ehtiva edir.
Çıxış Məlumatları
n sətir çap edin, burada i-ci sətir inək i-nin yolunun uzunluğunu ehtiva edir.