Joseph loves games about a tree! His friend Nick invented a game for him!
Initially, there is a rooted weighted tree with N vertices numbered . Nick guarantees that the tree is connected, and there is a unique path between any vertices! Also he gave us Q queries on it of following type:
All the indices in the queries are 1-based. Root of the tree is node 1.
But it turns out, Joseph has an exam tomorrow, and he doesn't have time for playing a game! And he asks your help!
Input format
The first line contains a single integer N denoting the number of vertices of the tree.
The next lines contain three integers and , denoting that there is an edge between vertices and with weight .
The next line contains a single integer Q denoting the number of queries.
The next Q lines contain two integers and , denoting the query described above.
Output format
Print the answer for each query. Note that if there is no such element, print 1.
Constraints
Subtasks