Utkarsh was playing with a rooted tree of N nodes. Each node is numbered from 1 to N. Assume 1 as the root. Each node i has two integers Ai an Bi associated with it.
You need to answer Q queries of 2 types
1 v x : update Av = x
2 v : Tell how many nodes p are there such that p is an ancestor of v and Ap ≤ Bv
Note: P is an ancestor of v if P = v or P is ancestor of parent of v.
First line contains two integers N and Q.
Following N-1 lines contains pair of integers a b denoting there is an edge between a and b.
Next line contains N integers denoting the Array A
Next line contains N integers denoting the Array B
Next Q lines describe Q queries.
For each query of type 2 output the required answer.
1 ≤ N ≤ 6104
1 ≤ Q ≤ 8104
1 ≤ Ai, Bi, x ≤ 105