You are given a tree of N nodes. The tree is rooted at vertex 1. Every node of the tree is assigned a value. Lets denote the value of the $i^{th}$ node by $f_i$. We call a node $good$ if the sum of values of all nodes in its subtree is strictly greater than X.

You have to perform Q update operations on this tree. In each update you have to increase the value of some node. After each update print the number of good nodes.

Input Format

The first line of input contains three integers N, Q and X.

Each of the next $N-1$ lines contain two integers $u_i$ and $v_i$ - indices of vertices, connected by the i-th edge. It's guaranteed that given graph is a tree.

The next line contains N integers, the $i^{th}$ denoting $f_i$.

The next Q lines contain two integers $d_i$ and $a_i$ denoting that $a_i$ is added to the node $d_i$.

Output Format

Output Q integers - the number of good nodes after the each update.

Constraints

$1 \leq N, Q \leq 10^{5}$
$1 \leq u_i, v_i, d_i \leq N$
$1 \leq X, a_i, f_i \leq 10^{9}$