Yaroslav, Andrey and Roman can play cubes for hours and hours. But the game is for three, so when Roman doesn't show up, Yaroslav and Andrey play another game. 

Roman leaves a word for each of them. Each word consists of 2·n binary characters "0" or "1". After that the players start moving in turns. Yaroslav moves first. During a move, a player must choose an integer from 1 to 2·n, which hasn't been chosen by anybody up to that moment. Then the player takes a piece of paper and writes out the corresponding character from his string. 

Let's represent Yaroslav's word as s = s_1s_2... s_2n. Similarly, let's represent Andrey's word as t = t_1t_2... t_2n. Then, if Yaroslav choose number k during his move, then he is going to write out character s_{k} on the piece of paper. Similarly, if Andrey choose number r during his move, then he is going to write out character t_{r} on the piece of paper.

The game finishes when no player can make a move. After the game is over, Yaroslav makes some integer from the characters written on his piece of paper (Yaroslav can arrange these characters as he wants). Andrey does the same. The resulting numbers can contain leading zeroes. The person with the largest number wins. If the numbers are equal, the game ends with a draw.

You are given two strings s and t. Determine the outcome of the game provided that Yaroslav and Andrey play optimally well.


-----Input-----

The first line contains integer n (1 ≤ n ≤ 10^6). The second line contains string s — Yaroslav's word. The third line contains string t — Andrey's word.

It is guaranteed that both words consist of 2·n characters "0" and "1".


-----Output-----

Print "First", if both players play optimally well and Yaroslav wins. If Andrey wins, print "Second" and if the game ends with a draw, print "Draw". Print the words without the quotes.


-----Examples-----
Input
2
0111
0001

Output
First

Input
3
110110
001001

Output
First

Input
3
111000
000111

Output
Draw

Input
4
01010110
00101101

Output
First

Input
4
01100000
10010011

Output
Second

Difficulty: MEDIUM
Tags: Game theory

Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase
from functools import cmp_to_key
from heapq import *
from math import gcd, factorial, floor, ceil, sqrt
from copy import deepcopy
from collections import deque
from bisect import bisect_left as bl
from bisect import bisect_right as br
from bisect import bisect
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
from types import GeneratorType

