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

def main():
  n,m = list(map(int,input().split()))
  d = []
  ma = 0
  mi = 0
  for i in range(m):
    a,b = list(map(int,input().split()))
    d.append( ((1<<a)-1) ^ ((1<<b)-1) )
    ma = max(ma,a,b)
    mi = min(mi,a,b)
  s = ((1<<ma)-1) | ((1<<mi)-1) 
  for bit in range(1<<n):
    if bit & s:
      spr = [True]*m
      for k in range(m):
        if (d[k] & bit) > 0:
          spr[k] = False
      if sum(spr) == 0:
        print(sum([1 for i in range(n) if bit & 1<<i]))
        exit()

main()


### FIXED CODE ###


n,m = list(map(int,input().split()))
d = [0]*m
spr = [True]*m
ma = 0
mi = 0
for i in range(m):
    a,b = list(map(int,input().split()))
    d[i] = [a,b]

d = sorted(d)
pre = d[0][1]
ans = 1
for i,(a,b) in enumerate(d):
  if a < pre:
    if b < pre:
      pre = b
  else:
    ans += 1
    pre = b

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

N = int(input())
A = list(map(int, input().split()))
x = 0
m = A[0]
for x in range(1, N):
    m *= A[x]

if m <= pow(10, 18):
    print(m)
else:
    print(-1)


### FIXED CODE ###

def main():
    N = int(input())
    A = list(map(int, input().split()))

    if 0 in A:
        print(0)
        return

    m = 1
    for x in A:
        m *= x
        if m > 10**18:
            print(-1)
            return
    print(m)
main()
### BUGGY CODE ###

import functools
import operator

N = int(input())

A = list(map(int, input().split()))

x = functools.reduce(operator.mul, A)
y = 10**18


if x > y:
    print("-1")
else:
    print(x)

### FIXED CODE ###

N = int(input())
l = list(map(int,input().split()))
l.sort()
ans = 1
rec = True
for i in range(N):
    ans = ans * l[i]
    if ans > 10**18:
        rec = False
        break

if rec:
    print(ans)
else:
    print('-1')
### BUGGY CODE ###

N, Y = map(int,input().split())

if Y % 1000 != 0:
    print(-1,-1,-1)

n1 = Y // 10000
n2 = Y // 5000
n3 = Y // 1000
if abs(N-n1) < abs(N-n3):
    for i in range(N,-1,-1):
        for j in range(n2+1):
            for k in range(n1+1):
                if i*10000 + j*5000 + k*1000 == Y and i+j+k == N:
                    print(i,j,k)
                    exit()
                if Y < i*10000 + j*5000 + k*1000: break
else:
    for i in range(N,-1,-1):
        for j in range(n2+1):
            for k in range(n3+1):
                if k*10000 + j*5000 + i*1000 == Y and i+j+k == N:
                    print(k,j,i)
                    exit()
                if Y < k*10000 + j*5000 + i*1000: break
print(-1,-1,-1)

### FIXED CODE ###

N, Y = map(int,input().split())

if Y % 1000 != 0:
    print(-1,-1,-1)

n1 = Y // 10000
n2 = Y // 5000

for i in range(n1+1):
    for j in range(n2+1):
        if (N-i-j) < 0: continue
        if i*10000 + j*5000 + (N-i-j)*1000 == Y:
            print(i,j,(N-i-j))
            exit()
        if Y < i*10000 + j*5000 + (N-i-j)*1000: break
print(-1,-1,-1)
### BUGGY CODE ###

N = int(input())
res = []
while True:
    if N % -2 != 0:
        res.append("1")
    else:
        res.append("0")
    
    if N == 1:
        break

    if N % -2 != 0:
        N -= 1
    N //= -2

print("".join(reversed(res)))

### FIXED CODE ###

N = int(input())
res = []
while N != 0:
    if N % -2 != 0:
        res.append("1")
    else:
        res.append("0")
    
    if N == 1:
        break

    if N % -2 != 0:
        N -= 1
    N //= -2

if N != 0:
    print("".join(reversed(res)))
else:
    print(0)
### BUGGY CODE ###

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

total = sum(a)

ans = float("INF")
for i in range(n-1):
    former = sum(a[:i+1])
    ans = min(ans, abs(former - (total - former)))
print(ans)

### FIXED CODE ###

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

a = list(itertools.accumulate(a))

target = a[-1]
for i in a:
    target = min(abs(a[-1] - i * 2), target)

