Acer Rubrum

You are given a tree. Each of $N$ vertices has time, when it is active (from $t_{start}$ to $t_{end}$ inclusive). You are given $Q$ queries of two kinds:

$\texttt{1 t a b}$, asking how many active nodes are on path between $\texttt{a}$ and $\texttt{b}$ in time $\texttt{t}$.

$\texttt{2 t a}$, asking how many active nodes are in the subtree of $\texttt{a}$ in time $\texttt{t}$.

The tree will be rooted at node number 0.

Input

The first line of input will contain $N$ and $Q$ ($1 \le N, Q \le 2\times10^5$), the size of tree and number of queries.

The next line will contain $N$ numbers ($t_{i}-start$, the start time of each node).

The next line will contain $N$ numbers ($t_i-end$, end time of each node).

Both start times/end times will be in range from $0$ to $10^{6}$ (and start time will never be after end).

The next $N-1$ lines will contain two integers $a$ and $b$ ($0 \le a, b < N$), the edges of the tree.

The last $Q$ will be in form described above. Here both $a$, $b$ will be in range from 0 to $N-1$ and $t$ from range $0$ to $10^6$.

Output

For each query, output the number of active nodes in given time.

Sample

Input	Output
5 6 1 2 3 4 5 6 7 8 9 10 0 1 0 2 2 3 2 4 2 3 0 2 11 0 2 6 0 1 10 2 4 1 5 3 4 1 3 4 3	3 0 5 1 3 1