题目描述

小 $A$ 得了忧郁综合症，小 $B$ 正在想办法开导她。

机智的小 $B$ 决定陪着小 $A$ 玩游戏，他从魔法的世界里变出一张无向联通图，每条边上都有边权。小 $B$ 定义一条路径的权值为所有经过边中的最大权值，小$A$则定义两点的最短路径为所有路径中权值最小的路径权。

每次小 $A$ 先选出两个点 $m1,m2$，然后小B选出两个点 $b1,b2$，计算出它们的最短路径 $m,b$，然后小 $B$ 会拿出两堆灵魂宝石，一堆有 $m$ 个，另一堆有 $b$ 个。然后小 $A$ 先从一堆中选出若干个灵魂宝石拿走，接下来小 $B$ 重复同样的操作，如此反复，直到取走最后一颗灵魂宝石，然后取走最后一颗宝石的人获胜。

小 $B$ 认为这样游戏太简单，于是他会不定期向这张图上加上一些边，以增大游戏难度。

小 $A$ 具有预知未来的能力，她看到了自己和小 $B$ 在未来游戏中的选择，以及小$B$增加的边。现在对于每次游戏，小 $A$ 想知道自己是否存在必胜的方法。但是预知未来已经消耗了她太多精力，出于疲惫她只好找到了你。

输入格式

第一行两个数 $N$ 和 $M$，表示这张无向图初始的点数与边数；

接下来 $M$ 行，每行三个数$u,v,q$，表示点 $u$ 和点 $v$ 之间存在一条权值为 $q$ 的边；

接下来一行一个数$Q$，表示操作总数；

接下来 $Q$ 行，表示操作，每行格式为下面两条中的一条：

• $\text{add}~u~v~q：$ 表示在 $u$ 与 $v$ 之间加上一条边权为 $q$ 的边；

• $\text{game}~m1~m2~b1~b2：$表示一次游戏，其中小A的选择点 $m1,m2$，小$B$的选择点 $b1,b2$。

数据保证 $1≤u,v,m1,m2,b1,b2≤n，1≤q，m1≠m2$ 且 $b1≠b2$

输出格式

对于每个 $game$ 输出一行，若小 $A$ 存在必胜策略，则输出 madoka，否则输出 Baozika，以回车结尾

样例

输入

5 6
1 2 3
2 3 6
4 2 4
5 3 5
3 4 5
5 1 5
4
game 1 3 4 3
game 1 5 2 4
add 2 5 4
game 1 5 3 4

输出

Baozika
madoka
madoka

样例解释

数据范围

$n\leq 50000$，$m\leq 150000$，$q\leq 50000$。

题目中的所有数均为正整数。