print(target)
### BUGGY CODE ###

A = int(input())
a = 1
for i in range(1,A+1):
  a = a * i
print(a%(pow(10,9)+7))

### FIXED CODE ###

A = int(input())
b = 1
mod = 1000000007
for a in range(1,A+1):
  b = b*a % mod
print(b)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)


def unite(par, i, j):
    j = get_par(par, j)
    par[j] = get_par(par, i)

def get_par(par, p):
    while par[p] != p:
        p = par[p]
    return par[p]

n,k,l = map(int, input().split())
pq = []
road = [i for i in range(n+1)]
rcnt = [set([i]) for i in range(n+1)]
rail = [i for i in range(n+1)]
acnt = [set([i]) for i in range(n+1)]
for i in range(k):
    p,q = map(int,input().split())
    pq.append((p,q))
    aa = get_par(road, p)
    bb = get_par(road, q)
    if aa == bb:
        continue
    # unite
    if aa < bb:
        road[bb] = aa
        rcnt[aa] |= rcnt[bb]
    else:
        road[aa] = bb
        rcnt[bb] |= rcnt[aa]

rs = []
for i in range(l):
    p,q = map(int,input().split())
    rs.append((p,q))
    aa = get_par(rail, p)
    bb = get_par(rail, q)
    if aa == bb:
        continue
    # unite
    if aa < bb:
        rail[bb] = aa
        acnt[aa] |= acnt[bb]
        # acnt[aa] += acnt[bb]
    else:
        rail[aa] = bb
        acnt[bb] |= acnt[aa]

ans = [0 for _ in range(n+1)]
for i in range(1,n+1):
    if ans[i] == 0:
        r = get_par(road, i)
        l = get_par(rail, i)
        # print(rcnt[r], acnt[l])
        cnt = 0
        for j in rcnt[r] | acnt[l]:
            if j in rcnt[r] and j in acnt[l]:
                cnt += 1
        for j in rcnt[r] & acnt[l]:
            ans[j] = cnt

print(*ans[1:])
# print(acnt)
# print(rcnt)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)


def unite(par, i, j):
    j = get_par(par, j)
    par[j] = get_par(par, i)

def get_par(par, p):
    while par[p] != p:
        p = par[p]
    return par[p]

n,k,l = map(int, input().split())
pq = []
road = [i for i in range(n+1)]
rcnt = [set([i]) for i in range(n+1)]
rail = [i for i in range(n+1)]
acnt = [set([i]) for i in range(n+1)]
for i in range(k):
    p,q = map(int,input().split())
    pq.append((p,q))
    aa = get_par(road, p)
    bb = get_par(road, q)
    if aa == bb:
        continue
    # unite
    if aa < bb:
        road[bb] = aa
        rcnt[aa] |= rcnt[bb]
    else:
        road[aa] = bb
        rcnt[bb] |= rcnt[aa]

rs = []
for i in range(l):
    p,q = map(int,input().split())
    rs.append((p,q))
    aa = get_par(rail, p)
    bb = get_par(rail, q)
    if aa == bb:
        continue
    # unite
    if aa < bb:
        rail[bb] = aa
        acnt[aa] |= acnt[bb]
        # acnt[aa] += acnt[bb]
    else:
        rail[aa] = bb
        acnt[bb] |= acnt[aa]

ans = [(road[get_par(road, i)], rail[get_par(rail, i)]) for i in range(1,n+1)]
from collections import Counter
c = Counter(ans)
print(*[c[(road[get_par(road, i)], rail[get_par(rail, i)])] for i in range(1,n+1)])
# print(acnt)
# print(rcnt)
### BUGGY CODE ###

while 1:
    INF = 10**9
    N, K = map(int, input().split())
    if N == K == 0:
        break
    E = [[INF]*N for i in range(N)]
    for i in range(N):
        E[i][i] = 0
    ans = []
    for i in range(K):
        q, *c = map(int, input().split())
        if q == 0:
            a, b = c
            cost = E[a-1][b-1]
            if INF <= cost:
                ans.append(-1)
            else:
                ans.append(cost)
        else:
            c, d, e = c
            if e < E[c-1][d-1]:
                E[c-1][d-1] = E[d-1][c-1] = e
                for i in range(N):
                    for j in range(N):
                        E[i][j] = E[j][i] = min(E[i][j], E[i][c-1] + e + E[d-1][j], E[i][d-1] + e + E[c-1][j])
    print(*ans, sep='\n')


