Portali in caduta#10441
Esistono mondi, su ciascuno dei quali si trova un portale. Inizialmente il mondo i~(1 \le i \le n) si trova nel punto con coordinata pari a e coordinata pari a A_i~(1 \le A_i \le 10^9). Su ogni mondo si trova anche una mucca. Al tempo tutte le coordinate sono distinte, e i mondi iniziano a cadere: il mondo si muove continuamente nella direzione negativa dell'asse con velocità unità al secondo.
Ogni volta che due mondi si trovano alla stessa coordinata , eventualmente in un istante non intero, i loro portali si «allineano», e la mucca su uno dei mondi può spostarsi istantaneamente sull'altro mondo.
Per ogni , la mucca sul mondo vuole raggiungere il mondo Q_i (Q_i \ne i). Aiuta ciascuna mucca a determinare il tempo minimo necessario per raggiungere la propria destinazione, spostandosi in modo ottimale.
Per ogni interrogazione, stampa il tempo di viaggio come frazione , dove e sono interi positivi coprimi, oppure stampa se il viaggio è impossibile.
Nella prima riga è contenuto un singolo numero intero n~(2 \le n \le 2 \cdot 10^5).
Nella seconda riga sono contenuti numeri interi separati da spazi A_1, A_2, \ldots, A_n.
Nella terza riga sono contenuti numeri interi Q_1, Q_2, \ldots, Q_n.
Stampa righe. Nella -esima riga, stampa il tempo minimo di viaggio per la mucca .
Esempio 1