問題文
IOI2015举办地阿拉木图过去曾名为韦尔内伊。
显然,它在俄语中的意思是“忠诚”或“值得信赖”。 。
乔伊西诺姐姐听了这话,决定测试下属对自己的忠诚度。
首先,我们准备一棵树X和一棵树Y。每个顶点是0不同编号的点最多为(木の頂点数-1)和从“a”到“j”的一个小写字母。
执行以下操作。
执行Q次。
树 X 上直至
例如,'a'和'b', 树 Y 上直至'a'是'b'变为 答案是正确的,因为'b'是'a'变为。 给定了
例如,'a'和'b', 树 Y 上直至'a'是'b'变为 答案是正确的,因为'b'是'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在一行中给出。 下一个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为0时
后面是一个由空格分隔的整数。a,b和小写字母c,d按此顺序给出。 这是树的顶部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按此顺序给出。 这是(树的顶点a,b( 之间的路径上的顶点a,b包括),a按顺序排列的字符串)和(树Y的顶点 意思是回答字符串(从c,d( 之间的路径上的顶点c,d包括),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