Существует n городов, пронумерованных от 1 до n. Все города соединены с помощью (n−1) дорог так, что от каждого города можно добраться до каждого. Каждая дорога имеет определенную длину.
Известно, что город с номером i был захвачен кланом бандитов с номером ai (1≤ai≤n) в момент времени ti. После захвата города i (то есть, начиная с момента времени ti включительно), через него могут проходить только представители клана ai.
Ответьте на m вопросов следующего вида:
u v b T
— сможет ли представитель клана b попасть из города u в город v, если он начнет свое путешествие в момент времени T. В случае невозможности совершения путешествия, необходимо также сообщить номер первого города на пути от u до v, через который невозможно проехать.
Первая строка содержит целое число n (2≤n≤105) — количество городов.
Каждая из следующих (n−1) строк содержит два целых числа pi и di (1≤pi<i, 1≤di≤103), обозначающие дорогу между городами i и pi длины di. Индексация начинается с 2.
Следующая строка содержит n целых чисел ai (1≤ai≤n), обозначающих номера кланов, захвативших соответствующий город.
Следующая строка содержит n целых чисел ti (1≤ti≤109), обозначающих моменты времени захвата каждого города.
Следующая строка содержит целое число m (1≤m≤105) — количество запросов.
Последние m строк описывают запросы. Каждый из них содержит четыре целые числа ui, vi, bi, Ti (1≤ui,vi,bi≤n, 1≤Ti≤109) — номера начального и конечного городов очередного пути, номер клана путешественника, и момент времени начала путешествия соответственно.
Для каждого запроса выведите в отдельной строке одно целое число — номер первого города на пути от u до v, через который невозможно пройти. Если такого города не существует, выведите «-1
».
Обратите внимание на большой объем входных и выходных данных в этой задаче. Советуем использовать быстрые средства ввода и вывода, например scanf/printf
вместо cin/cout
в языке C ++
и sys.stdin.readline
вместо input
в Python
. Также советуем использовать интерпретатор PyPy
при решении задачи на Python
.
(7 баллов): pi=1;
(9 баллов): n,m≤103;
(11 баллов): pi=i−1,ti=1;
(18 баллов): pi=i−1,ai=1,bi=2;
(15 баллов): pi=i−1;
(11 баллов): ti=1;
(17 баллов): ai=1,bi=2;
(12 баллов): без дополнительных ограничений.