Given a tree with $n$ nodes, each node has a value of $1$ or $-1$. For $q$ queries $(u, v)$, count the number of nodes $t$ on the simple path from $u$ to $v$ such that the sum of node values on the simple path from $u$ to $t$ is positive.
### Input
- The first line contains two integers $n$ and $q$.
- The second line contains $n$ integers representing the values of the nodes from $1$ to $n$.
- The next $n - 1$ lines each contain two integers $u, v$ representing an edge of the tree.
- The next $q$ lines each contain two integers $u, v$ representing a query.
### Output
- For each query, print a single integer as the answer.
### Constraints
- $1 \le n,q \le 10^5$.
- $1 \le u,v \le n$.
### Example
Input:
```
8 5
-1 1 1 1 -1 1 1 -1
1 5
5 6
3 6
4 5
4 7
4 8
1 2
3 8
2 2
1 7
2 7
6 4
```
Output:
```
5
1
0
2
2
```
