Harryxun/stf_run huggingface dataset:
# -*- coding: utf-8 -*-

import sys
from collections import defaultdict
from bisect import bisect_left

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, K = MAP()
A = LIST()

# 部分和DPを変形させて、その値になるのに使われた値の集合を持っておく
dp = defaultdict(set)
dp[0].add(0)
for i in range(N):
    for j in range(K-1, -1, -1):
        if len(dp[j]):
            dp[j+A[i]] |= dp[j]
            dp[j+A[i]].add(A[i])

raise Exception

# 和がK未満の集合はこの後のチェックで使わないので削る
dp = sorted(dp.items())
keys, sets = zip(*dp)
idx = bisect_left(keys, K)
keys = keys[idx:]
sets = sets[idx:]

ans = 0
for i in range(N):
    for k, s in zip(keys, sets):
        # A[i]減らしたらK未満になる状況で、一度でもA[i]が使われていれば必要
        if k-A[i] < K and A[i] in s:
            break
    else:
        # 該当するどの集合でも、一度も使われていなければ不要
        ans += 1
print(ans)


### FIXED CODE ###

# -*- coding: utf-8 -*-

import sys
import numpy as np

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

def bisearch_min(mn, mx, func):
    """ 条件を満たす最小値を見つける二分探索 """

    ok = mx
    ng = mn
    while ng+1 < ok:
        mid = (ok+ng) // 2
        if func(mid):
            # 下を探しに行く
            ok = mid
        else:
            # 上を探しに行く
            ng = mid
    return ok

N, K = MAP()
A = LIST()

def check(omit):
    # 部分和DP
    dp = np.zeros((N+1, K), dtype=np.bool)
    dp[0,0] = 1
    for i in range(N):
        # まとめて遷移
        dp[i+1] |= dp[i]
        if i != omit and A[i] < K:
            dp[i+1,A[i]:] |= dp[i,:K-A[i]]
    # 今回の値A[omit]を足してKに到達できるような部分和があれば、これは必要
    for j in range(max(0, K-A[omit]), K):
        if dp[N,j]:
            return True
    # なければ不要
    return False

A.sort()
print(bisearch_min(-1, N, check))
n = int(input())
result = 1
list=[]
list = list(map(int,input().split()))
if 0 in list:
  print(0)
else:
  for i in list:
  result *= list[i]
  if result > 10 ** 18:
  print(-1)
  break

print(result)

### FIXED CODE ###

n =int(input())
ls =[]
ls =list(map(int,input().split()))
if 0 in ls:
	print(0)
else:
	ans = 1
	for a in ls:
		ans *= a
		if ans > 10 ** 18:
			ans = -1;
			break
		
	print(ans)
count = 0
a, b, c = map(int, raw_input().split())
while 1:
    if c%a == 0:
    count += 1
    if a == b:
        break
    a += 1
print count

### FIXED CODE ###

count = 0
a, b, c = map(int, raw_input().split())
while 1:
    if c%a == 0:
        count += 1
    if a == b:
        break
    a += 1
print count
from math import gcd
K=int(input())+1
sum=0
for a in range(1,K):
    for b in range(1,K):
        for c in range(1,K):
            gcd1 = int(gcd(a,b))
            gcd2 = int(gcd(b,c))
            gcd = int(gcd(gcd1,gcd2))

            sum = sum+gcd
print(sum)

### FIXED CODE ###

from math import gcd

K = int(input())
out = 0
Count = [0]*K
gcds = [[0]*K for i in range(K)]

for i in range (1,K+1):
    for j in range(1,+K+1):
        value = gcd(i,j)
        gcds[i-1][j-1]=value
        Count[value-1]+=1

for i in range(1,K+1):
    for j in range(1,K+1):
        out +=gcds[i-1][j-1]*Count[j-1] #値*回数
        
