P1839 Play with Power

Masha and Stas are playing a game. At the start of the game, a number $n$ is given, along with two positive integers $a, b$, which initially satisfy $a^b \le n$. Masha moves first. On each turn, a player must increase exactly one of $a$ or $b$ by $1$, but may not make $a^b > n$; otherwise that player loses. Now Masha wants to know, if both players play optimally, for the same $n$ and different $a, b$, who will win.

The first line contains a number $n$. The second line contains a number $t$, the number of test cases. The next $t$ lines each contain two numbers $a, b$, describing each test case.

Output $t$ lines, one for each test case: - If Masha wins, output `Masha`. - If Stas wins, output `Stas`. - If it is a draw, output `Missing`.

Constraints - For 30% of the testdata, $1 \le n \le 2 \times 10^3$. - For 100% of the testdata, $1 \le n \le 10^8$, $1 \le t \le 100$, $1 \le a, b, a^b \le n$. Translated by ChatGPT 5