I. Same Frequency Echo
time limit per test
6 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are given a weighted tree with $$$n$$$ vertices, rooted at vertex $$$1$$$.

Vertex $$$i$$$ has a frequency band $$$c_i$$$ and a transmission time $$$a_i$$$. Each frequency band $$$c$$$ has an importance value $$$w_c$$$.

For two distinct vertices $$$u,v$$$ using the same frequency band, define their synchronization cost as

$$$$$$ D(u,v)=|a_u-a_v|+\operatorname{dist}(u,v), $$$$$$

where $$$\operatorname{dist}(u,v)$$$ denotes the sum of edge weights on the simple path between vertices $$$u$$$ and $$$v$$$.

There are $$$q$$$ queries. Each query gives a vertex $$$x$$$ and a non-negative integer $$$K$$$.

We say that a frequency band $$$c$$$ produces an echo in the subtree of $$$x$$$ if and only if there exist two distinct vertices

$$$$$$ u,v\in\operatorname{subtree}(x) $$$$$$

such that

$$$$$$ c_u=c_v=c $$$$$$

and

$$$$$$ D(u,v)\le K. $$$$$$

Here, $$$\operatorname{subtree}(x)$$$ denotes the subtree rooted at $$$x$$$.

For each query, find the sum of the importance values of all frequency bands that produce an echo, i.e.

$$$$$$ \sum_{c=1}^{m} w_c \left[ \exists\,u\ne v\in\operatorname{subtree}(x),\ c_u=c_v=c,\ D(u,v)\le K \right]. $$$$$$

The square brackets denote the Iverson bracket: its value is $$$1$$$ if the condition inside is true, and $$$0$$$ otherwise.

Input

The first line contains three integers $$$n,m,q$$$ $$$(1\le n\le10^6,\ 1\le m\le10^5,\ 1\le q\le10^6)$$$, denoting the number of nodes, the number of frequency bands, and the number of queries, respectively.

The second line contains $$$m$$$ integers $$$w_1,w_2,\ldots,w_m$$$ $$$(0\le w_c\le10^9)$$$, where $$$w_c$$$ is the importance of frequency band $$$c$$$.

The third line contains $$$n$$$ integers $$$c_1,c_2,\ldots,c_n$$$ $$$(1\le c_i\le m)$$$, where $$$c_i$$$ is the frequency band used by node $$$i$$$.

The fourth line contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ $$$(0\le a_i\le10^9)$$$, where $$$a_i$$$ is the transmission time of node $$$i$$$.

Each of the next $$$n-1$$$ lines contains three integers $$$u,v,d$$$ $$$(1\le u,v\le n,\ 0\le d\le10^9)$$$, indicating that there is an undirected edge of weight $$$d$$$ between nodes $$$u$$$ and $$$v$$$.

Each of the next $$$q$$$ lines contains two integers $$$x,K$$$ $$$(1\le x\le n,\ 0\le K\le4\times10^{18})$$$, describing a query.

It is guaranteed that the input edges form a tree and that every answer fits in a signed 64-bit integer.

Output

For each query, output one integer — the sum of the importance values of all frequency bands that produce an echo in the subtree of vertex $$$x$$$.

It is guaranteed that every answer fits in a signed $$$64$$$-bit integer.

Example
Input
7 3 5
5 7 11
1 2 1 3 2 1 3
10 4 13 8 9 20 7
1 2 2
1 3 3
2 4 4
2 5 1
3 6 2
3 7 5
1 5
1 6
2 6
3 9
1 15
Output
0
12
7
5
23
Note

The synchronization costs between vertices using the same frequency band are as follows:

  • The nodes using frequency band $$$1$$$ are $$$1,3,6$$$: $$$D(1,3)=|10-13|+3=6$$$, $$$D(1,6)=|10-20|+5=15$$$, and $$$D(3,6)=|13-20|+2=9$$$;
  • The nodes using frequency band $$$2$$$ are $$$2,5$$$: $$$D(2,5)=|4-9|+1=6$$$;
  • The nodes using frequency band $$$3$$$ are $$$4,7$$$: $$$D(4,7)=|8-7|+14=15$$$.

Therefore:

  • In query $$$(1,5)$$$, no frequency band produces an echo, so the answer is $$$0$$$;
  • In query $$$(1,6)$$$, frequency bands $$$1,2$$$ produce echoes, so the answer is $$$5+7=12$$$;
  • In query $$$(2,6)$$$, only frequency band $$$2$$$ produces an echo, so the answer is $$$7$$$;
  • In query $$$(3,9)$$$, only frequency band $$$1$$$ produces an echo, so the answer is $$$5$$$;
  • In query $$$(1,15)$$$, all three frequency bands produce echoes, so the answer is $$$5+7+11=23$$$.