VIII Wiosenny Turniej w Programowaniu Zespołowym Politechnika Poznańska, 29.05.2004

Opis

Jaś i Małgosia poznali wczoraj bardzo fajną grę. Polega ona na tym, że dwójka graczy naprzemiennie mówi liczby całkowite. Jeżeli jeden gracz powie jakąś liczbę, to jego przeciwnik może na to odpowiedzieć tylko liczbą co najmniej o 1 większą, a co najwyżej o 10 większą. Zakładamy, że przed grą w domyśle ostatnią wypowiedzianą liczbą jest 0, czyli (przy takich wartościach) gracz zaczynający może powiedzieć liczbę między 1 a 10. Kto pierwszy powie 100 (albo więcej) ten wygrywa.

Nie trzeba być geniuszem matematycznym, żeby sprawnie zauważyć strategię wygrywającą w tej grze. Dlatego Jaś i Małgosia uogólnili ją sobie. Zamiast 100 celem jest pewna liczba N, a zamiast maksymalnego "skoku", równego dotychczas 10, jest pewna liczba M (minimalny skok jest ciągle równy 1). Jednakże nie było to specjalnym utrudnieniem, gdyż nawet dla bardzo dużych liczb strategia ciągle była łatwa do znalezienia. Dlatego dzieci dokonały kolejnej modyfikacji. Najpierw losują sobie liczbę docelową N oraz pewien przedział. Następnie jedna osoba wybiera liczbę M (maksymalny skok) z wylosowanego przedziału, a jej przeciwnik zaczyna rozgrywkę już według normalnych zasad. Tym razem gra stała się nieco bardziej wymagająca i Małgosia przestała sobie radzić (co chwilę przegrywała z Jasiem). Jako że traktowała sprawę ambicjonalnie, to postanowiła dopomóc losowi, zdobywając program, który znajdzie za nią liczbę M, dzięki której Jaś nie będzie mógł wygrać. Napisz go dla niej (jest ładna, a do tego aktualnie nie ma chłopaka ;) ).

Zadanie

Mając dane N oraz pewien przedział, podaj najmniejsze i największe M z tego przedziału, dla którego rozpoczynający nie ma strategii wygrywającej lub stwierdź, że takie M nie istnieje.

Specyfikacja wejścia

W pierwszym wierszu wejścia podana jest dodatnia liczba całkowita D (D ≤ 50), oznaczająca liczbę gier do rozegrania, w których Małgosia chciałaby użyć Twojego programu. W kolejnych D wierszach podane są wylosowane parametry gry w postaci trzech liczb całkowitych: N, A i B (1 ≤ N ≤ 2.000.000.000, 1 ≤ A ≤ B ≤ N). N oznacza liczbę docelową, a A i B określają obustronnie domknięty przedział, z którego można wybrać M.

Specyfikacja wyjścia

Dla każdej rozważanej gry należy wypisać dwie liczby całkowite - najmniejsze i największe M z przedziału (być może obie wartości będą takie same), które pozbawią Jasia strategii wygrywającej, o ile tylko takie liczby istnieją. Jeśli nie istnieją, należy wypisać –1.

Przykład

Wejście

3
100 1 100
99 1 97
7 2 4

Przykładowe wyjście

1 99
2 32
-1