Как мы все знаем, Макс лучше всех играет в компьютерные игры. Ее друзья настолько ей завидуют, что придумали игру в реальном мире, чтобы показать, что она не во всех играх лучшая. Игра проходит на ориентированном ациклическом графе с n вершинами и m ребрами. На каждом ребре написан символ — строчная латинская буква.

Играют Макс и Лукас. Первой ходит Макс, потом ходит Лукас, затем снова Макс и так далее. У каждого игрока есть камешек, изначально расположенный в некоторой вершине. Каждый игрок в свой ход должен передвинуть свой камешек вдоль одного ребра (игрок может передвинуть камешек из вершины v в вершину u, если есть ребро из вершины v в u). Если игрок передвигает камешек из вершины v в вершину u, то «символом» этого раунда называется символ, написанный на ребре из v в u. Есть одно дополнительное правило: ASCII код символа раунда i должен быть не меньше, чем ASCII код символа раунда i - 1 (для i > 1). Раунды нумеруются для всех игроков вместе, иными словами, Макс ходит в нечетных раундах, в Лукас — в четных. Игрок, который не может сделать ход, проигрывает. Камешки могут находиться в одной вершине в одно и то же время.

Поскольку игра занимает некоторое время, а Лукас и Макс должны найти Дарта, у них нет времени для игр. Они спрашивают у вас, кто выиграет, если оба будут играть оптимально?

Вам необходимо определить победителя в игре для всех возможных начальных позиций камешков.