You are given a tree $T$ with $N$ nodes rooted at node 1. Each node has a value $A[i]$ associated with it.

You are required to perform $Q$ queries where each query is of type:

• $1 \ u \ x$: Increment the value associated with node $u$ by $x$.
• $2 \ p$: Find the shortest distance of any node from the root that has a value strictly greater than $p$. If no such node exists, then print -1.

Note: There exists at least 1 query of type 2.

Input format

• The first line contains an integer $T$ denoting the number of test cases.
• The first line of each test case contains an integer $N$.
• The second line of each test case contains $N$ space-separated integers denoting array $A$.
• Next $N - 1$ lines of each test case contain two space-separated integers denoting the edge.
• The next line of each test case contains an integer $Q$ denoting the number of queries.
• Next $Q$ lines of each test case contain queries.

Output format

For each test case, print the answer of queries of type $2$ in a new line.

Constraints

$1 \le T \le 10 \\ 2 \le N, Q \le 10^5 \\ 1 \le A[i] \le 10^6 \\ 1 \le x \le 10^6 \\ 1 \le p \le 10^{12}$