問題文

IOI2015の開催されたアルマトイは昔、Верный(ヴェールヌイ)という名前であった。
どうやらロシア語で「忠実な」とか「信頼できる」とかいった意味があるらしい。。
joisinoお姉ちゃんは、これを聞いて、部下が自分にいかに忠実かを試そうとした。

まず、木Xと木Yを用意した。各頂点は$0$から$(木の頂点数-1)$までの名前がついており、'a'から'j'までのどれかの小文字のアルファベットが一つ書かれている。

以下の操作を$Q$回行う。

• $A$から$B$までの木X上のパス($A$,$B$含む)上にあるアルファベット2つを入れ替える。
  　　例えば、$'a'$と$'b'$を入れ替えると、パス上の$'a'$は$'b'$となり、$'b'$は$'a'$となる。
• $A$から$B$までの木Y上のパス($A$,$B$含む)上にあるアルファベット2つを入れ替える。
  　　例えば、$'a'$と$'b'$を入れ替えると、パス上の$'a'$は$'b'$となり、$'b'$は$'a'$となる。
• 木Xの$A$から$B$までのパス($A$,$B$含む)上にあるアルファベットを並べた文字列と、木Yの$C$から$D$までのパス($C$,$D$含む)上にあるアルファベットを並べた文字列が完全に一致するか、そうでないかを答える。
• $a$回のクエリを実行した直後の状態に戻す。
  　 ただし、(このクエリを処理する前に処理したクエリの数)≧$a$≧$0$とする。

制限

$1$≦$Q$≦$10^5$
$1$≦$(木Xの頂点数)$≦$10^5$
$1$≦$(木Yの頂点数)$≦$10^5$

配点

• この問題に部分点は存在しない。すべてのテストケースに正解すると$100$点が得られる。

入力

入力は以下の形式で標準入力から与えられる。

木Xについてのデータ 木Yについてのデータ $Q$ $クエリ1$ $クエリ2$ . . . $クエリQ$ 　始めに、木Xについてのデータが与えられる。
　その次に、木Yについてのデータが与えられる。
　その次に、クエリ数を指す整数$Q$が1行で与えられる。 　その次の$Q$行は各クエリを意味する。
　各木のデータは、以下の形式で与えられる。
$N$ $s$ $a_1$ $b_1$ $a_2$ $b_2$ . . . $a_N-1$ $b_N-1$ 　データ内の1行目に、木の頂点数$N$が整数で与えられる。
　次の1行に、長さ$N$の文字列sが与えられる。この文字列の$i+1$文字目($0$≦$i$＜$N$)は、木の頂点iに書かれている小文字を指す。
　次のN-1行の各行は、木の辺を意味する。
　$a_i$と$b_i$は、頂点$a_i$と頂点$b_i$($0$＜$i$≦$N-1$)の間に辺があることを意味する。

各クエリは1行から与えられる。 　まず、初めにクエリの種類を指す整数$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$,$b$間のパス上の頂点($a$,$b$含む)に書かれている文字を、$a$から順に並べたときの文字列)と(木Yの頂点$c$,$d$間のパス上の頂点($c$,$d$含む)に書かれている文字を、$c$から順に並べたときの文字列)が一致するかしないかを答えることを意味する。 　 　* $t$が3の時
　空白区切りでこの後に整数$a$が与えられる。 　これは、木Xと木Yを、$a$回クエリを処理した直後の状況に戻すことを意味する。

出力

それぞれのクエリにおいて$t$が2のとき、文字列が一致する場合$"YES"$、一致しない場合$"NO"$を1行に出力せよ。
　なお入力全体の最後には改行を忘れないこと。

入力例$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