Chef is again playing a game with his best friend Garry. As usual, the rules of this game are extremely strange and uncommon.
First, they are given a stack of $N$ discs. Each disc has a distinct, non-negative integer written on it. The players exchange turns to make a move. Before the start of the game, they both agree upon a set of positive integers  $S$ of size $K$. It is guaranteed that S contains the integer $1$. In a move, a player can select any value $x$ from $S$ and pop exactly $x$ elements from the top of the stack. The game ends when there are no discs remaining. Chef goes first.
Scoring: For every disc a player pops, his score increases by $2^p$ where $p$ is the integer written on the disc. For example, if a player pops the discs, with integers $p_1, p_2, p_3, \dots, p_m$ written on it, during the entire course of the game, then his total score will be $2^{p_1} + 2^{p_2} + 2^{p_3} + \dots + 2^{p_m}$.
The player with higher score wins the game. Determine the winner if both the players play optimally, or if the game ends in a draw.

-----Input:-----
- First line contains $T$, the number of testcases. Then the testcases follow.
- The first line of each test case contains two space separated integers $N$ and $K$, denoting the size of the stack and the set S respectively.
- Next line contains $N$ space separated integers $A_i$ where $A_1$ is the topmost element, denoting the initial arrangement of the stack.
- The last line of each test case contains $K$ space separated integers each denoting $x_i$.

-----Output:-----
For each testcase, output "Chef" (without quotes) if Chef wins, "Garry" (without quotes) if Garry wins, otherwise "Draw" (without quotes) in a separate line.

-----Constraints-----
- $1 \leq T \leq 1000$
- $1 \leq N \leq 10^5$
- $1 \leq K \leq \min(100, N)$
- $0 \leq A_i \leq 10^9$
- $1 \leq x_i \leq N$
- $x_i \neq x_j$ for all $i \neq j$
- $A_i \neq A_j$ for all $i \neq j$
- Set $S$ contains integer $1$. 
- Sum of $N$ over all test cases does not exceed $10^5$.

-----Sample Input:-----
1
3 2
5 7 1
1 2

-----Sample Output:-----
Chef

-----Explanation:-----
Chef can select 2 from the set and draw the top two discs (with integers 5 and 7 written on it) from the stack. Garry cannot select 2 from the set as there is only 1 disc left in the stack. However, he can select 1 from the set and pop the last disc.
So, Chef's score = $2^5$ + $2^7$ = $160$

Garry's score = $2^1$ = $2$

Chef wins.

Source: codechef | Difficulty: VERY_HARD
Tags: Dynamic programming

Game theory


Solutions:
for t in range(int(input())):
	(n, k) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	brr = list(map(int, input().split()))
	arr.append(-1)
	arr = arr[::-1]
	x = arr.index(max(arr))
	dp = [0] * (n + 1)
	for i in range(1, n + 1, 1):
		for l in brr:
			if i - l < 0:
				continue
			elif i - l < x and x <= i:
				dp[i] = 1
			else:
				dp[i] |= not dp[i - l]
	if dp[n]:
		print('Chef')
	else:
		print('Garry')


for t in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	x = list(map(int, input().split()))
	wv = max(a)
	wvi = a.index(wv)
	dp = [False] * n
	dp[wvi] = True
	for i in range(wvi - 1, -1, -1):
		for j in x:
			if i + j > n:
				continue
			if i + j > wvi:
				dp[i] = True
			elif dp[i + j] == False:
				dp[i] = True
				break
	if dp[0]:
		print('Chef')
	else:
		print('Garry')


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	a = [-1] + a[::-1]
	mx = a.index(max(a))
	dp = [0] * (n + 1)
	for i in range(1, n + 1):
		for x in b:
			if i - x < 0:
				continue
			if i - x < mx <= i:
				dp[i] = 1
			else:
				dp[i] |= not dp[i - x]
	print('Chef' if dp[-1] else 'Garry')


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	s = list(map(int, input().split()))
	m = max(a)
	mi = a.index(m)
	dp = [0] * (n + 1)
	dp[mi] = 1
	for i in range(mi, -1, -1):
		for j in s:
			if i + j > n:
				continue
			if not dp[i + j]:
				dp[i] = 1
				break
	print('Chef' if dp[0] else 'Garry')


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	s = list(map(int, input().split()))
	m = -1
	p = -1
	for i in range(n):
		if a[i] > m:
			m = a[i]
			p = i + 1
	dp = [False] * (p + 1)
	s.sort()
	for i in range(1, p + 1):
		flag = 0
		for j in range(k):
			if s[j] <= i:
				if dp[i - s[j]] == False:
					dp[i] = True
					break
			elif s[j] - i <= n - p:
				dp[i] = True
				break
	if dp[-1] == False:
		print('Garry')
	else:
		print('Chef')