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.

Difficulty: interview

Starter code:

Solutions:
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 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))
 # print(arr)
 dp=[0]*(n+1)
 for i in range(1,n+1,1):
  for l in brr:
   # print(i-l)
   if i-l<0:
    continue
   elif i-l<x and x<=i:
    dp[i]=1
   else:
    dp[i]|=not dp[i-l]
 # print(dp)
 if dp[n]:
  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') 

# cook your dish here
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
 # print(wvi)
 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:
    # print(i, j)
    dp[i] = True
    break
 # print(dp)
    
 if dp[0]:
  print("Chef")
 else:
  print("Garry")

for _ in range(int(input())):
 n,k=list(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()
 #print(s)
 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
   else:
    if s[j]-i<=n-p:
     dp[i]=True
     break
 if dp[-1]==False:
  print('Garry')
 else:
  print('Chef')


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')