Колонія мурах
Група мурах дуже пишається своєю величезною колонією. Проте її великий розмір став проблемою, оскільки багато мурах не знають, як дістатися до різних частин колонії. Вони відчайдушно потребують вашої допомоги!
Колонія мурах складається з n мурашників, з'єднаних тунелями. Мурахи, будучи передбачливими, нумерували мурашники в порядку їх побудови. Перший мурашник, з номером 0, не потребував тунелю, але для кожного наступного мурашника, з 1 по n − 1, мурахи будували один тунель, що з'єднує новий мурашник з одним із вже існуючих. Цей тунель забезпечував можливість дістатися до будь-якого раніше побудованого мурашника, можливо, проходячи через інші мурашники. Тому вони не турбувалися про додаткові тунелі і продовжували будувати нові мурашники.
Ваше завдання — враховуючи структуру колонії та набір запитів, обчислити для кожного запиту найкоротший шлях між парами мурашників. Довжина шляху — це сума довжин усіх тунелів, які потрібно пройти.
Вхідні дані
Кожен тест складається з кількох рядків. Перший рядок містить кількість мурашників n (2 ≤ n ≤ 10^5) у колонії. Кожен з наступних n − 1 рядків містить два числа, що описують тунель. Рядок i (1 ≤ i ≤ n − 1) містить A[i] і L[i], які вказують, що мурашник i напряму з'єднаний з мурашником A[i] тунелем довжини L[i] (0 ≤ A[i] ≤ i − 1 і 1 ≤ L[i] ≤ 10^9). Наступний рядок містить кількість запитів q (1 ≤ q ≤ 10^5). Кожен з наступних q рядків описує запит і містить два різних числа s і t (0 ≤ s, t ≤ n − 1) — номери мурашників, між якими потрібно знайти відстань.
Після останнього тесту знаходиться рядок з одного нуля.
Вихідні дані
Для кожного тесту виведіть один рядок з q цілими числами, кожне з яких є довжиною найкоротшого шляху між парою мурашників запиту. Запишіть результати для кожного запиту в тому ж порядку, в якому запити були задані у вхідних даних.