Düşən portallar

$n$ dünya var, hər birində bir portal yerləşir. Əvvəlcə i~(1 \le i \le n) dünyası $x$-koordinatı $i$ və $y$-koordinatı A_i~(1 \le A_i \le 10^9) olan nöqtədə yerləşir. Hər dünyada həmçinin bir inək var. $0$ vaxt anında bütün $y$-koordinatları müxtəlifdir və dünyalar düşməyə başlayır: $i$ dünyası $y$ oxunun mənfi istiqamətində saniyədə $i$ vahid sürətlə fasiləsiz hərəkət edir.

İki dünya eyni $y$-koordinatında olduqda, bu tam olmayan vaxt anında da baş verə bilər, onların portalları «düzülür» və bir dünyadakı inək anında digər dünyaya keçə bilər.

Hər $i$ üçün $i$ dünyasındakı inək Q_i (Q_i \ne i) dünyasına çatmaq istəyir. Hər inəyə, optimal şəkildə hərəkət etdikdə, təyinat nöqtəsinə çatmaq üçün lazım olan minimum vaxtı təyin etməyə kömək edin.

Hər sorğu üçün səyahət vaxtını $a/b$ kəsri şəklində çıxarın, burada $a$ və $b$ — müsbət qarşılıqlı sadə tam ədədlərdir, əks halda səyahət mümkün deyilsə $-1$ çıxarın.