Logo Infinity Online Judge

InfOJ

时间限制:3 s 空间限制:512 MB

#4. 玩游戏

Statistics

题目描述

小 $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$。

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