Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

import math as f 
a=int(input())
ans=0
for i in range(1,a+1):
 for j in range(1,a+1):
  for k in range(1,a+1):
   b=f.gcd(i,j)
   ans+=f.gcd(b,k)
print(ans)

### FIXED CODE ###

import math as f 
a=int(input())
ans=0
for i in range(1,a+1):
 for j in range(1,a+1):
  for k in range(1,a+1):
   b=f.gcd(i,j)
   ans+=f.gcd(b,k)
print(ans)
### BUGGY CODE ###

N = int(input())
inpt = input()
A = [int(a) for a in inpt.split()]
outputs = []
for i in range(N-1):
    negative = 0
    positive = 0
    for a in A:
        if a > 0:
            positive += 1
        elif a <= 0:
            negative += 1
    maxA = max(A)
    minA = min(A)
    if positive > negative:
        A.append(min(A)-max(A))
        outputs.append(str(minA)+" "+str(maxA))
    else:
        A.append(max(A)-min(A))
        outputs.append(str(maxA)+" "+str(minA))
    A.remove(maxA)
    A.remove(minA)

print(A[0])
for output in outputs:
    print(output)


### FIXED CODE ###

from collections import deque

N = int(input())
inpt = input()
A = [int(a) for a in inpt.split()]
A = deque(sorted(A))
outputs = []
negative = 0
positive = 0

for a in A:
    if a > 0:
        positive += 1
    elif a <= 0:
        negative += 1
for i in range(N-1):
    maxA = A[-1]
    minA = A[0]
    if minA>0:
        positive -= 1
    else:
        negative -= 1
    if maxA>0:
        positive -= 1
    else:
        negative -= 1
    A.pop()
    A.popleft()
    if positive > negative:
        newnum = minA-maxA
        A.appendleft(newnum)
        outputs.append(str(minA)+" "+str(maxA))
    else:
        newnum = maxA - minA
        A.append(newnum)
        outputs.append(str(maxA)+" "+str(minA))
    if newnum > 0:
        positive += 1
    else:
        negative += 1

print(A[0])
for output in outputs:
    print(output)
### BUGGY CODE ###

from collections import defaultdict

N, P = map(int, input().split())
S = input()

if P in (2, 5):
    count = 0
    for i in range(N):
        if int(S[i]) % P == 0:
            count += i + 1
    print(count)
else:
    d = defaultdict(int)
    r = 0
    for i in range(N):
        r += int(S[N - 1 - i]) * 10 ** (i % (P - 1))
        r %= P
        d[r] += 1

    count = d[0]
    for num in d.values():
        count += num * (num - 1) // 2
    print(count)

### FIXED CODE ###

from collections import defaultdict

N, P = map(int, input().split())
S = input()

if P in (2, 5):
    count = 0
    for i in range(N):
        if int(S[i]) % P == 0:
            count += i + 1
    print(count)
else:
    d = defaultdict(int)
    r = 0
    for i in range(N):
        r += int(S[N - 1 - i]) * pow(10, i % (P - 1), P)
        r %= P
        d[r] += 1

    count = d[0]
    for num in d.values():
        count += num * (num - 1) // 2
    print(count)
### BUGGY CODE ###

X, Y, Z, K = map(int, input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))
A.sort(reverse = True)
B.sort(reverse = True)
C.sort(reverse = True)
ans = [A[i]+B[j]+C[k] for k in range(Z) for j in range(Y) for i in range(X) if i*j*k <= K]
ans.sort(reverse=True)
for i in range(K):
    print(ans[i])

### FIXED CODE ###

X, Y, Z, K = map(int, input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))
A.sort(reverse = True)
B.sort(reverse = True)
C.sort(reverse = True)
t =[]
for i in range(X):
    for j in range(Y):
        for k in range(Z):
            if (i+1)*(j+1)*(k) <= K:
                t.append(A[i]+B[j]+C[k])
            else:break
t.sort(reverse=True)
for i in range(K):
    print(t[i])
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000)

#%%
def dfs(gr,li,pt,n,fr):
    li[n] += pt
    if(len(gr[n])==1 and gr[n][0]==fr):
        return True
    else:
        for i in gr[n]:
            if(i==fr):continue
            dfs(gr,li,li[n],i,n)
        return True
