给定一个包含 $n$ 个顶点的无向连通图。每个顶点 $v$ 都有一个模 $b_v$ 的计数器。该计数器的初始状态为 $a_v$。每次访问该顶点时，计数器加一（即 $a_v \leftarrow (a_v + 1) \pmod{b_v}$）。

你需要处理 $q$ 个以下两种类型的询问：

• “1 $s$”：假设你从顶点 $s$ 出发，请回答是否可能使所有 $v$ 的 $a_v = 0$。你可以沿着图 $G$ 进行任意行走，即你可以多次经过边和顶点。注意，从 $s$ 出发开始行走即视为访问了一次 $s$，即其计数器初始会增加一。
• “2 $v$ $x$”：更新 $a_v \leftarrow x$。

输入格式

第一行包含三个整数 $n, m, q$ ($1 \le n, q \le 5 \cdot 10^4, 0 \le m \le 10^5$)，分别表示顶点数、边数和询问数。

第二行包含 $n$ 个整数 $a_1, \dots, a_n$。

第三行包含 $n$ 个整数 $b_1, \dots, b_n$ ($0 \le a_v < b_v \le 10^9$)。

接下来的 $m$ 行包含图的边。每行包含两个整数 $u$ 和 $v$ ($1 \le u, v \le n, u \neq v$)，描述连接顶点 $u$ 和 $v$ 的边。给定的图是连通的。

最后有 $q$ 行描述询问。它们可以是上述两种格式之一：

• “1 $s$”：($1 \le s \le n$)
• “2 $v$ $x$”：($1 \le v \le n, 0 \le x < b_v$)

输出格式

对于每个类型 1 的询问，如果可能使所有 $v$ 的 $a_v = 0$，则输出 YES，否则输出 NO。

样例

输入 1

2 1 4
0 0
3 3
1 2
1 1
2 1 1
1 1
1 2

输出 1

YES
NO
YES

说明

在第一个询问中，我们从顶点 1 出发，计数器状态为 $[1, 0]$。 我们沿着路径 $1 \to 2 \to 1 \to 2 \to 1 \to 2$ 行走。 计数器状态变化如下：$[1, 0] \to [1, 1] \to [2, 1] \to [2, 2] \to [0, 2] \to [0, 0]$。