题目描述

你想练习打字，但是你需要先生成一些供训练用的单词。

于是你拿出了 $n$ 个结点并将它们从 $1$ 至 $n$ 编号，还在每个结点上放置了一个字母。

现在你只需要将这些结点用 $n-1$ 条边连接起来，就可以任意选定一条链，然后将起点到终点路径上的所有结点上的字母依次排列，得到所需单词。

但是你是打字小白，不希望单词中大小写字母混杂，于是你希望在每次选定链之后，能知道这条链上的结点上的字母大小写是否均相同

具体的，现在有 $q$ 次操作：

• 1 u v：你下定决心将 $u,v$ 用一条边连接起来。
• 2 u v：询问从 $u$ 出发，到达 $v$ 的过程中，能否遇到与 $u$ 结点上的字母大小写不同的点，能则输出 $1$，反之输出 $0$。若 $u,v$ 不联通，则查询结果为 UKE（保证 $u\ne v$）。

保证所有 $1$ 操作后所有结点联通。

输入格式

第一行两个整数 $n,q$。

接下来一行一个字符串 $s$，$s_i$ 表示第 $i$ 个结点上的字母。

接下来 $q$ 行每行三个整数 $T,u,v$，表示一次操作。

输出格式

行数等于给出的操作 $2$ 的次数，每行均为 $0$ 或 $1$ 或 UKE，意义见上。

样例1

7 15
AaBeECc
2 2 3
1 1 2
2 2 3
1 1 3
2 2 3
1 2 4
1 2 5
1 3 6
1 3 7
2 1 5
2 2 4
2 1 6
2 1 7
2 4 7
2 5 6

UKE
UKE
1
1
0
0
1
1
1

所有 1 操作后结点连边状况如图所示（其中每个点字母前数字表示该点编号）：

样例2

见下发文件 ex_2.in/ex_2.out。

数据范围