def iterative(f, stack=[]):

	def wrapped_func(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		to = f(*args, **kwargs)
		while True:
			if type(to) is GeneratorType:
				stack.append(to)
				to = next(to)
				continue
			stack.pop()
			if not stack:
				break
			to = stack[-1].send(to)
		return to
	return wrapped_func

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def testcase(t):
	for pp in range(t):
		solve(pp)

def google(p):
	print('Case #' + str(p) + ': ', end='')

def lcm(a, b):
	return a * b // gcd(a, b)

def power(x, y, p):
	y %= p - 1
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def ncr(n, r):
	return factorial(n) // (factorial(r) * factorial(max(n - r, 1)))

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True
inf = pow(10, 20)
mod = 10 ** 9 + 7

def solve(case):
	n = int(inp())
	a = inp()
	b = inp()
	chck = [0] * 4
	for i in range(2 * n):
		chck[int(a[i]) + 2 * int(b[i])] += 1
	f = 0
	s = 0
	for i in range(n):
		if chck[3] > 0:
			f += 1
			chck[3] -= 1
		elif chck[1] > 0:
			f += 1
			chck[1] -= 1
		elif chck[2] > 0:
			chck[2] -= 1
		else:
			chck[0] -= 1
		if chck[3] > 0:
			s += 1
			chck[3] -= 1
		elif chck[2] > 0:
			s += 1
			chck[2] -= 1
		elif chck[1] > 0:
			chck[1] -= 1
		else:
			chck[0] -= 1
	print('Draw' if f == s else 'First' if f > s else 'Second')
testcase(1)


n = input()
s = input()
t = input()
fir = 0
sec = 0
same = 0
for (l, r) in zip(s, t):
	if l == '1':
		fir += 1
		if r == '1':
			same += 1
			sec += 1
	elif r == '1':
		sec += 1
if same % 2 != 0:
	fir += 1
if fir > sec:
	print('First')
elif sec > fir + 1:
	print('Second')
else:
	print('Draw')


import sys
import math
n = int(input())
st1 = input()
st2 = input()
k = 0
res = 0
for i in range(2 * n):
	if st1[i] == '1' and st2[i] == '1':
		k += 1
	elif st1[i] == '1':
		res -= 1
	elif st2[i] == '1':
		res += 1
res1 = int(k / 2) + k % 2
res2 = k - res1
v = 0
if k % 2 == 0:
	v = -1
if res < 0:
	b = math.fabs(res)
	res1 += int(b / 2) + res % 2
elif res > 0:
	res += v
	res2 += int(res / 2) + res % 2
if res1 > res2:
	print('First')
elif res1 < res2:
	print('Second')
else:
	print('Draw')


n = int(input())
s = input()
t = input()
s_1 = 0
t_1 = 0
for i in range(2 * n):
	if s[i] == '1':
		s_1 += 1
	if t[i] == '1':
		t_1 += 1
first = 0
second = 0
r = 0
for i in range(2 * n):
	if s[i] == '1' and t[i] == '0':
		first += 1
	elif s[i] == '0' and t[i] == '1':
		second += 1
	elif s[i] == '1' and t[i] == '1':
		r += 1
if r % 2 == 1:
	first += 1
if s_1 > t_1:
	print('First')
elif first == second or first == second - 1:
	print('Draw')
elif first > second:
	print('First')
elif first < second:
	print('Second')


ii = lambda : int(input())
kk = lambda : map(int, input().split())
ll = lambda : list(kk())
(n, a1, a2) = (ii(), input(), input())
locs = [0] * 4
for i in range(2 * n):
	locs[int(a1[i]) + 2 * int(a2[i])] += 1
rm = min(locs[1], locs[2])
locs[1] -= rm
locs[2] -= rm
locs[3] = locs[3] & 1
if locs[1]:
	print('First')
elif locs[3]:
	if locs[2] == 0:
		print('First')
	elif locs[2] < 3:
		print('Draw')
	else:
		print('Second')
elif locs[2] < 2:
	print('Draw')
else:
	print('Second')


import io, os
input = io.StringIO(os.read(0, os.fstat(0).st_size).decode()).readline
ii = lambda : int(input())
kk = lambda : map(int, input().split())
ll = lambda : list(kk())
(n, a1, a2) = (ii(), input(), input())
locs = [0] * 4
for i in range(2 * n):
	locs[int(a1[i]) + 2 * int(a2[i])] += 1
rm = min(locs[1], locs[2])
locs[1] -= rm
locs[2] -= rm
locs[3] = locs[3] & 1
if locs[1]:
	print('First')
elif locs[3]:
	if locs[2] == 0:
		print('First')
	elif locs[2] < 3:
		print('Draw')
	else:
		print('Second')
elif locs[2] < 2:
	print('Draw')
else:
	print('Second')


n = int(input())
(a, b) = (input(), input())
t = {i + j: 0 for i in '01' for j in '01'}
for i in range(2 * n):
	t[a[i] + b[i]] += 1
d = t['11'] & 1
d += (t['10'] - t['01'] + 1 - d) // 2
if d > 0:
	d = 1
elif d < 0:
	d = 2
print(['Draw', 'First', 'Second'][d])


from sys import stdin
n = int(stdin.readline())
a = stdin.readline()
b = stdin.readline()
cnt0 = 0
cnt1 = 0
cnt2 = 0
for i in range(n * 2):
	if a[i] == '0':
		if b[i] == '0':
			cnt0 += 1
		else:
			cnt1 += 1
	elif b[i] == '0':
		cnt2 += 1
cnt = [cnt0, cnt1, cnt2, 2 * n - cnt0 - cnt1 - cnt2]
dif = 0
iter1 = iter((3, 2, 1, 0))
iter2 = iter((3, 1, 2, 0))
cur1 = next(iter1)
cur2 = next(iter2)
left = n
while left > 0:
	while cnt[cur1] == 0:
		cur1 = next(iter1)
	dif += cur1 >> 1
	cnt[cur1] -= 1
	while cnt[cur2] == 0:
		cur2 = next(iter2)
	dif -= cur2 & 1
	cnt[cur2] -= 1
	jump = min(cnt[cur1], cnt[cur2]) if cur1 != cur2 else cnt[cur1] // 2
	dif += ((cur1 >> 1) - (cur2 & 1)) * jump
	cnt[cur1] -= jump
	cnt[cur2] -= jump
	left -= jump + 1
if dif > 0:
	print('First')
elif dif < 0:
	print('Second')
else:
	print('Draw')


n = int(input())
s = list(input())
l = list(input())
a = len([_ for _ in zip(s, l) if _ == ('1', '1')])
b = len([_ for _ in zip(s, l) if _ == ('1', '0')])
c = len([_ for _ in zip(s, l) if _ == ('0', '1')])
f = b + (a + 1) // 2
s = c + a // 2
if f > s:
	print('First')
elif f + 1 < s:
	print('Second')
else:
	print('Draw')


from sys import stdin
from math import ceil, floor
n = int(input())
s = stdin.readline()
t = stdin.readline()
first = 0
second = 0
draw = 0
for i in range(2 * n):
	if s[i] == '1' and t[i] == '1':
		draw += 1
	elif s[i] == '1':
		first += 1
	elif t[i] == '1':
		second += 1
if first > second:
	if draw % 2 == 1:
		first -= ceil((first - second) / 2)
	else:
		first -= first - second - ceil((first - second) / 2)
elif second > first:
	if draw % 2 == 1:
		second -= second - first - ceil((second - first) / 2)
	else:
		second -= ceil((second - first) / 2)
first += ceil(draw / 2.0)
second += draw - ceil(draw / 2.0)
if first > second:
	print('First')
elif second > first:
	print('Second')
else:
	print('Draw')


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from collections import Counter
import heapq
from collections import Counter
n = int(input())
s = input()
t = input()
both = 0
only_a = 0
only_b = 0
for i in range(2 * n):
	if s[i] == '1' and t[i] == '1':
		both += 1
	else:
		if s[i] == '1':
			only_a += 1
		if t[i] == '1':
			only_b += 1
a = 0
b = 0
for i in range(n):
	if both:
		a += 1
		both -= 1
	elif only_a:
		only_a -= 1
		a += 1
	elif only_b:
		only_b -= 1
	if both:
		both -= 1
		b += 1
	elif only_b:
		b += 1
		only_b -= 1
	elif only_a:
		only_a -= 1
if a > b:
	print('First')
elif a == b:
	print('Draw')
else:
	print('Second')


from sys import stdin

def readLine():
	return stdin.readline()

def main():
	while True:
		n = int(readLine())
		a = readLine()
		b = readLine()
		both = 0
		onlyA = 0
		onlyB = 0
		for i in range(2 * n):
			if a[i] == '1' and b[i] == '1':
				both += 1
			elif a[i] == '1':
				onlyA += 1
			elif b[i] == '1':
				onlyB += 1
		A = 0
		B = 0
		for i in range(n):
			if both:
				A += 1
				both -= 1
			elif onlyA:
				A += 1
				onlyA -= 1
			elif onlyB:
				onlyB -= 1
			if both:
				B += 1
				both -= 1
			elif onlyB:
				B += 1
				onlyB -= 1
			elif onlyA:
				onlyA -= 1
		if A > B:
			print('First')
		elif A < B:
			print('Second')
		else:
			print('Draw')
		break
main()


import sys
import bisect
try:
	fin = open('in')
except:
	fin = sys.stdin
input = lambda : fin.readline().strip()
n = int(input())
a = list(map(int, input()))
b = list(map(int, input()))
r = [[0, 0], [0, 0]]
for i in range(2 * n):
	r[a[i]][b[i]] += 1
t = [0] * 2
for i in range(2 * n):
	j = i % 2
	if r[1][1] > 0:
		r[1][1] -= 1
		t[j] += [1, 1][j]
	elif r[0][1] > 0:
		r[0][1] -= 1
		t[j] += [0, 1][j]
	elif r[1][0] > 0:
		r[1][0] -= 1
		t[j] += [1, 0][j]
	else:
		r[0][0] -= 1
		t[j] += [0, 0][j]
(x, y) = t
if x > y:
	print('First')
elif x < y:
	print('Second')
else:
	print('Draw')