### FIXED CODE ###

while 1:
    INF = 10**9
    N, K = map(int, input().split())
    if N == K == 0:
        break
    E = [[INF]*N for i in range(N)]
    for i in range(N):
        E[i][i] = 0
    ans = []
    for i in range(K):
        q, *c = map(int, input().split())
        if q == 0:
            a, b = c
            cost = E[a-1][b-1]
            if INF <= cost:
                ans.append(-1)
            else:
                ans.append(cost)
        else:
            c, d, e = c
            if e < E[c-1][d-1]:
                E[c-1][d-1] = E[d-1][c-1] = e
                Ec = E[c-1]; Ed = E[d-1]
                for i in range(N):
                    Ei = E[i]
                    Eic = Ei[c-1] + e
                    Eid = Ei[d-1] + e
                    for j in range(i+1, N):
                        Ei[j] = E[j][i] = min(Ei[j], Eic + Ed[j], Eid + Ec[j])
    print(*ans, sep='\n')
### BUGGY CODE ###

n = int(input())
A = list(map(int, input().split()))
for i in range(n):
    ans = 0
    now = 0
    for j, a in enumerate(A):
        if i == j:
            continue
        ans += abs(a-now)
        now = a
    print(ans + abs(now))

### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
A.insert(0, 0)
A.append(0)
ans = 0
now = 0
for a in A:
    ans += abs(a - now)
    now = a
for i in range(1, n+1):
    removei = abs(A[i-1] - A[i]) + abs(A[i] - A[i+1])
    concati = abs(A[i-1] - A[i+1])
    print(ans - removei + concati)
### BUGGY CODE ###

N,Q=list(map(int,input().strip().split(' ')))
gr=[[] for _ in range(N)]
val=[0]*N
for _ in range(N-1):
    a,b=list(map(int,input().strip().split(' ')))
    a-=1
    b-=1
    gr[a]+=[b]
    gr[b]+=[a]
for _ in range(Q):
    p,x=list(map(int,input().strip().split(' ')))
    p-=1
    val[p]+=x
ans=[0]*N
stack=[0]
checked=[0]*N
checked[0]=1
ans[0]=val[0]
while stack:
    x=stack.pop()
    for v in gr[x]:
        if checked[v]==0:
            stack+=[v]
            checked[v]=1
            ans[v]=ans[x]+val[v]
ans=[str(x) for x in ans]

print(" ".join(ans))

### FIXED CODE ###

N,Q=list(map(int,input().strip().split(' ')))
gr=[[] for _ in range(N)]
val=[0]*N
for _ in range(N-1):
    a,b=list(map(int,input().strip().split(' ')))
    a-=1
    b-=1
    gr[a]+=[b]
    gr[b]+=[a]
for _ in range(Q):
    p,x=list(map(int,input().strip().split(' ')))
    p-=1
    val[p]+=x
ans=[0]*N
stack=[0]
checked=[0]*N
checked[0]=1
ans[0]=val[0]
while stack:
    x=stack.pop()
    for v in gr[x]:
        if checked[v]==0:
            stack+=[v]
            checked[v]=1
            ans[v]=ans[x]+val[v]
ans=[str(x) for x in ans]

print(" ".join(ans))
### BUGGY CODE ###

def merge_sort(A):
    if len(A) <= 1:
        return A, 0
    mid = len(A) // 2
    left, lcount = merge_sort(A[:mid])
    right, rcount = merge_sort(A[mid:])
    merged, count = merge(left, right)
    return merged, lcount + rcount + count

def merge(left, right):
    lpos = 0
    rpos = 0
    rcount = 0
    merged = []
    while lpos < len(left) and rpos < len(right):
        if left[lpos] < right[rpos]:
            merged.append(left[lpos])
            lpos += 1
        else:
            merged.append(right[rpos])
            rpos += 1
            rcount += len(left[lpos:])
    
    if left[lpos:]:
        merged.extend(left[lpos:])
    if right[rpos:]:
        merged.extend(right[rpos:])
    
    return merged, rcount
    
if __name__ == '__main__':
    n = int(raw_input())
    A = map(int, raw_input().split())
    
    sorted, count = merge_sort(A)
    #print ' '.join(str(x) for x in sorted)
    print count

### FIXED CODE ###

from array import array

