Дерево с p вершинами представляет собой связный граф с p - 1 ребром. Обозначим через r корень дерева. Если a - вершина на расстоянии l от r, а b - вершина на расстоянии l + 1 от r, при этом a соединено с b, то будем a называть предком b.

Аналогично если a находится на расстоянии l от r и b на расстоянии l + k от r, и существует путь длины k от a до b, то будем называть a k-ым предком b.

Сьюзен любит играть с графами, а структура данных Дерево - одна из ее любимых. Она сделала задачу и хочет знать, сможет ли кто-нибудь решить ее. Иногда она добавляет или удаляет вершину, являющуюся листом. Ваша задача - в любой момент найти k-го предка вершины.

Входные данные

Первая строка содержит количество тестов t (1 ≤ t ≤ 3). Далее следуют t тестов. Первая строка каждого теста содержит количество p (1 ≤ p ≤ 105) вершин в дереве. Каждая из следующих p строк содержит два целых числа x и y означающих что y является предком x. Если y равно 0, то x корень дерева (0 не принадлежит дереву). Известно, что 1 ≤ x, y ≤ 105.

Следующая строка содержит количество запросов q (1 ≤ q ≤ 105). Каждая из следующих q строк содержит запрос.

• 0 y x: x добавляется новым листом с предком y. x еще не в дереве, y принадлежит дереву.
• 1 x: вершина-лист x удаляется из дерева. x является листом дерева.
• 2 x k: выведите k-го (1 ≤ k ≤ 105) предка x. x - вершина в дереве.

Выходные данные

Для каждого запроса типа 2 выведите k-го предка x. Если k-ый предок не существует, выведите 0. Если указанная вершина не существует, выведите 0.