408765: GYM103295 M Ominous Chess

Professor Y and Magnato have entered a showdown with the fate of humanity decided by the winner. After exhausting themselves in a physical fight that ended evenly, they decide to settle the winner through $$$t$$$ games of their favorite childhood game. The game is a variant on simple chess designed as follows:

At the start of a single game, you use a board with $$$n$$$ rows and $$$m$$$ columns and each player has $$$n$$$ rook pieces. Then, for each of the $$$n$$$ rows, a third-party neutral robot (humans can't be trusted to be objective with their future on the line) will choose two distinct columns at random and place one of Professor's rooks in the position of the grid defined by that row and one of the chosen columns and one of Magnato's rooks in the position of the grid defined by that row and the other chosen column. After the game is set up, the players alternate taking turns and on a single turn, they can choose one of their rooks and move it left or right any number of spaces to another column in that row (and within the boundaries of the grid). Furthermore, one player may not move their rook past the other player's rook or into the column where the other player's rook is currently residing. When a player can no longer move any of their rooks, the other player will be considered the winner of that game.

Given that Professor Y will always go first and both players will use optimal strategies, output the winner of each of their $$$t$$$ games.

The first line of input will have a single integer $$$t$$$ representing the number of games played ($$$1 \leq t \leq 50$$$).

For each of the $$$t$$$ games, the first line will contain two space-separated integers $$$n$$$ and $$$m$$$ representing the number of rows and number of columns of the board ($$$1 \leq n \leq 2 \cdot 10^{5}$$$ and $$$1 \leq m \leq 10^{18}$$$). It will then be followed by $$$n$$$ lines with the $$$i$$$th line containing $$$2$$$ space-separated integers $$$c_i$$$ and $$$p_i$$$ representing the column that Professor's rook is located at and the column that Magnatoo's rook is located at in the $$$i$$$th row ($$$1 \leq c_i, p_i \leq m$$$ and $$$c_i \neq p_i$$$).

It is guaranteed that the sum of the number of rows over all the test cases will be less than or equal to $$$2 \cdot 10^{5}$$$.

For each of the $$$t$$$ games, output Professor Y or Magnato depending on who wins that game if both players use optimal strategies.

2
2 5
1 3
2 4
3 10
2 6
10 5
3 9

Magnato
Professor Y