print(out)
def sol():
    n,m=map(int,input().split())
    w={}
    p,q=set(),set()
    for i in range(m):
        l,r,d=[int(i) for i in input().split()]
        if l in w:
            w[l].add((r,d))
        else:
            w[l]={(r,d)}
        p.add(l)
        q.add(r)
    s=p-q
    for i in s:
        k={j for j in w[i]}
        g=set()
        cnt=0
        while len(k):
            x=k.pop()
            cnt+=1
            if cnt==121212:
                print(p[10])
                exit()
                
            if x[0] not in w:
                g.add(x)
            else:
                for j in w[x[0]]:
                    k.add((j[0],j[1]+x[1]))
        y=set()
        for j in g:
            if j[0] in y or j[0]==i:
                print("No")
                exit()
            else:
                y.add(j[0]) 
    print("Yes" if len(s) or m==0 else "No")

if __name__=="__main__":
    sol()

### FIXED CODE ###

def sol():
    n,m=map(int,input().split())
    t,w={},{}
    p,q=set(),set()
    for i in range(m):
        l,r,d=[int(i) for i in input().split()]
        if l in w: w[l].add((r,d))
        else: w[l]={(r,d)}
        p.add(l)
        q.add(r)
    s=p-q
    chk=set()
    if len(s)==0:
        print(["No","Yes"][m==0])
        exit()
    for i in s:
        chk.add((i,0))
        while len(chk):
            x=chk.pop()
            if x[0] in w:
                for j in w[x[0]]:
                    if (i,j[0]) in t and t[(i,j[0])]!=t[(i,x[0])]+j[1]:
                        print("No")
                        exit()
                    elif (i,j[0]) not in t:
                        #t[(i,j[0])]=t[(i,x[0])]+j[1]
                        t[(i,j[0])]=x[1]+j[1]
                        chk.add((j[0],x[1]+j[1]))
    print("Yes")

if __name__=="__main__":
    sol()
import heapq

if __name__ == "__main__":
    K,T = map(int, input().split())
    data = list(map(int, input().split()))
    cake = []
    for i,x in enumerate(data):
        cake.append([x, i])
    heapq._heapify_max(cake)
    while (len(cake) > 1):
        heapq._heapify_max(cake)
        p = heapq.heappop(cake)
        q = heapq.heappop(cake)
        # print (p,q)
        p[0] -= 1
        q[0] -= 1
        if p[0] > 0:
            heapq.heappush(cake, p)
        if q[0] > 0:
            heapq.heappush(cake, q)
    result = 0
    if len(cake) > 0:
        t = heapq.heappop(cake)
        result = t[0]
    print (max(0, result - 1))


### FIXED CODE ###

import heapq

if __name__ == "__main__":
    K,T = map(int, input().split())
    data = list(map(int, input().split()))
    cake = []
    for i,x in enumerate(data):
        cake.append([x, i])
    heapq._heapify_max(cake)
    while (len(cake) > 1):
        heapq._heapify_max(cake)
        p = heapq.heappop(cake)
        q = heapq.heappop(cake)
        # print (p,q)
        p[0] -= 1
        q[0] -= 1
        if p[0] > 0:
            heapq.heappush(cake, p)
        if q[0] > 0:
            heapq.heappush(cake, q)
    result = 0
    if len(cake) > 0:
        t = heapq.heappop(cake)
        result = t[0]
    print (max(0, result - 1))
from collections import defaultdict as dd

N, M = map(int, input().split())
MOD = 10 ** 9 + 7
# a1 x a2 x .. x aN = M となる数列{ai}が何通りあるか
# まずは素因数分解
def make_prime_dict(x):
    primes = dd(int)
    check = 2
    while True:
        if x % check == 0:
            primes[check] += 1
            x = x // check
        else:
            check += 1
            if check > x:
                break
    return dict(primes)

primes = make_prime_dict(M)

Q = max(primes.values())
fact = [1]
fact_inv = [1]
for i in range(Q+N):
    new_fact = fact[-1] * (i+1) % MOD
    fact.append(new_fact)
    fact_inv.append(pow(new_fact, MOD - 2, MOD))

