Задача №114758. Еще одна игра с фишками
Петя и Маша никак не могут решить, во что они будут играть. Петя предлагает шахматы, а Маша — в го. Чтобы решить спор, они решили сыграть в следующую игру.
Для этого они взяли поле размером \(n \times n\) с двумя фишками на нем. Верхняя левая клетка имеет координаты (\(0,0\)), а правая нижняя — (\(n - 1, n - 1\)). Игроки ходят по очереди. Начинает Петя. За один ход нужно переместить одну выбранную фишку вверх или влево, иными словами уменьшить ровно одну из ее координат на один. При этом перемещать фишку на занятую клетку или вне поля нельзя. Проигрывает тот, кто не может сделать хода.
Сыграв несколько раз они обнаружили, что такая игра не совсем честная, поэтому решили усложнить её и добавили новое правило: нельзя перемещать фишки на клетки, сумма координат которой меньше \(k\).
Ваша задача — узнать, кто выиграет, при оптимальной игре обоих игроков.
В первой строке заданы два целых положительных числа \(n\) и \(k\) (\(1 \leq k < n \leq 10^9\)) — размеры поля и ограничение на сумму координат клетки с фишкой.
Во второй строке задано одно целое число \(t\) (\(1 \leq t \leq 100\,000\)) — количество игр, для которых нужно узнать, кто выиграет.
Каждая из следующих \(t\) строк содержит по четыре целых числа \(x_1\), \(y_1\), \(x_2\), \(y_2\) (\(0 \leq x_1, y_1, x_2, y_2 < n\); \(k \leq x_1 + y_1\); \(k \leq x_2 + y_2\); \(x_1 \neq x_2\) или \(y_1 \neq y_2\)) — исходные координаты фишек.
Для каждой игры, если Петя выигрывает, в новой строке выведите « Petr », иначе выведите « Maria ».
В первой и третьей игре Петя не может сделать ход с самого начала и проигрывает
Во второй игре Петя может сделать единственный ход, после которого Маша ничего не сможет сделать и проиграет.
5 2 6 0 2 2 0 0 3 2 0 0 2 0 3 1 3 3 1 2 4 3 4 3 3 4 4
Maria Petr Maria Maria Petr Maria