题目描述

某一天 gty 在与他的妹子玩游戏。妹子提出一个游戏，给定一棵有根树，每个节点有一些石子，每次可以将不多于 $L$ 的石子移动到父节点，询问将某个节点的子树中的石子移动到这个节点先手是否有必胜策略。gty 很快计算出了策略。但 gty 的妹子十分机智，她决定修改某个节点的石子或加入某个新节点。gty 不忍心打击妹子，所以他将这个问题交给了你。另外由于 gty 十分绅士，所以他将先手让给了妹子。

输入格式

第一行两个数字，$n$ 和 $L$，$n \le 5*10^4$，$L \le 10^9$。 第二行 $n$ 个数字，表示每个节点初始石子数。 接下来 $n-1$ 行，每行两个整数 $u$ 和 $v$，表示有一条从 $u$ 到 $v$ 的边。 接下来一行一个数 $m$，表示 $m$ 组操作。 接下来 $m$ 行，每行第一个数字表示操作类型

• 若为 $1$，后跟一个数字 $v$，表示询问在 $v$ 的子树中做游戏先手是否必胜。
• 若为 $2$，后跟两个数字 $x$， $y$ 表示将节点 $x$ 的石子数修改为 $y$。
• 若为 $3$，后跟三个数字 $u$， $v$， $x$，表示为 $u$ 节点添加一个儿子 $v$，初始石子数为 $x$。 在任意时刻，节点数不超过 $5*10^4$。

输出格式

对于每个询问，若先手必胜，输出"MeiZ"，否则输出"GTY"。

另，数据进行了强制在线处理，对于 $m$ 组操作，除了类型名以外，都需要异或之前回答为"MeiZ"的个数。

输入样例

2 1000
0 0
1 2
1
1 1

输出样例

GTY