def mod_comb(n, r, mod):
    return fact[n] * fact_inv[n - r] % mod * fact_inv[r] % mod

res = 1
for q in primes.values():
    res *= mod_comb(q + N - 1, q, MOD) % MOD

print(res)

### FIXED CODE ###

from collections import defaultdict as dd

N, M = map(int, input().split())
MOD = 10 ** 9 + 7
# a1 x a2 x .. x aN = M となる数列{ai}が何通りあるか
# まずは素因数分解
def make_prime_dict(x):
    primes = dd(int)
    check = 2
    while True:
        if x % check == 0:
            primes[check] += 1
            x = x // check
        else:
            check += 1
            if check > x:
                break
    return dict(primes)

primes = make_prime_dict(M)
if len(primes) == 0:
    print(1)
    exit()
Q = max(primes.values())
fact = [1]
fact_inv = [1]
for i in range(Q+N):
    new_fact = fact[-1] * (i+1) % MOD
    fact.append(new_fact)
    fact_inv.append(pow(new_fact, MOD - 2, MOD))

def mod_comb(n, r, mod):
    return fact[n] * fact_inv[n - r] % mod * fact_inv[r] % mod

res = 1
for q in primes.values():
    res *= mod_comb(q + N - 1, q, MOD)
    res %= MOD

print(res)
import math

A,B,C,D = map(int, input().split())

c = int(B/C) - int((A-1)/C)
d = int(B/D) - int((A-1)/D)

CD = C * D / math.gcd(C, D)
cd = int(B/CD) - int((A-1)/CD)

ans = B - (A-1) - (c + d - cd)
print(ans)

### FIXED CODE ###

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

A,B,C,D = map(int, input().split())

c = B//C - (A-1)//C
d = B//D - (A-1)//D

CD = C * D // gcd(C, D)
cd = B//CD - (A-1)//CD

ans = B - (A-1) - (c + d - cd)
print(ans)
S = Sa
card = S.pop(0)
while True:
    if card == 'a':
        S = Sa
    if card == 'b':
        S = Sb
    if card == 'c':
        S = Sc
    try:
        card = S.pop(0)
    except:
        print(card.upper())
        break

### FIXED CODE ###

Sa = list(input())
Sb = list(input())
Sc = list(input())
card = Sa.pop(0)
while True:
    if card == 'a':
        S = Sa
    if card == 'b':
        S = Sb
    if card == 'c':
        S = Sc
    try:
        card = S.pop(0)
    except:
        print(card.upper())
        break
n = int(input()) % 10
if n in {2, 4, 5, 7, 9}:
    print('hon')
elif n in {0, 1, 6, 8}:
    print('pon')
else
    print('bon')


### FIXED CODE ###

n = int(input()) % 10
if n in {2, 4, 5, 7, 9}:
    print('hon')
elif n in {0, 1, 6, 8}:
    print('pon')
else:
    print('bon')
d,n = map(int, input().split())
if d == 0:
    l = [i for i in range(0,100)]
elif d == 1:
    l = [i for i in range(0, 10000, 100)]
else:
    l = [i for i in range(0, 1000000, 10000)]
print(l[n])


### FIXED CODE ###

d,n = map(int, input().split())
r = 100 ** d
l = [i for i in range(0, r*100, r)]
if n == 100:
    print(100 ** (d + 1) + 100 ** d)
else:
    print(l[n])
# input
N, M = int(input())
X = list(map(int, input().split()))

X.sort()
K = [
    abs(X[n] - X[n - 1])
    for i in range(1, N)
]

print(sum(K[:M - (N - 1)]))


### FIXED CODE ###

# input
N, M = map(int, input().split())
X = list(map(int, input().split()))

X.sort()
K = sorted(
    [
        abs(X[i] - X[i - 1])
        for i in range(1, M)
    ],
    reverse=True
)

