题目背景

有两棵树小 A 和小 B，小 A 发育不良，小 B 发育的很好。

为了追上小 B 的发育，小 A 开始了魔改之路。

题目描述

小 A 有 $n$ 个节点，小 B 有 $m$ 个节点。每一个节点都有一种颜色。小 A 和小 B 都以一号节点为根。

为了追赶小 B，小 A 进行了 $q$ 次发育操作。

对于每一次操作先读入一个整数 $P$ 表示操作类型。

若 $P=1$，表示一次询问，那么接下来读入四个整数 $P_1,P_2,P_3,P_4$。

我们令 $lt$ 为上一次询问的答案，那么令 $D_1=P_3\oplus lt,D_2=P_4\oplus lt$，$lt$ 初始时为 $0$。

小 A 希望你能回答出小 A 的 $P_1$ 子树内离 $P_1$ 距离不超过 $D_1$ 和小 B 的 $P_2$ 子树内离 $P_2$ 距离不超过 $D_2$ 的节点中一共有多少种不同的颜色。

若 $P=2$，表示小 A 对自己进行了一次魔改发育，接下来读入两个整数 $S_1,S_2$ 表示小 A 将自己的 $S_1$ 节点的颜色魔改为了 $S_2$。

输入格式

第一行读入三个整数 $n,m,q$。

接下来读入 $n-1$ 行，每行两个正整数 $u,v$，表示有一条边连接小 A 的 $u$ 和 $v$。

然后读入 $m-1$ 行，每行两个正整数 $u,v$，表示有一条边连接小 B 的 $u$ 和 $v$。

紧接着读入 $n$ 行，每行一个正整数 $v_1$，第 $i$ 行表示小 A 的第 $i$ 号节点的颜色。

还需要读入 $m$ 行，每行一个正整数 $v_2$，第 $i$ 行表示小 B 的第 $i$ 号节点的颜色。

最后再读入 $q$ 个询问，询问格式见题目描述。

输出格式

对于每一个询问单独输出一行，每行一个整数表示答案。

5 5 5
4 3
1 3
5 4
2 3
4 2
5 4
3 2
1 3
4
1
3
5
4
1
5
1
2
3
1 2 1 1 2
1 1 5 2 2
1 4 1 2 3
1 5 4 2 2
1 4 1 1 3

2
2
2
2
3

数据范围与提示

对于全部数据，保证：

• $n\leq 20$，$m\leq 2\times 10^5$，$q\leq 10^6$
• $P_1\leq n$，$P_2\leq m$，$1\leq P_3,P_4\leq 2\times 10^5$