#%%
def main():
    N,Q = [int(x) for x in input().split()]
    li = [0]*N
    gp = [[] for _ in range(N)]
    for _ in range(N-1):
        a,b = [int(x) for x in input().split()]
        gp[a-1].append(b-1)
        gp[b-1].append(a-1)

    for _ in range(Q):
        p,x = [int(x) for x in input().split()]
        li[p-1] += x

    dfs(gp,li,0,0,-1)
    print(*li)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    N,Q = [int(x) for x in input().split()]
    li = [0]*N
    gp = [[] for _ in range(N)]
    for _ in range(N-1):
        a,b = input().split()
        a = int(a)
        b = int(b)
        gp[a-1].append(b-1)
        gp[b-1].append(a-1)

    for _ in range(Q):
        p,x = input().split()
        li[int(p)-1] += int(x)

    st = []
    seen = set()
    st.append(0)
    while(st):
        x = st.pop()
        if(x in seen):continue
        seen.add(x)
        for i in gp[x]:
            if(i in seen):continue
            li[i]+=li[x]
            st.append(i)
    print(*li)

if __name__ == '__main__':
    main()
### BUGGY CODE ###

n,k = input().split()
d = list(map(int,input().split()))
num = [i for i in range(10)]
poss = list(set(d) ^ set(num))
an = int(n)
while True:
    sum = 0
    for p in poss:
        sum += n.count(str(p))
    if sum ==len(n):
        break
    else:
        an +=1
print(an)

### FIXED CODE ###

n,k = map(int,input().split())
d=set(input().split())
while True:
    if len(set(str(n))&d)!=0:
        n+=1
    else:
        break
print(n)
### BUGGY CODE ###

n = int(input())
p = [int(i) for i in input().split()]

cnt = 0
for i in range(n):
    min_val = min(p[:i+1])
    if min_val >= p[i]:
        cnt += 1

print(cnt)

### FIXED CODE ###

n = int(input())
p = [int(i) for i in input().split()]

cnt = 0
min_val = p[0]
for i in range(n):
    min_val = min(min_val, p[i])
    if min_val >= p[i]:
        cnt += 1

print(cnt)
### BUGGY CODE ###

import sys
S=sys.stdin.readline()

mod=10**9+7

a=0
ab=0
ans=0
all=1

for x  in S:
	if x=="A":
		a+=all
	elif x=="B":
		ab+=a
	elif x=="C":
		ans+=ab
	elif x=="?":
		ans = ans*3 + ab
		ab = ab*3 + a
		a = a*3 + all
		all *= 3

	ans%=mod
	ab%=mod
	a%=mod
	all%mod


print ans%mod


### FIXED CODE ###

S=raw_input()

M=10**9+7

all=1
abc=0
ab=0
a=0

for x in S:
	if x=="A":
		a+=all
	if x=="B":
		ab+=a
	if x=="C":
		abc+=ab

	if x=="?":
		abc=abc*3+ab
		ab=ab*3+a
		a= a*3+all
		all*=3

	abc%=M
	ab%=M
	a%=M
	all%=M


print abc%M
### BUGGY CODE ###

N, K = map(int, input().split())
A = [list(map(int, input().split())) for i in range(N)]
MOD = 10**9 + 7


def dot(M1, M2, mod=10**9+7):
  n = len(M1)
  res = [[0]*n for _ in range(n)]
  for i in range(n):
    for j in range(n):
      for k in range(n):
        res[i][j] += M1[i][k] * M2[k][j] % MOD
  
  return res