print(sum(K[N - 1:]))
H, W, M = map(int, input().split())
h = [0 for i in range(H)]
w = [0 for i in range(W)]
dp = [[0 for i in range(W)] for j in range(H)]

for i in range(M):
    hh, ww = map(int, input().split())
    h[hh - 1] += 1
    w[ww - 1] += 1
    dp[hh - 1][ww - 1] += 1
    

hhh = max(h)
www = max(w)

print(hhh + www - (1-check))


### FIXED CODE ###

H, W, M = map(int, input().split())
h = [0 for i in range(H)]
w = [0 for i in range(W)]
DP = set()
for i in range(M):
    hh, ww = map(int, input().split())
    h[hh - 1] += 1
    w[ww - 1] += 1
    DP.add((hh - 1, ww - 1))

hhh = max(h)
www = max(w)
hhhh = [i for i, x in enumerate(h) if x == hhh]
wwww = [i for i, x in enumerate(w) if x == www]
check = 0

for i in hhhh:
    for j in wwww:
        if (i, j) not in DP:
            print(hhh + www)
            exit()
print(hhh + www - 1)
x, y = map(int,input().split()))
  
if b%a == 0:
  print(a+b)
else:
  print(b-a)

### FIXED CODE ###

a, b = map(int,input().split())
  
if b%a == 0:
  print(a+b)
else:
  print(b-a)
n,q=map(int,raw_input().split())
c=map(int,raw_input().split())
p=[0]*(max(c)+1)
for i in c:
	p[i]=1

for k in range(q):
	m=int(raw_input())n,q=map(int,raw_input().split())
c=map(int,raw_input().split())
p=[0]*(max(c)+1)
for i in c:
	p[i]=1

for k in range(q):
	m=int(raw_input())
	flag=0
	for i in range(m-1,0,-1):
		for pi in p[i::m]:
			if pi:
				print i
				flag=1
				break
		if flag: break
	else:
		print 0
	flag=0
	for i in range(m-1,0,-1):
		for pi in p[i::m]:
			if pi:
				print i
				flag=1
				break
		if flag: break

### FIXED CODE ###

N,Q=map(int,raw_input().split())
c=map(int,raw_input().split())

mxc=max(c)
p=[0]*(mxc+1)
for i in c:
    p[i]=1
    
l=[0]*(mxc+1)
num=0
for i in range(mxc+1):
    l[i]=num
    if p[i]:
        num=i
        
for i in range(Q):
    q=int(raw_input())
    sp=mxc
    ans=0
    while 1:
        r=sp%q
        ans=max(ans,r)
        if sp-r<=0:break
        sp=l[sp-r]
    print ans
N, M = map(int, input().split())
a = [int(input()) for i in range(M)]

def d(n: int) -> int:
    if n == N or n == N-1:
        return 1
    
    if not(n+1 in a) and not(n+2 in a):
        return d(n+1) + d(n+2)
    elif n+1 in a and not (n+2 in a):
        return d(n+2)
    else:
        return d(n+1)

flag = 0
for i in range(M-1):
    if a[i] == a[i+1]:
        flag = 1
        break
        
if flag == 1:
    print(0)
else:
    print(d(0) % 1000000007)

### FIXED CODE ###

N, M = map(int, input().split())
a = [False] * (N+1)
for i in range(M):
    a[int(input())] = True
 
memo = [None] * (N+1)
memo[0] = 1 #0番目にたどり着く方法は1通りと定義する。
memo[1] = 1 if not a[1] else 0
 
for i in range(2, N+1):
    memo[i] = memo[i-1] + memo[i-2] if not a[i] else 0
 
print(memo[N] % 1000000007)
import copy

K,N = map(int, input().split())
An = list(map(int, input().split()))
ans = [max(An) - min(An)]
for i in range(len(An)/2,len(An)):
    A_list = copy.copy(An)
    A_list[i] = A_list[i]-K
    ans.append(max(A_list) - min(A_list))
print(min(ans))

### FIXED CODE ###

import numpy as np