def merge_sort(A):
    if len(A) <= 1:
        return A, 0
    mid = len(A) // 2
    left, lcount = merge_sort(A[:mid])
    right, rcount = merge_sort(A[mid:])
    merged, count = merge(left, right)
    return merged, lcount + rcount + count

def merge(left, right):
    lpos = 0
    rpos = 0
    rcount = 0
    merged = array('I', [])  # List is too slow. Use an array instead.
    len_left = len(left)
    len_right = len(right)
    while lpos < len_left and rpos < len_right:
        if left[lpos] < right[rpos]:
            merged.append(left[lpos])
            lpos += 1
        else:
            merged.append(right[rpos])
            rpos += 1
            #rcount += len(left[lpos:])
            rcount += len_left - lpos
    
    if left[lpos:]:
        merged.extend(left[lpos:])
    if right[rpos:]:
        merged.extend(right[rpos:])
    
    return merged, rcount
    
if __name__ == '__main__':
    n = int(raw_input())
    A = array('I', map(int, raw_input().split()))
    
    sorted, count = merge_sort(A)
    #print ' '.join(str(x) for x in sorted)
    print count
### BUGGY CODE ###

from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
INF = float("inf")


def main():
    N, M = map(int, input().split())
    graph = defaultdict(list)
    route = []
    for _ in range(M):
        A, B = map(int, input().split())
        if not route:
            route += [A, B]
        graph[A].append(B)
        graph[B].append(A)

    while True:
        start, end = route[0], route[-1]
        start_ok = True
        for n in graph[start]:
            if n not in route:
                start_ok = False
                route = [n] + route
                break

        end_ok = True
        for n in graph[end]:
            if n not in route:
                end_ok = False
                route.append(n)
                break

        if start_ok and end_ok:
            break

    print(len(route))
    print(*route, sep=" ")


if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
INF = float("inf")


def main():
    N, M = map(int, input().split())
    graph = defaultdict(list)

    for _ in range(M):
        A, B = map(int, input().split())
        graph[A].append(B)
        graph[B].append(A)

    route = deque()
    used = set()
    route.appendleft(1)
    used.add(1)
    for n in graph[1]:
        route.append(n)
        used.add(n)
        break

    while True:
        start, end = route[0], route[-1]
        start_ok = True
        for n in graph[start]:
            if n not in used:
                start_ok = False
                route.appendleft(n)
                used.add(n)
                break

        end_ok = True
        for n in graph[end]:
            if n not in used:
                end_ok = False
                route.append(n)
                used.add(n)
                break

        if start_ok and end_ok:
            break

    print(len(route))
    print(*route, sep=" ")


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

#ABC169b

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

sum = 1

for i in range(n):
    sum = sum * a[i]

if sum > 10**18:
    print(-1)
else:
    print(sum)


### FIXED CODE ###

#ABC169b

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

sum = 1

if 0 in a:
    sum = 0
else:
    for i in range(n):
        sum = sum * a[i]
        if sum > 10**18:
            break

if sum > 10**18:
    print(-1)
else:
    print(sum)
### BUGGY CODE ###

def main():
    N = int(input())
    X = tuple(map(int,input().split()))
    MOD = 10 ** 9 + 7
    goal = X[-1]
    ans = goal - X[0]
    x = 1
    count = 2
    for i in X[1:N-1]:
       tmp = goal - i
       ans = ((ans * count) + ((x * tmp))) % MOD
       x *= count % MOD
       count += 1
    print(ans)
if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    N = int(input())
    X = list(map(int,input().split()))
    MOD = 10 ** 9 + 7
    goal = X[-1]
    ans = goal - X[0]
    fact = [1]
    fact_inv = [1]
    for i in range(10**5+5):
        new_fact = fact[-1]*(i+1)%MOD
        fact.append(new_fact)
    count = 1
    for i in range(1,N-1):
        count += 1
        tmp = goal - X[i]
        ans = ((ans * count) + ((fact[i] * tmp))) % MOD  
    print(ans)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import itertools
import heapq

def heapsort(iterable):
    h = []
    for value in iterable:
        heapq.heappush(h, value)
    return [heapq.heappop(h) for i in range(len(h))]

N = int(input())
L = list(map(int, input().split()))
# L.sort(reverse=True)
L_sort = heapsort(L)
# print (L)
answer = 0
for i in itertools.combinations(L_sort, 3):
    # print(i)
    if i[2] < i[0] + i[1]:
        answer += 1
print(answer)

### FIXED CODE ###

