Archiwum zadań programistycznych WWSI

Marek jest administratorem sieci w pewnej bardzo dużej firmie. Firma ta posiada ogromną liczbę serwerów a każdy z nich jest w stanie odpowiedzieć na ograniczoną liczbę zapytań w ciągu godziny. Serwery ponumerowane są od 1 do n. Marek jest znużony ciągłymi pytaniami swojego przełożonego o to który z serwerów jest najwolniejszy a który najszybszy w danym przedziale. Postanowił napisać program, który ułatwi mu życie. Jest jednak pewien problem Marek jest typowym administratorem sieci - nie ma pojęcia o programowaniu dlatego też poprosił Ciebie o pomoc.

Pomóż Markowi, napisz program, który sam określi najwolniejszy i najszybszy serwer w danym przedziale.

Wejście

W pierwszej linii wejścia znajduje się dokładnie jedna liczba naturalna t (1 <= t <= 10) określająca ilość zestawów danych. W kolejnych liniach znajduje się t zestawów danych.

W pierwszej linii każdego zestawu danych znajduje się liczba naturalna n (1 <= n <= 10⁶) określająca ilość serwerów jakie posiada firma. W kolejnej linii znajduje się dokładnie n liczb pooddzielanych pojedynczymi spacjami. Liczba i - ta w kolejności oznacza wydajność i - tego serwera. W kolejnych liniach znajdują się zapytania składane przez przełożonego Marka. Ilość zapytań nie będzie większa niż 1000.

Każde zapytanie zapisane jest w osobnej linii i składa się z dwóch liczb naturalnych x oraz y (1 <= x <= y <= n) gdzie x oznacza początek zaś y koniec przedziału, w którym szukamy najwolniejszego i najszybszego serwera. Wczytywanie zapytań należy zakończyć w momencie wczytania wartości 0 0.

Wyjście

Dla każdego zapytania należy w osobnej linii wypisać dwie liczby naturalne oddzielone pojedynczą spacją określające odpowiednio wydajność najwolniejszego serwera oraz wydajność najszybszego serwera.

Przykład

Dla danych:

2 
6 
10000 20000 30000 40000 30000 20000 
1 6 
5 6 
2 5 
0 0 
2 
12345 67890 
1 2 
2 2 
0 0 

Twój program powinien wypisać:

10000 40000 
20000 30000 
20000 40000 
12345 67890 
67890 67890