K,N = map(int, input().split())
An = list(map(int, input().split()))
arr = np.array(An)
arr = np.diff(arr)
ans = list(arr)
ans.append(K-An[-1]+An[0])
# print(ans)
ans.remove(max(ans))
print(sum(ans))
a, b = map(int, input().split())
if a % 3 == 0 or b % 3 == 0 or (a+b) % 3 == 0:
  print("Possible")
else:
  Print("Impossible")

### FIXED CODE ###

a, b = map(int, input().split())
if a % 3 == 0 or b % 3 == 0 or (a+b) % 3 == 0:
  print("Possible")
else:
  print("Impossible")
a, b = map(int, input().split())
count = 1
x = a
print(x)
while x * 2 <= b:
    x = x * 2
    print(x)
    count += 1
print(count)

### FIXED CODE ###

a, b, c, d = map(int, input().split())
#a, b, c, d = 3,4,5,2
if a + b > c + d:
    result = "Left"
elif a + b == c + d:
    result = "Balanced"
elif a + b < c + d:
    result = "Right"
print(result)
N=int(input())
A=list(map(int,input().split()))
B=A[0]
def gcd(a,b):
  while b:
    a,b=b,a%b
  return a
for i in range(1,N):
  B=gcd(B,A[i])
prnt(B)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
B=A[0]
def gcd(a,b):
  while b:
    a,b=b,a%b
  return a
for i in range(1,N):
  B=gcd(B,A[i])
print(B)
import sys
    sys.setrecursionlimit(10**6)
    n, q = map(int, input().split())
    node = [0] * n
    par = [-1] * n
    for _ in range(n-1):
        a, b = map(int, input().split())
        par[b-1] = a-1
    for _ in range(q):
        p, x = map(int, input().split())
        node[p-1]+=x
    def dfs(i, count=0):
        count+=node[i]
        if par[i] == -1:
            return count
        else:
            return dfs(par[i], count)
    print(' '.join([str(dfs(i)) for i in range(n)]))

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
n, q = map(int, input().split())
node = [0] * n
to = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = map(int, input().split())
    to[b-1].append(a-1)
    to[a-1].append(b-1)
for _ in range(q):
    p, x = map(int, input().split())
    node[p-1]+=x

def dfs(i, source, count=0):
    node[i]+=count
    for next_node in to[i]:
        if next_node == source: continue 
        dfs(next_node, i, node[i])
dfs(0, -1, 0)

print(' '.join(list(map(str, node))))
a = list(map(int, input.split()))
res = 0

num = a.pop(0) * 2

for i in range(num):
    if (a[i] == 'BTC'):
        b = a[i-1] * 380000
        res += b
    elif (a[i] == 'JPY'):
        res += a[i-1]
    else:
        pass

print(res) 

### FIXED CODE ###

a = int(input())

b = []

for i in range(a):
    b.append(input().split())

res = 0

for i in b:
    if (i[1] == 'BTC'):
        res += float(i[0])*380000
    else:
        res += int(i[0])

print(res)
x, N = map(int, input().split(" "))
data = list(map(int, input().split(" ")))
point = 0
i = 0
while(1):
    if x not in data:
        print(x)
        break
    elif x+i not in data:
        print(x+i)
        break
    elif x+(-1*i) not in data:
        print(x+(-1*i))
        break
    else:
        i=i-1

### FIXED CODE ###

x, N = map(int, input().split(" "))
try:
  data = list(map(int, input().split(" ")))
except:
  data = []
point = 0
i = 0
while(1):
    if x not in data:
        print(x)
        break
    elif x+i not in data:
        print(x+i)
        break
    elif x+(-1*i) not in data:
        print(x+(-1*i))
        break
    else:
        i=i-1
