Read problems statements in mandarin chinese, russian and vietnamese as well. 

One free afternoon, Chef found an old board game in his kitchen. He decided to invite his friends Miron and Slava to come play it with him.  

The board is a rectangular grid of size  2 × N. Initially, Miron and Slava each put their chips at a location (x_{1},y_{1} ) and (x_{2},y_{2} ) respectively. The game then proceeds as follows : 

Each player moves their chip in turns.
In each turn, a player can move his chip to an adjacent cell that has not been visited by the other player before.
Two cells are adjacent if they share a side
A player can also skip his turn
The cell that is initially occupied by a particular player's chip is considered visited by him

The outcome of the game is decided as follows : 

If a player manages to visit strictly more than half the total number of cells (i.e. visited at least N+1 cells), he immediately wins and the other player loses.
if the game continued for more than 10^{100} turns without any player declared a winner yet then it becomes a draw.

Given that both players move optimally and Miron starts first, can you help Chef predict the winner of the game?

------ Input ------ 

The first line contains a single integer T, the number of test cases. Each test case is described by a single line containing five space-separated integers N, x_{1}, y_{1}, x_{2}, y_{2}. 

------ Output ------ 

For each test case, output a single line with string Miron, Slava or Draw, denoting the answer to the problem.

------ Constraints ------ 

$1 ≤ T ≤  10^{5} $
$1 ≤ N ≤  10^{18} $
$1 ≤ x_{1}, x_{2}  ≤  2$
$1 ≤ y_{1}, y_{2}  ≤  N$
$Cells (x_{1}, y_{1}) and (x_{2}, y_{2}) are different.$

----- Sample Input 1 ------ 
4
5 1 1 2 3
1 1 1 2 1
3 1 1 2 3
4 1 2 1 4
----- Sample Output 1 ------ 
Slava
Draw
Draw
Miron

Difficulty: VERY_HARD
Tags: Game theory

Ad-hoc

Starter code:

Solutions:
def list_input():
	return list(map(int, input().split()))

def map_input():
	return map(int, input().split())

def map_string():
	return input().split()
for _ in range(int(input())):
	(n, x1, y1, x2, y2) = map_input()
	c1 = abs((n + 1) / 2 - y1)
	c2 = abs((n + 1) / 2 - y2)
	if x1 == x2:
		if c1 < c2:
			print('Miron')
		if c1 == c2:
			if n % 2 == 1:
				print('Miron')
			else:
				print('Draw')
		if c1 > c2:
			if c1 - 1 > c2:
				print('Slava')
			elif n % 2 == 1 or abs(y1 - y2) == 1:
				print('Slava')
			else:
				print('Draw')
	else:
		if c1 < c2:
			if c1 + 1 == c2 and n % 2 == 0 and (abs(y1 - y2) != 1):
				print('Draw')
			else:
				print('Miron')
		if c1 == c2:
			print('Draw')
		if c1 > c2:
			if c1 - 1 > c2 and (not (n % 2 == 0 and c1 - 2 == c2 and (abs(y1 - y2) != 2))):
				print('Slava')
			else:
				print('Draw')


for _ in range(int(input())):
	(n, x1, y1, x2, y2) = map(int, input().split())
	d = lambda x, y: abs(x - y)
	if n % 2 == 0:
		m1 = n // 2 if d(n // 2, y2) < d(1 + n // 2, y2) else 1 + n // 2
		m2 = n // 2 if d(n // 2, y1) < d(1 + n // 2, y1) else 1 + n // 2
	else:
		m1 = (n + 1) // 2
		m2 = (n + 1) // 2
	winner = 0
	if x1 == x2:
		if d(m1, y1) <= d(m1, y2):
			winner = 1
		elif d(m2, y2) < d(m2, y1):
			winner = 2
	elif d(m1, y1) < d(m1, y2):
		winner = 1
	elif d(m2, y2) + 1 < d(m2, y1):
		winner = 2
	print(['Draw', 'Miron', 'Slava'][winner])


for _ in range(int(input())):
	(n, x1, y1, x2, y2) = map(int, input().split())
	if n % 2 == 0:
		(p1, p2) = (n // 2, 1 + n // 2)
		m1 = p1 if abs(p1 - y2) < abs(p2 - y2) else p2
		m2 = p1 if abs(p1 - y1) < abs(p2 - y1) else p2
	else:
		m1 = m2 = (n + 1) // 2
	winner = 0
	if x1 == x2:
		if abs(m1 - y1) <= abs(m1 - y2):
			winner = 1
		elif abs(m2 - y2) < abs(m2 - y1):
			winner = 2
	elif abs(m1 - y1) < abs(m1 - y2):
		winner = 1
	elif abs(m2 - y2) + 1 < abs(m2 - y1):
		winner = 2
	print(['Draw', 'Miron', 'Slava'][winner])


for t in range(int(input())):
	(N, x1, y1, x2, y2) = map(int, input().split())
	dist = lambda x, y: abs(x - y)
	if N % 2 == 0:
		(p1, p2) = (N // 2, N // 2 + 1)
		w1 = p1 if dist(y2, p1) < dist(y2, p2) else p2
		w2 = p1 if dist(y1, p1) < dist(y1, p2) else p2
	else:
		w1 = w2 = (N + 1) // 2
	res = 0
	if dist(w1, y1) < dist(w1, y2) + (x1 == x2):
		res = 1
	elif dist(w2, y2) + (x1 != x2) < dist(w2, y1):
		res = 2
	print(['Draw', 'Miron', 'Slava'][res])