问题描述

曾经举办 IOI2015 的阿拉木图（Almaty）在过去以 Верный（Verny）之名存在。
听说这个名字在俄语中表示"忠诚"或"可信赖"。
joisino姐姐听说后，决定测试下手下对她的忠诚度。

首先，准备了两棵树X和树Y。每个顶点从0到(树的顶点数-1)编号，每个顶点上标有小写字母'a'到'j'中的一个。

进行以下操作Q次。

1. 在树X上的路径A到B（包括A和B）上交换两个字母。
   例如，交换'a'和'b'，路径上的'a'变为'b'，'b'变为'a'。
2. 在树Y上的路径A到B（包括A和B）上交换两个字母。
   例如，交换'a'和'b'，路径上的'a'变为'b'，'b'变为'a'。
3. 判断树X上路径A到B（包括A和B）上的字母序列和树Y上路径C到D（包括C和D）上的字母序列是否完全相同。
4. 恢复到执行a次查询之前的状态。
   其中(本次查询之前已经执行过的查询数)≧a≧0。

限制条件

$1$≦$Q$≦$10^5$
$1$≦$(树X的顶点数)$≦$10^5$
$1$≦$(树Y的顶点数)$≦$10^5$

得分

• 此问题没有部分分。只有在通过所有测试用例时才能得到100分。

输入

从标准输入中按以下格式提供输入。

关于树X的数据 关于树Y的数据 Q Query1 Query2 . . . QueryQ

首先，提供有关树X的数据。
然后，提供有关树Y的数据。
然后，提供一个整数Q表示查询次数。
接下来的Q行表示每个查询。
每棵树的数据以以下格式给出。

N s $a_1$ $b_1$ $a_2$ $b_2$ . . . $a_N-1$ $b_N-1$

数据的第一行为整数N，表示树的顶点数。
接下来的一行是长度为N的字符串s，表示树上各个顶点上的字母。第i+1个字符（$0$≦$i$＜$N$）代表树的第i个顶点上的字母。
接下来的N-1行表示树的边。
$a_i$和$b_i$表示顶点$a_i$和顶点$b_i$（$0$＜$i$≦$N-1$）之间有一条边。

每个查询由单独的一行表示。首先，给出查询类型t的整数t。

• 当t为0时，以空格分隔后面的整数a、b和小写字母c、d。这表示在树X的顶点a和b之间的路径上，对于每个顶点（包括a和b），如果字母c被写在上面，则替换为字母d；如果字母d被写在上面，则替换为字母c。
• 当t为1时，以空格分隔后面的整数a、b和小写字母c、d。这表示在树Y的顶点a和b之间的路径上，对于每个顶点（包括a和b），如果字母c被写在上面，则替换为字母d；如果字母d被写在上面，则替换为字母c。
• 当t为2时，以空格分隔后面的整数a、b和小写字母c、d。这表示判断（按照树X上从a开始连续编号的顶点上写的字母序列）和（按照树Y上从c开始连续编号的顶点上写的字母序列）是否完全相同。
• 当t为3时，以空格分隔后面的整数a。这表示恢复树X和树Y到执行a次查询之前的状态。

输出

对于每个查询，当t为2时，如果字符串匹配，则输出"YES"，否则输出"NO"。
请确保整个输出结束时有一个换行符。

输入示例$1$

4
ckdl
0 2
0 1
1 3
4
lckd
2 1
1 3
2 0
4
2 2 3 3 0
2 2 3 0 3
2 3 2 0 3
2 3 2 3 0

输出示例$1$

YES
NO
YES
NO