n = int(input())
ans = []
for i in range(1,int(n**0.5)):
    if n%i==0:
        ans.append(i-1+((n//i)-1))
print(min(ans))


### FIXED CODE ###

n = int(input())
ans = []
for i in range(1,int(n**0.5)+1):
    if n%i==0:
        ans.append(i-1+((n//i)-1))
print(min(ans))
import math
from functools import reduce
n=int(input())
T=[int(input())for _ in range(n)]
def lcm(a, b):
  return (a * b) // math.gcd(a, b)

def lcm_list(num):
  return reduce(lcm, num, 1)

print(lcm_list(T))

### FIXED CODE ###

n=int(input())
def gcd(a, b):
  while b:
    a, b = b, a % b
  return a

def lcm(a, b):
  return (a * b) // gcd(a, b)
num = 1
for i in range(n):
  num = lcm(num, int(input()))

print(num)
import math


def lcm(x,y):
    return x*y/math.gcd(x,y)

a,b=map(int, input().split(' '))

print(int(lcm(a,b)))

### FIXED CODE ###

import fractions
def lcm(x,y):
    return x*y/fractions.gcd(x,y)

a,b=map(int, input().split(' '))

print(int(lcm(a,b)))
a, b = map(int, input().split(' ')
if a % 2 == 0 or b % 2 == 0:
    print('Even')
else:
    print("Odd")

### FIXED CODE ###

a, b = map(int, input().split(' '))
if a % 2 == 0 or b % 2 == 0:
    print("Even")
else:
    print("Odd")
if(modR <= modL):
    modMin = 0
else:
    modMin = 2018

for i in range(modL,modR):
    for j in range(i+1,modR+1):
        modIJ = (i*j)%2019
        # print(i)
        # print(j)
        # print('----')
        #print(modMin)
        #print(modIJ)
        #print('---')
        if modIJ < modMin:
            modMin = modIJ
print(modMin)

### FIXED CODE ###

l,r = map(int, input().split())
waruL = l // 2019
waruR = r // 2019
if waruL < waruR :
    modMin = 0
else:
    modMin = 2018
    modL = l%2019
    modR = r%2019

    for i in range(modL,modR):
        for j in range(i+1,modR+1):
            modIJ = (i*j)%2019

            if modIJ < modMin:
                modMin = modIJ
print(modMin)
n=int(input())
edge=[]
G=[[] for _ in range(n+1)]
for _ in range(n-1):
    x,y=map(int,input().split())
    edge.append([x,y])
    G[x].append(_)
    G[y].append(_)
k=0
root=0
for i in range(1,n+1):
    if k<len(G[i]):
        root=i
        k=len(G[i])
co=[1 for i in range(n+1)]
def dfs(node,pa=-1):
    #print(node)
    tmp=0
    if pa>=0:
        tmp=co[pa]
    for v in G[node]:
        if pa not in edge[v]:
            #print("??",v)
            tmp+=1
            co[v]=tmp%k+1
            if node==edge[v][0]:
                dfs(edge[v][1],node)
            else:
                dfs(edge[v][0],node)

dfs(root)
print(k)
for i in range(n-1):
    print(co[i])


### FIXED CODE ###

import sys
sys.setrecursionlimit(100010)
n=int(input())
edge=[]
G=[[] for _ in range(n+1)]
for _ in range(n-1):
    x,y=map(int,input().split())
    edge.append([x,y])
    G[x].append(_)
    G[y].append(_)
k=0
root=0
for i in range(1,n+1):
    if k<len(G[i]):
        root=i
        k=len(G[i])
co=[1 for i in range(n+1)]
vis=[False for i in range(n+1)]
def dfs(node,lastco=-1):
    tmp=lastco
    for v in G[node]:
        if not vis[v]:
            tmp+=1
            co[v]=tmp%k
            vis[v]=True
            if node==edge[v][0]:
                dfs(edge[v][1],co[v])
            else:
                dfs(edge[v][0],co[v])

dfs(root)
print(k)
for i in range(n-1):
    print(co[i]+1)
a, b = map(int, input().split())
coin = 0
coin += max(a, b)
max(a, b) -= 1
coin += max(a, b)
print(coin)

### FIXED CODE ###

(a, b) = map(int, input().split())
buttons = [a, b]
ans = 0
for i in range(2):
    if a >= b:
        ans += a
        a -= 1
    else:
        ans += b
        b -= 1
print(ans)
S=int(input())
if S[0]==S[1]:
  print('Bad')
elif S[1]==S[2]:
  print('Bad')
elif S[2]==S[3]:
  print('Bad')
else:
  print('Good')

### FIXED CODE ###

S=input()
if S[0]==S[1]:
  print('Bad')
elif S[1]==S[2]:
  print('Bad')
elif S[2]==S[3]:
  print('Bad')
else:
  print('Good')
while 1:
  n=int(input())
  if not n:break
  f=1
  L={}
  for a,b,c in [map(int,input().split()) for i in range(n)]:
    a=str(a)
    if a in L:
      d=b*c
      if L[a]>=1e6:continue
      L[a]+=d
    else:L[a]=d
    if L[a] >= 1e6:
      print(a)
      f=0
  if f:print('NA')

### FIXED CODE ###

while 1:
  n=int(input())
  if not n:break
  f=1
  L={}
  for a,b,c in [input().split() for i in range(n)]:
    d=int(b)*int(c)
    if a in L:
      if L[a]>=1e6:continue
      L[a]+=d
    else:L[a]=d
    if L[a]>=1e6:print(a);f=0
  if f:print('NA')
L, R, d = input().split()
cnt = 0
for t in Range(L,R+1):
  if t % d == 0:
    cnt = cnt + 1

print(cnt)


### FIXED CODE ###

L, R, d = input().split()
L = int(L)
R = int(R)
d = int(d)
cnt = 0
for t in range(L,R+1):
    if t % d == 0:
        cnt = cnt + 1

print(cnt)
dict = ["a","b","c","d","e","f","g","h","i","j","k","l","m",\
        "n","o","p","q","r","s","t","u","v","w","x","y","z"]
lsalpha = [1,3,5,7,9,11,15,17,19,21,23,25]

def deaffine(alpha, beta, code):
    decode = ""
    for chara in code:
        if chara != " ":
            f = dict.index(chara)
            for i in range(26):
                if (alpha*i + beta)%26 == f:
                    dechara = dict[i]
                    break
            decode += dechara
        else:
            decode += " "
    return decode
    
n = int(raw_input())
for roop in range(n):
    code = raw_input()
    for alpha in lsalpha:
        flag = 0
        for beta in range(26):
            deaffine(alpha, beta, code)
            if decode.count("that") > 0 or decode.count("this") > 0:
                flag = 1
                break
        if flag == 1:
            break
    print decode

### FIXED CODE ###

dict = ["a","b","c","d","e","f","g","h","i","j","k","l","m",\
        "n","o","p","q","r","s","t","u","v","w","x","y","z"]
lsalpha = [1,3,5,7,9,11,15,17,19,21,23,25]

def decode(alpha, beta, code):
    msg = ""
    for chara in code:
        if chara != " ":
            f = dict.index(chara)
            for i in range(26):
                if (alpha*i + beta)%26 == f:
                    dechara = dict[i]
                    break
            msg += dechara
        else:
            msg += " "
    return msg
    
n = int(raw_input())
for roop in range(n):
    code = raw_input()
    for alpha in lsalpha:
        flag = 0
        for beta in range(26):
            msg = decode(alpha, beta, code)
            if msg.count("that") > 0 or msg.count("this") > 0:
                flag = 1
                break
        if flag == 1:
            break
    print msg
n=int(input())
s=list(input() for i in range(n))
m=int(input())
t=list(input() for j in range(m))

for i in range(n):
    result=s.count(s[i])-t.count(s[i])

print(max(o,result))


### FIXED CODE ###

n=int(input())
s=[input() for _ in range(n)]
m=int(input())
t=[input() for _ in range(m)]
result=0
for i in set(s):
    result=max(result,s.count(i)-t.count(i))
print(result)