Description

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

Format

Input

第一行两个数字，n和L,n<=510^4,L<=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。 在任意时刻，节点数不超过510^4。

Output

对于每个询问，若先手必胜，输出"MeiZ",否则输出"GTY"。 另，数据进行了强制在线处理，对于m组操作，除了类型名以外，都需要异或之前回答为"MeiZ"的个数。

Samples

2 1000
0 0
1 2
1
1 1

GTY

Limitation