Problem description

Janusz, znudzony swoim życiem, postanowił dokonać prawdziwego rozlewu krwi w całym pięknym Bajtokraju. Składa się on z miast ponumerowanych od 1 do N. Do tej pory kraj prosperował bez zarzutów, więc mieszkańcom udało się nawet stworzyć specjalne, dwukierunkowe linie metra pomiędzy niektórymi z miast.

Żądze Janusza muszą jednak zostać zaspokojone. Pierwszym jego dekretem wydanym w Bajtokraju było to aby w żadnym momencie nie dopuścić aby liczba ludności w którymkolwiek z miast przekroczyła 10⁹. Kiedy tylko liczba ludności jest osiąga lub przekracza 10⁹ to natychmiast zabijanych jest dokładnie 10⁹ mieszkańców.

Niestety Januszowi to nie wystarczyło. Kolejną czynnością jaką wykonał było wysłanie grup buntowników do niektórych z miast. Kiedy wysyła on grupę d buntowników do miasta o numerze v to liczba mieszkańców tego miasta wzrasta o d, a następnie wszystkie miasta do których da się dojechać korzystając z co najwyżej d przejażdżek metrem (wliczając w to v) przechodzą rewolucję. Rewolucja polega na kompletnym przeformowaniu danego miasta. Okazuje się, że po rewolucji liczba ludności danego miasta zmienia się – zapis dziesiętny się odwraca, a wiodące zera są ucinane. Nikt nie wie co jest tego powodem, ale mało osób rozumie podburzoną ludność. Jeśli więc liczba ludności przed rewolucją wynosiła 450, to po rewolucji wyniesie ona 54.

Janusz był już prawie zadowolony ze swojego dzieła. Teraz chce dokonać tylko ostatecznej rzezi. Chce wybrać liczbę e i względem niej podzielić kraj na dwie spójne części, tak że do jednej z nich trafią wszystkie miasta o numerach mniejszych bądź równych e, zaś do drugiej wszystkie pozostałe. Następnie znajdzie miasta z największą liczbą mieszkańców w każdej z tych części i wystawi je na pojedynek. Każdy mieszkaniec tych miast musi wziąć udział w pojedynku. Janusz będzie najbardziej zadowolony z podziału kraju jeśli różnica w liczebności podczas tej bitwy będzie jak największa.

Niestety Janusz nie wie, które z posłanych przez niego grup buntowników dotarły do celu, a podziału chce dokonać jak najszybciej. Pomóż Januszowi określić optymalne punkty podziału biorąc pod uwagę możliwy aktualny stan kraju.

Przykładowy stan miast na początku pokazany jest na rysunku poniżej.

A tak wygląda po wizycie pierwszych buntowników. Widać, że optymalnym punktem podziału jest 1.

Napisz program, który: wczyta opis ludności kraju przed posłaniem buntowników przez Janusza, opis połączeń metra występujących w kraju oraz opis działania wszystkich grup buntowników i na każdy z nich odpowie optymalnym punktem podziału przy założeniu, że ta i wszystkie poprzednie dotarły do odpowiednich miast, a ostatecznie wynik wypisze na standardowe wyjście.

Wejście

W pierwszym wejścia znajduje się jedna dodatnia liczba naturalna N, oznaczająca liczbę miast. W kolejnym wierszu wejścia znajduje się ciąg N liczb naturalnych A_i, poodzialanych pojedynczymi odstępami. i-ta liczba określa liczbę mieszkańców i-tego miasta.

W kolejnym wierszu znajduje się jedna liczba M oznaczająca liczbę linii metra w kraju, a następnie znajduje się M wierszy, a w każdym z nich dwie liczby naturalne a i b oodzielone pojedyncznym odstępem oznaczające, że istnieje dwukierunkowa linia metra pomiędzy miastami o numerach a i b.

W kolejnym wierszu znajduje się liczba Q oznaczająca liczbę rozkazów wysłania buntowników wydanych przez Janusza. Następnie pojawi się Q wierszy, a w każdym z nich dwie liczby naturalne v oraz d oznaczające, że Janusz wysłał d buntowników do miasta o numerze v.

Wyjście

Twój program powinien wypisać na wyjście Q liczb naturalnych w kolejnych wiersza wyjścia. W i-tym wierszu wyjścia powinna znaleźć się liczba oznaczająca optymalny punkt podziału kraju pod warunkiem, że dotarło do niego pierwszych i grup buntowników.

Ograniczenia

2 ≤ N ≤ 100 000, 0 ≤ M ≤ 100 000, 1 ≤ Q ≤ 100 000 , 0 ≤ A_i, d ≤ 10⁹, 1 ≤ a, b, v ≤ N

Przykład

7
21 37 7 51 12 43 30
4
1 5
2 3
2 5
4 6
1
3 3

1