The 1000th Gem Collection Contest has begun!

Audiences have grown tired of gem collection problems occurring on linear sequences, so this year's contest features a significant innovation: participants must now collect gems on an unrooted tree with $n$ nodes.

There are $m$ gems on this tree. Each gem $i$ ($1 \le i \le m$) has a corresponding pair of parameters $(a_i, d_i)$, meaning that if a participant reaches node $a_i$ via a simple path containing no more than $d_i$ edges, they may choose to collect this gem immediately (or choose not to).

Correspondingly, the contestants are enthusiastic, with a total of $q$ participants signed up. For each participant, they are assigned a starting node $x$ and a range of gems $[l, r]$. They must complete the following task: starting from node $x$, repeatedly choose an adjacent edge to move to, and collect gems $l$ through $r$ in order, i.e., collect all $r - l + 1$ gems in the sequence $l, l + 1, \dots, r$.

Since every participant encountered some route planning difficulties during the contest, the organizers have asked you to calculate the minimum total number of edges each participant needs to traverse to complete their collection task.

Implementation Details

You do not need to, and should not, implement the main function.

You must ensure that your submitted program includes the header file gems.h by adding the following code at the beginning of your program:

#include "gems.h"

You must implement the following two functions in your submitted source file gems.cpp:

void gems(int c, int n, int m, std::vector<int> u,
std::vector<int> v, std::vector<int> a, std::vector<int> d);

• $c, n, m$ represent the test case ID, the number of nodes in the tree, and the number of gems, respectively. $c = 0$ indicates that the test case is a sample.
• For $0 \le i < n - 1$, $u_i, v_i$ represent an edge in the tree.
• For $0 \le i < m$, $a_i, d_i$ represent the two parameters of the $(i+1)$-th gem.
• For each test case, this function will be called exactly once by the interactor, before any calls to the query function.

long long query(int x, int l, int r);

• $x, l, r$ represent the participant's starting node and the range of gems to collect, respectively.
• This function must return the minimum total number of edges the participant needs to traverse to collect gems $l$ through $r$ in order, starting from node $x$.
• For each test case, this function will be called exactly $q$ times by the interactor.

Testing Your Program

You can compile your program in the problem directory using the following command:

g++ grader.cpp gems.cpp -o gems -O2 -std=c++14 -static

For the compiled executable: The executable will read data from standard input in the following format: The first line contains three non-negative integers $c, n, m$. The $1 + i$ ($1 \le i \le n - 1$) line contains two positive integers $u_i, v_i$. The $n + 1$ line contains $m$ positive integers $a_1, a_2, \dots, a_m$. The $n + 2$ line contains $m$ non-negative integers $d_1, d_2, \dots, d_m$. The $n + 3$ line contains a positive integer $q$. The $n + 3 + i$ ($1 \le i \le q$) line contains three positive integers $x, l, r$. The executable will output data to standard output in the following format: * Output $q$ lines, each containing one non-negative integer representing the return value of the query function.

Examples

Input 1

0 5 4
1 2
1 3
2 4
2 5
4 1 5 3
1 0 1 2
2
2 2 4
4 1 2

Output 1

2
2

Note

For the first participant, they need to start from node 2 and collect gems 2 through 4. One possible collection path is $2 \to 1 \to 2 \to 2$, traversing a total of 2 edges.

For the second participant, they need to start from node 4 and collect gems 1 through 2. One possible collection path is $4 \to 4 \to 1$, traversing a total of 2 edges.

Constraints

For all test data: $2 \le n \le 3 \times 10^5$, $1 \le m \le 3 \times 10^5$; For all $1 \le i \le n - 1$, $1 \le u_i, v_i \le n$, and all edges form a tree; For all $1 \le i \le m$, $1 \le a_i \le n$ and $0 \le d_i \le n$; $1 \le q \le 5 \times 10^5$; * $1 \le x \le n$, $1 \le l \le r \le m$.

Special Property A: The tree is a chain, i.e., no node has a degree greater than 2. Special Property B: For all $1 \le i \le m$, $d_i \ge n/2$. Special Property C: $l = 1$.