# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

# Freezing Trees

By souravvv · Limits 1s, 512 MB

We heard you like trees. But this problem has no relation to trees being frozen. :D

You are given a rooted tree with $n$ nodes. The node with index $1$ is the root. Although the tree is not frozen, the tree is colorful. Each of the nodes is colored with a color identified by an integer from $1$ to $m$.

You will also be given an array of integers of $m$ length. Let's call this array $A$.

There are two types of operations. They are:

Operation 1:
$1 ~i ~x$.
Set the value of $A[i]$ to $x$. It means perform the assignment $A[i] = x$.

Operation 2:
$2 ~v ~l ~r$.
Consider the subtree rooted at node $v$. Lets count occurrences of all the $m$ colors in the subtree. We will denote this using $F_v$. It means the $i^{th}$ color appears $F_v [i]$ times in the subtree rooted at node $v$.
You have to tell if the following statement is true:
Is $F_v [i] = A[i]$ for all $i$ such that $l ≤ i ≤ r$ ?
In other words, does the following equation
$F_v [l, l + 1, l + 2, ... r] = A[l, l + 1, l + 2, ... r]$
hold?
You have to print "YES" if the equation is true, otherwise print "NO" (without the quotes).

## Input

First line will contain three integers $n, ~m, ~q$. They represent the number of nodes, the length of the array $A$ and the number of operations respectively.

The next line contains $n$ integers, $c_1, ~c_2, ~c_3 ... ~c_n; ~c_i$ is the color of the $i^{th}$ node.

The next line contains $m$ integers, $a_1, ~a_2, ~a_3 ... ~a_m$;
the $A$ array.

Next $n-1$ lines contain the $u ~v$ pairs. They represent the edges in the tree.

Next $q$ line will describe the operation.

For type - 1 operation the input is:
$1 ~i ~x$.
For type - 2 operation input format is:
$2 ~v ~l ~r$.

Constraints:
$1 ≤ m ≤ 5 × 10^4$.
$1 ≤ n ≤ 5 × 10^4$.
$1 ≤ q ≤ 5 × 10^4$.
$1 ≤ c_i ≤ m$.
$1 ≤ a_i ≤ 10^9$.
$1 ≤ u, ~v ≤ n$.

For type 1 operation:
$1 ≤ i ≤ m$.
$0 ≤ x ≤ 10^9$.

For type 2 operation:
$1 ≤ v ≤ n$.
$1 ≤ l ≤ r ≤ m$.

## Output

For each of the type-2 operations, print "YES" or "NO" without the quotes.

## Sample

InputOutput
7 4 4
1 1 2 4 4 3 3
2 1 2 3
1 2
2 4
2 5
3 6
3 7
1 3
2 3 2 3
2 3 1 3
1 1 0
2 3 1 3

YES
NO
YES


### Statistics

81% Solution Ratio

tmwilliamlin168Earliest, Dec '19

mahdi.hasnatFastest, 0.1s

ShahinLightest, 10 MB

tmwilliamlin168Shortest, 1767B