import itertools
import heapq
from bisect import bisect_left


def heapsort(iterable):
    h = []
    for value in iterable:
        heapq.heappush(h, value)
    return [heapq.heappop(h) for i in range(len(h))]

N = int(input())
L = list(map(int, input().split()))
L.sort()
# L_sort = heapsort(L)
# print (L)
answer = 0
for i, a in enumerate(L[0:N-2]):
    for j, b in enumerate(L[i+1:N-1]):
        index = bisect_left(L, a+b)
        answer += max(index - (j+i+1) -1, 0)
        # print(L, a+b, index, j+i+1, answer)
print(answer)
### BUGGY CODE ###

N, = map(int, input().split())
R = [0] * (N**2+1)
V = [0] * (N**2+1)
X = list(map(int, input().split()))
for ai in range(N**2):
    i, j = divmod(ai, N)
    R[ai+1] = min([i, N-i-1, j, N-j-1])
#print(R)

r = 0
for a in X:
    r += R[a]
    V[a] = 1
    stack=[a]
    vs = set([a])
    while stack:
        v = stack.pop()
        i, j = divmod(v-1, N)
        ccs = []
        if v>N:
            ccs.append(v-N)
        if v<N**2+1-N:
            ccs.append(v+N)
        if v%N:
            ccs.append(v+1)
        if v%N!=1:
            ccs.append(v-1)
        for u in ccs:
            if u in vs:
                continue
            if V[v] and R[v] >= R[u]:
                continue
            if (1-V[v]) and R[v] +1 >= R[u]:
                continue
            R[u] -= 1
            vs.add(u)
            stack.append(u)
print(r)


### FIXED CODE ###

N, = map(int, input().split())
R = [0] * (N**2+1)
V = [0] * (N**2+1)
X = list(map(int, input().split()))
for ai in range(N**2):
    i, j = divmod(ai, N)
    R[ai+1] = min([i, N-i-1, j, N-j-1])

r = 0
for a in X:
    r += R[a]
    V[a] = 1
    stack=[a]
    while stack:
        v = stack.pop()
        ccs = []
        if v>N:
            ccs.append(v-N)
        if v<N**2+1-N:
            ccs.append(v+N)
        if v%N:
            ccs.append(v+1)
        if v%N!=1:
            ccs.append(v-1)
        for u in ccs:
            if R[v]>=R[u] or ((1-V[v]) and R[v]+1 >= R[u]):
                continue
            R[u] -= 1
            stack.append(u)
print(r)
### BUGGY CODE ###

n = int(input())
x = int(input(),2)

def popcount2(n):
    return bin(n).count("1")

def popcount(n):
    ans = 0
    while n:
        ans += n % 2
        n //= 2
    return ans

pops = popcount(x)
x_pop_p = x%(pops + 1)
try:
    x_pop_m = x%(pops - 1)
except:
    x_pop_m = 0
#print(x_pop_p)
#print(x_pop_m)
#print()
for i in reversed(range(0,n)):
    bit = x^(1<<i)
    #print(bin(bit))
    #print(bit)
    #print(popcount(bit))
    if bit == 0:
        print(0)
        continue
    if x&(1<<i):
        tmp = (x_pop_m - pow(2,i,(pops - 1)))%(pops - 1)
    else:
        tmp = (x_pop_p + pow(2,i,(pops + 1))) % (pops + 1)
    #print(tmp)
    if tmp == 0:
        print(1)
        continue
    cnt = 2
    tmp_pop = popcount(tmp)
    if tmp_pop == 0:
        print(cnt-1)
        continue
    tmp = tmp % tmp_pop
    while tmp > 0:
        cnt += 1
        tmp_pop = popcount(tmp)
        if tmp_pop == 0:
            print(cnt-1)
            continue
        tmp %= tmp_pop
    print(cnt)
    #print()

### FIXED CODE ###

n = int(input())
s = input()
x = int(s, 2)
pcx = s.count("1")
pc1 = x % (pcx - 1) if pcx > 1 else 0
pc2 = x % (pcx + 1)

def f(j):
    cnt = 0
    while j:
        j %= bin(j).count("1")
        cnt += 1
    return cnt

for i, y in enumerate(s):
    k = n - 1 - i
    if y == "0":
        print(f((pc2 + pow(2, k, pcx + 1)) % (pcx + 1)) + 1)
    elif pcx > 1:
        print(f((pc1 - pow(2, k, pcx - 1)) % (pcx - 1)) + 1)
    else:
        print(0)