def power(M, k, mod=10**9+7):
  if k == 1:
    return M
  elif k%2 == 0:
    return power(dot(M, M, mod), k//2)
  else:
    return dot(M, power(dot(M, M, mod), k//2), mod)


trans = power(A, K) 

ans = 0
for t in trans:
  ans += sum(t)%MOD
  ans %= MOD

print(ans)

### FIXED CODE ###

N, K = map(int, input().split())
A = [list(map(int, input().split())) for i in range(N)]
MOD = 10**9 + 7


def dot(M1, M2, mod=10**9+7):
  n = len(M1)
  res = [[0]*n for _ in range(n)]
  for i in range(n):
    for j in range(n):
      for k in range(n):
        res[i][j] += M1[i][k] * M2[k][j] % MOD
  
  return res


def power(M, k, mod=10**9+7):
  if k == 1:
    return M
  elif k%2 == 0:
    return power(dot(M, M, mod), k//2)
  else:
    return dot(M, power(dot(M, M, mod), k//2), mod)


trans = power(A, K) 

ans = 0
for t in trans:
  ans += sum(t)%MOD
  ans %= MOD

print(ans)
### BUGGY CODE ###

s = input()
count = 0

while ("01" in s) | ("10" in s):
    count += 2 * s.count("01")
    s = s.replace("01", "")
    count += 2 * s.count("10")
    s = s.replace("10", "")
print(count)


### FIXED CODE ###

s = input()
print(2 * min(s.count("0"), s.count("1")))
### BUGGY CODE ###

from collections import deque

def breadth_first_search(start):
    work_q = deque([])
    visited = set()
    work_q.append(start)
    visited.add(start)
    cnt_array = [0] * (n+1)
    while work_q:
        here = work_q.popleft()
        for i in edge[here]:
            if i not in visited:
                work_q.append(i)
                visited.add(i)
                cnt_array[i] = cnt_array[here] + 1
    return cnt_array

n,x,y = map(int,input().split())
edge = []
for i in range(n+1):
    edge.append([])
for i in range(1,n+1):
    if i != n:
        edge[i].append(i+1)
    if i != 1:
        edge[i].append(i-1)
edge[x].append(y)
edge[y].append(x)

ans = [0] * n
for i in range(1, n+1):
    a = breadth_first_search(i)
    for j in range(len(a)):
        ans[a[j]] += 1
for i in range(1,n):
    print(ans[i]//2)

### FIXED CODE ###

from collections import deque

def breadth_first_search(start):
    work_q = deque([])
    visited = set()
    work_q.append(start)
    visited.add(start)
    cnt_array = [0] * (n+1)
    while work_q:
        here = work_q.popleft()
        for i in edge[here]:
            if i not in visited:
                work_q.append(i)
                visited.add(i)
                cnt_array[i] = cnt_array[here] + 1
    return cnt_array

n,x,y = map(int,input().split())
edge = []
for i in range(n+1):
    edge.append([])
for i in range(1,n+1):
    if i != n:
        edge[i].append(i+1)
    if i != 1:
        edge[i].append(i-1)
edge[x].append(y)
edge[y].append(x)

ans = [0] * n
for i in range(1, n+1):
    a = breadth_first_search(i)
    for j in range(len(a)):
        ans[a[j]] += 1
for i in range(1,n):
    print(ans[i]//2)
### BUGGY CODE ###

mod = 10 ** 9 + 7


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


def read_list():
    return list(read_valus())


def read_lists(N):
    return [read_list() for n in range(N)]


def p(N, a):
    return (a * (N - a)) % mod


def main():
    N = int(input())
    A = read_list()

    num = [0] * 65
    for a in A:
        b = format(a, "065b")[::-1]
        for i in range(65):
            num[i] += int(b[i])

    res = 0
    for i in range(65):
        if num[i] == 0:
            continue

        res = (res + (pow(2, i, mod) * p(N, num[i])) % mod) % mod

    print(res % mod)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline

mod = 10 ** 9 + 7


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


def read_list():
    return list(read_valus())


def read_lists(N):
    return [read_list() for n in range(N)]


def p(N, a):
    return (a * (N - a)) % mod


def main():
    pows = [1] * 66
    for i in range(65):
        pows[i + 1] = (pows[i] * 2) % mod

    N = int(input())
    A = read_list()

    num = [0] * 65
    for a in A:
        tmp = a
        for i in range(65):
            if tmp == 0:
                break
            num[i] += tmp % 2
            tmp //= 2

    res = 0
    for i in range(65):
        if num[i] == 0:
            continue

        res = (res + (pows[i] * p(N, num[i])) % mod) % mod

    print(res % mod)


if __name__ == "__main__":
    main()
### BUGGY CODE ###

import networkx as nx

N,M=map(int,input().split())
S = [list(input()) for _ in range(N)]

if N == M == 1:
  print(0)
  print(S[0][0])
  exit()

index = lambda i,j: i*M+j

G=nx.DiGraph()
G.add_node('source')
G.add_node('sink')
dx,dy=(1,0),(0,1)
for i in range(N):
  for j in range(M):
    if S[i][j]=='#':continue
    if (i+j) %2:
      G.add_edge(index(i,j),'sink',capacity=1)
    else:
      G.add_edge('source',index(i,j),capacity=1)
    for k in range(2):
      v1,v2 = index(i,j),index(i+dx[k],j+dy[k])
      if not (0<=i+dx[k]<N and 0<=j+dy[k]<M):
        continue
      if S[i+dx[k]][j+dy[k]] == '#': continue
      if (i+j) % 2:
        G.add_edge(v2,v1,capacity=1)
      else:
        G.add_edge(v1,v2,capacity=1)
        
flow_value, flow_dict = nx.maximum_flow(G, "source", "sink")

for v1 in flow_dict.keys():
  if v1 in ('sink','source'):continue
  for v2 in flow_dict[v1]:
    if v2 in ('sink','source'):continue
    if flow_dict[v1][v2]:
      i1,j1 = divmod(v1,M)
      i2,j2 = divmod(v2,M)
      (i1,j1),(i2,j2) = sorted([(i1,j1),(i2,j2)])
      if i1 + 1 == i2:
        S[i1][j1] = 'v'
        S[i2][j2] = '^'
      else:
        S[i1][j1] = '>'
        S[i2][j2] = '<'

print(flow_value)
for i in range(N):
  print(''.join(S[i]))

### FIXED CODE ###

import networkx as nx

def main():
  N,M=map(int,input().split())
  S = [list(input()) for _ in range(N)]

  if N == M == 1:
    print(0)
    print(S[0][0])
    exit()

  index = lambda i,j: i*M+j

  G=nx.Graph()
  dx,dy=(1,0),(0,1)
  E = []
  n1,n2 = [],[]
  for i in range(N):
    for j in range(M):
      if S[i][j]=='#':continue
      if (i+j)%2:
        n1.append(index(i,j))
      else:
        n2.append(index(i,j))
      for k in range(2):
        v1,v2 = index(i,j),index(i+dx[k],j+dy[k])
        if not (0<=i+dx[k]<N and 0<=j+dy[k]<M):
          continue
        if S[i+dx[k]][j+dy[k]] == '#': continue
        if (i+j) % 2:
          E.append((v2,v1))
        else:
          E.append((v1,v2))
     
  G.add_nodes_from(n1, bipartite=0)
  G.add_nodes_from(n2, bipartite=1)
  G.add_edges_from(E)
  u = [n for n in G.nodes if G.nodes[n]['bipartite'] == 0]
  match = nx.bipartite.maximum_matching(G, top_nodes=u)
  match = {v:match[v] for v in match.keys() if v < match[v]}
 
  for v in match.keys():
    i1,j1 = divmod(v,M)
    i2,j2 = divmod(match[v],M)
    if i1 > i2 or j1 > j2:
      (i1,j1),(i2,j2) = (i2,j2),(i1,j1)
    if i1 < i2:
      S[i1][j1] = 'v'
      S[i2][j2] = '^'
    else:
      S[i1][j1] = '>'
      S[i2][j2] = '<'

  print(len(match))
  for i in range(N):
    print(''.join(S[i]))
    
if __name__ == "__main__":
  main()
### BUGGY CODE ###

n,m=map(int, input().split())
a=list(map(int, input().split()))

for _ in range(m):
    a[a.index(max(a))] //=2
print(sum(a))

### FIXED CODE ###

n,m=map(int, input().split())
a=list(map(int, input().split()))

from heapq import heappush, heappop
hq=[]

for a_val in a:
    # heappopで最も小さい値が取り出されるため、(-1)をかけて入れる
    heappush(hq, -a_val)
for _ in range(m):
    heappush(hq, -(heappop(hq)//(-2)))
print(-sum(hq))
### BUGGY CODE ###

from bisect import bisect_right,bisect_left
import sys
input = sys.stdin.readline

n,k=map(int,input().split())
a=list(map(int,input().split()))
ap,an=[],[]
zeronum=0
for i in a:
  if i>0: ap.append(i)
  elif i<0: an.append(-i)
  else: zeronum+=1
an.sort()
ap.sort()
np,nn=len(ap),len(an)
if np*nn<k<=np*nn+zeronum*(zeronum-1)//2+zeronum*(np+nn):
  print(0)
elif k<=np*nn:
    ng=10**18
    ok=0
    while ng-ok>1:
        mid=(ok+ng)//2
        cnt=0
        for i in an:
            if mid%i!=0: cnt+=np-bisect_left(ap,mid//i+1)
            else: cnt+=np-bisect_left(ap,mid//i)
        if cnt>=k: ok=mid
        else: ng=mid
    print(-ok)
else:
    k-=np*nn+zeronum*(zeronum-1)//2+zeronum*(np+nn)
    ok=10**18
    ng=0
    while ok-ng>1:
        mid=(ok+ng)//2
        cnt1,cnt2=0,0
        if np>=2:
            for i in ap:
                cnt1+=bisect_right(ap,mid//i)
                if i**2<=mid: cnt1-=1
        if nn>=2:
            for i in an:
                cnt2+=bisect_right(an,mid//i)
                if i**2<=mid: cnt2-=1
        if cnt1//2+cnt2//2>=k: ok=mid
        else: ng=mid
    print(ok)


### FIXED CODE ###

import numpy as np
n, k = map(int, input().split())
a = np.array(list(map(int, input().split())))
pos = np.sort(a[a>0])
neg = np.sort(np.abs(a[a<0]))
zero = (a==0).sum()

INF = 2*(10**18)
l = -INF
r = INF

while(r-l>1):
    mid = (l+r)//2
    cnt = 0
    if mid >= 0:
        cnt = len(pos)*len(neg)  #(+) * (-)
        cnt += (len(pos)+len(neg)) * zero # 0 * (non-zero)
        cnt += (zero*(zero-1))//2 # 0 * 0
        x = np.searchsorted(pos, mid//pos, side='right').sum() #(+) * (+)
        x += np.searchsorted(neg, mid//neg, side='right').sum() #(-) * (-)
        x -= (pos*pos<=mid).sum()
        x -= (neg*neg<=mid).sum()
        cnt += x/2
    else:
        #積がmid以上になれば良い -> midよりも小さい
        cnt = (len(neg) - np.searchsorted(neg, abs(mid)//pos + (mid%pos!=0), side='left')).sum()
    #print(mid, cnt)
    #cnt := 積がmid以下になる物の数
    #k番目の数　-> それ以下のものがk個以上ある事が必要
    #cntがk個よりも少ない -> 条件を満たしていない
    #cntがそれ以上ならok
    if cnt < k:
        l = mid
    else:
        r = mid
print(r)
### BUGGY CODE ###

n, q = map(int, input().split())
s = list(input())
#print(s)
for i in range(q):
    x = 0
    l, r =  map(int, input().split())
    y = s[l-1:r]
    y = [i for i in y if i  == 'A' or i  == 'C']
    #print(y)
    for j in range(len(y)-1):
        if y[j] + y[j+1] == 'AC':
            x += 1
    print(x)


### FIXED CODE ###

from itertools import accumulate

n, q = map(int, input().split())
s = list(input())
#print(s)
z = []
for i in range(n-1):
    if s[i] + s[i+1] == 'AC':
        z.append(1)
    else:
        z.append(0)
#print(z)

z = [0] + list(accumulate(z))
#print(z)

for j in range(q):
    l, r =  map(int, input().split())
    print(z[r-1] - z[l-1])
### BUGGY CODE ###

import numpy as np

H, W = map(int, input().split())

maze01 = np.array([[int(x=='.') for x in input()] for _ in range(H)]) 

u = np.zeros((H, W), dtype=np.int32)
d = np.zeros((H, W), dtype=np.int32)
r = np.zeros((H, W), dtype=np.int32)
l= np.zeros((H, W), dtype=np.int32)


u[0] = maze01[0]
d[H - 1] = maze01[H - 1]
for hh in range(1,H):
    u[hh] = u[hh-1] + maze01[hh]
    u[hh] = [x * y for x, y in zip(u[hh], maze01[hh])]
    d[H - hh - 1, :] = d[H - hh] + maze01[H - hh - 1]
    d[H - hh - 1] = [x * y for x, y in zip(d[H - hh -1], maze01[H - hh - 1])]

l[:, 0] = maze01[:, 0]
r[:, W - 1] = maze01[:, W - 1]
for ww in range(1, W):
    l[:, ww] = l[:, ww -1] + maze01[:, ww]
    l[:, ww] = [x * y for x, y in zip(l[:, ww], maze01[:, ww])]
    r[:, W - ww -1] = r[:, W - ww] + maze01[:, W - ww - 1]
    r[:, W - ww -1] = [x * y for x, y in zip(r[:, W - ww -1], maze01[:, W -ww - 1])]

cnt = r + l + u + d - 3

print(max([max(cnt[i]) for i in range(H)]))


### FIXED CODE ###

import numpy as np

H, W = map(int, input().split())

maze01 = np.array([[int(x=='.') for x in input()] for _ in range(H)]) 

u = np.zeros((H, W), dtype=np.int32)
d = np.zeros((H, W), dtype=np.int32)
r = np.zeros((H, W), dtype=np.int32)
l= np.zeros((H, W), dtype=np.int32)


u[0] = maze01[0]
d[H - 1] = maze01[H - 1]
for hh in range(1,H):
    u[hh] = u[hh-1] + maze01[hh]
    u[hh] *= maze01[hh]
    d[H - hh - 1] = d[H - hh] + maze01[H - hh - 1]
    d[H - hh - 1] *= maze01[H - hh - 1]

l[:, 0] = maze01[:, 0]
r[:, W - 1] = maze01[:, W - 1]
for ww in range(1, W):
    l[:, ww] = l[:, ww -1] + maze01[:, ww]
    l[:, ww] *= maze01[:, ww]
    r[:, W - ww -1] = r[:, W - ww] + maze01[:, W - ww - 1]
    r[:, W - ww -1] *= maze01[:, W - ww - 1]

cnt = r + l + u + d - 3

print(max([max(cnt[i]) for i in range(H)]))
### BUGGY CODE ###

def hash1(m,key):
    return key % m

def hash2(m,key):
    return 1 +  key % ( m -1 )

def hash(m,key,i):
    return (hash1(m,key) + i * hash2(m,key) ) % m

def insert(T,key):
    i = 0
    l = len(T)
    while True:
        h = hash(1046527,key,i)
        if (T[h] == None ):
            T[h] = key
            return h
        else:
            i += 1

def search(T,key):
    l = len(T)
    i = 0
    while True:
        h = hash(1046527,key,i)
        if(T[h] == key):
            return h
        elif(T[h] is None or h >= l):
            return -1
        else:
            i += 1

def find(T,key):
    a = search(T,key)
    if(a == -1):
        print('no')
    else:
        print('yes')

dict = {'A' : '1', 'C' : '2', 'G' : '3', 'T' : '4'}
data = []
T = [None]*1046527
n = int(input())


while n > 0:
    st = input()
    d = list(st.split())

### convert key to num(1~4)
    tmp_key = ''
    for x in list(d[1]):
        tmp_key += dict[x]

    data.append([d[0],int(tmp_key)])
    n -= 1
for com in data:
    if(com[0] == 'insert'):
        insert(T,com[1]) 
    else:
        find(T,com[1])

### FIXED CODE ###

def hash1(m, key):
    return key % m

def hash2(m, key):
    return 1 +  key % (m - 1)

def hash(m, key, i):
    return (hash1(m, key) + i * hash2(m, key) ) % m

def insert(T, key):
    i = 0
    l = len(T)
    while True:
        h = hash(1046527,key,i)
        if (T[h] == None ):
            T[h] = key
            return h
        elif (T[h] == key):
            return h
        else:
            i += 1

def search(T,key):
    l = len(T)
    i = 0
    while True:
        h = hash(1046527,key,i)
        if(T[h] == key):
            return h
        elif(T[h] is None or h >= l):
            return -1
        else:
            i += 1

def find(T, key):
    a = search(T,key)
    if(a == -1):
        print('no')
    else:
        print('yes')

dict = {'A' : '1', 'C' : '2', 'G' : '3', 'T' : '4'}
data = []
T = [None]*1046527
n = int(input())


while n > 0:
    st = input()
    d = list(st.split())

### convert key to num(1~4)
    tmp_key = ''
    for x in list(d[1]):
        tmp_key += dict[x]

    data.append([d[0],int(tmp_key)])
    n -= 1
for com in data:
    if(com[0] == 'insert'):
        insert(T,com[1]) 
    else:
        find(T,com[1])
### BUGGY CODE ###

from sys import stdin


def readline_from_stdin() -> str:
    return stdin.readline().rstrip


if __name__ == '__main__':
    N, K, = input().split()
    A = [int(i) for i in input().split()]
    N, K = int(N), int(K)

    score = 1
    for i in range(K):
        score *= A[i]

    for i in range(N-K):
        new_score = int(score / A[i]) * A[K+i]
        if new_score > score:
            print("Yes")
        else:
            print("No")
        score = new_score

    # scores = [score]
    # for i in range(N-K):
    #     print(i, K+i)
    #     score = int(score / A[i]) * A[K+i]
    #     scores.append(score)
    #
    # print(scores)
    #
    # results = [False for i in range(len(scores)-1)]
    #
    # for i in range(len(scores)-1):
    #     results[i] = scores[i+1] > scores[i]
    #
    # [print("Yes") if r else print("no") for r in results]


### FIXED CODE ###

from sys import stdin


def readline_from_stdin() -> str:
    return stdin.readline().rstrip


if __name__ == '__main__':
    N, K, = input().split()
    A = [int(i) for i in input().split()]
    N, K = int(N), int(K)

    for i in range(N-K):
        if A[i] < A[K+i]:
            print("Yes")
        else:
            print("No")
### BUGGY CODE ###

import sys

n = int(input())
ans = 0
while n>0:
    ans += n%10
    n = n//10
    
#print(ans)

if ans%9 == 0:
    print("Yes")
else:
    print("No")




### FIXED CODE ###

def digitSum(n):
    # 数値を文字列に変換
    s = str(n)
    # １文字ずつ数値化し配列にする。
    array = list(map(int, s))
    # 合計値を返す
    return sum(array)

n = int(input())
ans = digitSum(n)
#print(ans)

if ans%9 == 0:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

n = int(input())

ans = 0
D = {}
for i in range(n):
      s = "".join(sorted(input()))
      if s in D.keys():
            ans += D[s]
            D[s] += 1
      else:
            D[s] = 1
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
 
N=int(input())
dic={}
sum=0
for i in range(N):
    s=list(input())
    s.sort()
    s = "".join(s)
    if s in dic:
        sum+=dic[s]
        dic[s]+=1
    else:
        dic[s]=1
print(sum)
### BUGGY CODE ###

N, X = map(int, input().split())
dp = [''] * (N + 1)
dp[0] = 'P'

for i in range(1, N + 1):
	dp[i] = 'B' + dp[i - 1] + 'P' + dp[i - 1] + 'B'
	
print(dp[N][0:X].count('P'))

### FIXED CODE ###

N, X = map(int, input().split())
dp_layer = [1] * (N + 1)
dp_numP = [1] * (N + 1)

for i in range(1, N + 1):
	dp_layer[i] = 3 + 2 * dp_layer[i - 1]
	dp_numP[i] = 1 + 2 * dp_numP[i - 1]
	
x = X
countP = 0
i = N

while x > 0:
	if x >= dp_layer[i]:
		x -= dp_layer[i]
		countP += dp_numP[i]
		if x > 0:
			x -= 1
			countP += 1
	else:
		i -= 1
		x -= 1
		
print(countP)