题目描述

那维莱特给了你一棵 $n$ 个点的树和一个初始为空的可重路径集合 $P$ ，同时你需要支持 $m$ 次操作。三种操作被描述如下：

• $\text{1 s t}$ 表示在 $P$ 中加入一条路径 $(s,t)$。
• $\text{2 s t}$ 表示在 $P$ 中删除任意一条路径 $(s,t)$，保证删除时 $P$ 至少存在一条 $(s,t)$。
• $\text{3 d}$ 表示询问 $\max_{i=1}^n\sum_{(s,t)\in P}\max_{j\in (s,t)}[dist(i,j)\le d]=|P|$ 是否成立，保证询问时有 $|P|>0$。你需要回答 Y 如果等式成立，否则回答 N。

为了避免这个集合被窃听，输入的数字是经过加密的。 具体的，对于输入的 $s,t,d$ 都需要 $xor$ 上 $(k\times$ 你已回答的 Y 的数量 $)$ 。

输入格式

第一行输入 $2$ 个正整数 $n,m,k$ 。

接下来 $n-1$ 行，每行输入 $2$ 个正整数 $u,v$ ，表示一条树边。

接下来 $m$ 行，每行 $2$ 或 $3$ 个数，表示一次操作。

输出格式

对于每个 $3$ 操作，输出一个字符 Y 或 N 表示等式成立与否。

样例 #1

样例输入 #1

10 10 0
1 2
2 3
3 4
4 7
7 10
2 5
5 6
6 8
8 9
1 9 9
1 8 4
1 8 5
3 0
3 1
3 2
2 9 9
3 2
2 8 4
3 1

样例输出 #1

NYYYY

提示

对于所有数据, 解密后有 $1\le s,t\le n,0\le d<n,k\in{0,1}$ 。