题解

本题是 $2021$ 年 $CCPC$ 湘潭邀请赛的 $G$ 题，实在不会写的同学可以网上搜索题解。另外，由于本题数据造的都是 $10^5$ 的情况，所以下载数据找 bug 也不见得有效。实在找不出错误的可以去跟其他同学的正确代码进行小数据对拍找问题，这个可能更直接有效，对拍方法自行百度。数据在 data.zip 里，有需要的可以下载。

Background

在聪明的你解决了“$MZ$ 的签到题”之后，$MZ$ 提出，既然 $KK$ 这么喜欢 $9$，那就玩个跟 $9$ 有关的游戏吧。在 $MZ$ 说完游戏的规则后，聪明的你一眼就看出了谁会赢谁会输。

Description

这个游戏是这样的：给定一个集合，集合里面包含 $n$ 个正整数，每次操作可以选择集合中的任意一个数 $x$,将其变成 $x - 9$ 或 $x - 99$ 或……即变成 $x - (10^k-1)$（其中 $k$ 为任意正整数，且操作后的数必须大于 $0$，即集合中的数必须一直大于 $0$）。$KK$ 和 $MZ$ 轮流操作且 $KK$ 先操作，谁先不能操作谁就输。

Format

Input

• 第一行给出一个整数 $n（1 \leq n \leq 10^5）$，表示集合中有 $n$ 个数。
• 第二行给出 $n$ 个互不相同的正整数且每个正整数保证在 $int$ 范围内。

Output

输出“$KK$”或“$MZ$”，如果 $KK$ 获胜输出“$KK$”，$MZ$ 获胜输出“$MZ$”。

Samples

4
1 2 10 11

MZ

TIPS.

• 集合具有互异性