Мало кто знает, но давным-давно на Марсе существовало развитое государство. В его состав входили n городов, пронумерованных целыми числами от 1 до n, столица имела номер 1. Некоторые пары городов были соединены дорогой. Жители государства были очень расчётливыми, поэтому между любыми двумя городами существовал ровно один путь (возможно, состоящий из нескольких дорог).

Так как государство было развитым, его жители любили путешествовать. Туристический маршрут на Марсе задавался двумя числами L и R. Это означало, что турист начинает путь в городе с номером L, затем едет в город с номером L + 1 (не заезжая в города, не лежащие на пути между L и L + 1), затем едет в город с номером L + 2, и так далее. Последним городом в маршруте был город с номером R. Главной достопримечательностью маршрута туристы считали ближайший к столице город среди всех посещённых на этом маршруте (если расстояние между городами считать по дорогам).

Зная карту марсианского государства и все туристические маршруты, укажите для каждого маршрута номер города, который являлся его главной достопримечательностью.

В первой строке дано целое число n — количество городов (1 ≤ n ≤ 2 · 10⁵).

Затем в n − 1 строке перечислены дороги. Каждая дорога задаётся двумя номерами городов, которые эта дорога соединяет (1 ≤ v_i, u_i ≤ n; v_i ≠ u_i).

В (n + 1)-й строке дано целое число q — количество туристических маршрутов (0 ≤ q ≤ 10⁶).

Затем в q строках перечислены сами маршруты. Каждый маршрут — пара целых чисел L_i, R_i (1 ≤ L_i ≤ R_i ≤ n).

Выведите q целых чисел по одному в строке — номер главной достопримечательности для каждого маршрута. Числа следует выводить в том же порядке, в котором были описаны соответствующие маршруты.

В этой задаче большие объёмы ввода и вывода, а Time Limit выставлен достаточно жёстко. Для решений на языке C++ рекомендуем использовать компилятор Visual C++ 2013.