### BUGGY CODE ###

s=input()
q=int(input())
sign=1
for i in range(q):
  Q=[str(i) for i in input().split()]
  if Q[0]=="1":
    sign*=-1
  else:
    f,c=Q[1:]
    if f=="1" and sign==1:
      s=c+s
    elif f=="2" and sign==-1:
      s=c+s
    else:
      s=s+c
print(s if sign==1 else s[::-1])

### FIXED CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip()
s=input()
q=int(input())
sign=1
F,B="",""
for i in range(q):
  Q=[str(i) for i in input().split()]
  if Q[0]=="1":
    sign*=-1
  else:
    f,c=Q[1:]
    if f=="1" and sign==1:
      F=c+F
    elif f=="2" and sign==-1:
      F=c+F
    else:
      B=B+c
ans=F+s+B
print(ans if sign==1 else ans[::-1])
### BUGGY CODE ###

import sys 
sys.setrecursionlimit(10**7)
N, T = map(int, input().split())
A = []
for _ in range(N):
  a, b = map(int,input().split())
  A.append((a, b))
A.sort(key=lambda x: x[1], reverse=True)
A.sort(key=lambda x: x[0])
ans = []
max_point = [-1 for _ in range(T)]
def solve(point, x, unvisit_list):
  if x >= T or len(unvisit_list) == 0:
    ans.append(point)
    return 0
  elif max_point[x] > point:
    return 0
  else:
    max_point[x] = point
    for k in range(len(unvisit_list)):
      new_unvisit = unvisit_list[:k] + unvisit_list[k+1:]
      solve(point+unvisit_list[k][1], x + unvisit_list[k][0], new_unvisit)
    return 0

while A:
  item = A[0]
  del A[0]
  solve(item[1], item[0], A)
print(max(ans))

### FIXED CODE ###

N, T = map(int, input().split())
A = []
for _ in range(N):
  a, b = map(int,input().split())
  A.append((a, b))
A.sort(key=lambda x: x[0])

newdp = [0 for _ in range(T)]
ans = 0
from collections import deque
A = deque(A)
visited = [0]
while A:
  olddp = tuple(newdp)
  newdp = list(newdp)
  X = A.popleft()
  a = X[0]
  b = X[1]
  for v in visited:
    if v + a > T-1:
      ans = max(ans, olddp[v]+b)
    else:

      if newdp[v+a] == 0:
        visited.append(v+a)
      newdp[v+a] = max(olddp[v] + b, newdp[v+a])


if ans == 0:
  print(max(olddp))
else:
  print(ans)
### BUGGY CODE ###

def spline(func=int, iter_=None):
    if iter_ is None:
        iter_ = input().split()
    return map(func, iter_)


def parg(**kwargs):
    text = ''
    for item in kwargs.items():
        if text:
            text += ',\t'
        text += '{}: {}'.format(*item)
    print(text)


K, S = spline()
count = 0
K += 1
for x in range(K):
    for y in range(K):
        for z in range(K):
            tmp = x + y + z
            if tmp == S:
                count += 1
                # parg(x=x, y=y, z=z, sum=tmp)
                break

print(count)


### FIXED CODE ###

def spline(func=int, iter_=None):
    if iter_ is None:
        iter_ = input().split()
    return map(func, iter_)


K, S = spline()
count = 0
k = K + 1
for x in range(k):
    for y in range(k):
        z = S - x - y
        if 0 <= z <= K:
            count += 1
print(count)
### BUGGY CODE ###

a,b,k = map(int,input().split())
L=[]
for i in range(a,b+1):
    L.append(i)
L.sort(reverse=True)
O=L[:k]+L[-k:]
O=list(set(O))
O.sort(reverse=False)
for j in range(len(O)):
    print(O[j])

### FIXED CODE ###

a,b,k = map(int,input().split())
A=[]
for i in range(a,min(a+k,b+1)):
    A.append(i)
B=[]
for i in range(b,max(b-k,a-1),-1):
    B.append(i)
C=list(set(A+B))
C.sort(reverse=False)
for j in range(len(C)):
    print(C[j])
### BUGGY CODE ###

n=int(input())
s=0
while n>0:
  s=s+n%10
  n=n//10
if s%9==0:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

n=input()
a=list(map(int,n))
x=sum(a)%9
if x==0:
  print("Yes")
else:
  print("No")