8686번 - Banki 다국어

Do bajtockich banków często przybywają kupcy, chcący wypłacić pieniądze ze swoich kont. W każdym banku dostępne są tylko dwa nominały, ale każdego z nich jest nieograniczona liczba. Nie każdą kwotę da się wypłacić, więc banki wywieszają listy, informujące klientów o niedostępnych sumach. Czasami listy te są tak długie, że banki wywieszają tylko początkową część niewypłacalnych kwot.

Kupiec Kozik chce wypłacić dużą kwotę pieniędzy. Zanim wyruszy do banku, to chciałby znać najwyższe kwoty, których banki nie są w stanie wypłacać. Kozik nie ma dostępu do list wywieszonych przez banki. Ma jedynie informację o dostępnych nominałach.

Pierwszy wiersz standardowego wejścia zawiera jedną liczbę całkowitą n (1 ≤ n ≤ 10⁶), oznaczającą liczbę bajtockich banków. W następnych n wierszach znajdują się opisy banków. Każdy wiersz zawiera dwie liczby całkowite x, y (1 ≤ x, y ≤ 10⁹), oznaczające wartości dostępnych nominałów.

Standardowe wyjście powinno zawierać n wierszy, będące odpowiedziami dla kolejnych banków. W każdym wierszu powinna znaleźć się jedna liczba całkowita, równa najwyższej kwocie, której bank nie może wypłacić, lub wartość -1, jeśli takiej kwoty nie można ustalić.