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

import sys
input = sys.stdin.readline

class BIT:

    def __init__(self, N):
        self.N = N
        self.bit = [0] * (N+1)

    def add(self, x, a):
        while x <= self.N:
            self.bit[x] += a
            x += x & -x

    def sum(self, x):
        ret = 0
        while x != 0:
            ret += self.bit[x]
            x -= x & -x
        return ret

N, Q = map(int, input().split())
c = list(map(int, input().split()))
rl = [None] * Q
for i in range(Q):
    l, r = map(int, input().split())
    rl[i] = (r, l, i)
rl.sort()
bit = BIT(N+1)
ans = [None] * Q
last_idx = [-1] * (N+1)
j = 0
for r, l, i in rl:
    while j < r:
        if last_idx[c[j]] == -1:
            last_idx[c[j]] = j
        else:
            bit.add(last_idx[c[j]]+1, -1)
            last_idx[c[j]] = j
        bit.add(j+1, 1)
        j += 1
    ans[i] = bit.sum(r) - bit.sum(l-1)
print(*ans, sep='\n')
            

### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    N, Q = map(int, input().split())
    bit = [0] * (N+1)

    def add(x, a):
        while x <= N:
            bit[x] += a
            x += x & -x

    def sum(x):
        ret = 0
        while x != 0:
            ret += bit[x]
            x -= x & -x
        return ret

    c = list(map(int, input().split()))
    lr = [None] * Q
    for i in range(Q):
        l, r = map(int, input().split())
        lr[i] = (i, l, r)
    lr.sort(key=lambda x: x[2])
    ans = [None] * Q
    last_idx = [-1] * (N+1)
    j = 0
    for i, l, r in lr:
        while j < r:
            if last_idx[c[j]] == -1:
                last_idx[c[j]] = j
            else:
                add(last_idx[c[j]]+1, -1)
                last_idx[c[j]] = j
            add(j+1, 1)
            j += 1
        ans[i] = sum(r) - sum(l-1)
    for a in ans:
        print(a)
            
if __name__ == "__main__":
    main()
### BUGGY CODE ###

import collections

class Node():
  def __init__(self, num):
    self.num = num
    self.count = 0
    self.nexts = []
    self.checked = False
  def add_nexts(self, node):
    self.nexts.append(node)
  def counter(self, n):
    self.count += n
  def __repr__(self):
    return str(self.num)
  def __str__(self):
    return str(self.num)

N, Q = list(map(int, input().split()))
node_list = [Node(i) for i in range(0, N+1)]
for i in range(0, N-1): 
  a, b = list(map(int, input().split()))
  node_list[a].add_nexts(node_list[b])
  node_list[b].add_nexts(node_list[a])
for i in range(0, Q):
  p, x = list(map(int, input().split()))
  node_list[p].counter(x)
q = collections.deque()
q.append(node_list[1])
while q:
  node = q.pop()
  node.checked = True
  for nexts_node in node.nexts:
    if nexts_node.checked:
      continue
    nexts_node.counter(node.count)
    q.append(nexts_node)
print(*[node.count for node in node_list[1:]])
               

### FIXED CODE ###

import collections

n,q=map(int, input().split())
cnt=[0]*(n+1) # 添字で指定しやすいように一つ多い １以降を使用する
g=[[] for _ in range(n+1)]
for _ in range(n-1):
  a,b=map(int, input().split())
  g[a].append(b)
  g[b].append(a)
for _ in range(q):
  v,val=map(int, input().split())
  cnt[v]+=val
q=collections.deque()
q.append(1)
checked_=[0]*(n+1)
while q:
  v=q.pop()
  checked_[v]=1
  for u in g[v]:
    if checked_[u]==1:
      continue
    cnt[u]+=cnt[v]
    q.append(u)
print(*cnt[1:])
### BUGGY CODE ###

N=int(input())
for h in range(1,3501):
    for n in range(h,3501):
        if 4*h*n-N*n-N*h!=0:
            w=(N*h*n)/(4*h*n-N*n-N*h)
            if w>0 and w==int(w):
                print(h,n,int(w))
                exit()

### FIXED CODE ###

N=int(input())
for h in range(1,3501):
    for n in range(h,3501):
        if 4*h*n>N*n+N*h:
            w=(N*h*n)/(4*h*n-N*n-N*h)
            if w==int(w):
                print(h,n,int(w))
                exit()
### BUGGY CODE ###

from collections import deque

N = int(input())

G = set()
for _ in range(N-1):
    a, b, c = map(int, input().split())
    G.add((a, b, c))

Q, K = map(int, input().split())

visited = [False] * N
visited[K-1] = True

distance = [-1]*N

que = deque([(K, 0)])
while que:
    cur, d = que.popleft()
    distance[cur-1] = d

    for a, b, c in G:
        if a == cur and visited[b-1] is False:
            visited[b-1] = True
            que.append((b, d+c))
        elif b == cur and visited[a-1] is False:
            visited[a-1] = True
            que.append((a, d+c))

for i in range(Q):
    x, y = map(int, input().split())
    print(distance[x-1]+distance[y-1])


### FIXED CODE ###

from collections import deque

N = int(input())

G = [set() for i in range(N)]
for _ in range(N-1):
    a, b, c = map(int, input().split())
    G[a-1].add((b, c))
    G[b-1].add((a, c))

Q, K = map(int, input().split())

visited = [False] * N
visited[K-1] = True

distance = [-1]*N

que = deque([(K, 0)])
while que:
    cur, d = que.popleft()
    distance[cur-1] = d

    for nx, nd in G[cur-1]:
        if visited[nx-1] is False:
            visited[nx-1] = True
            que.append((nx, d+nd))

for i in range(Q):
    x, y = map(int, input().split())
    print(distance[x-1]+distance[y-1])
### BUGGY CODE ###

N = int(input())
A = [int(input()) for _ in range(N)]
 
s = []
cnt = 0
n = 1
f = False
while True:
  s.append(n)
  cnt += 1
  n = A[n - 1]
  if n == 2:
    f = True
    break
  elif s.count(n) != 0:
    break
print(cnt if f else -1)

### FIXED CODE ###

N = int(input())
A = [int(input()) for _ in range(N)]

cnt = 0
n = 1
f = False
while cnt <= N:
  cnt += 1
  n = A[n - 1]
  if n == 2:
    f = True
    break
print(cnt if f else -1)
### BUGGY CODE ###

N,K=map(int,input().split())
_=input().split()
S=[]
for s in _:
    S.append(int(s))

# K=4
# S=[17, 13, 13, 12, 15, 20, 10, 13, 17, 11]
# K=3
# S=[1,2,2,4,5]

EVlist=[]

for i in range(len(S)):
    tempEV=(S[i]*(S[i]+1))/2/S[i]
    EVlist.append(tempEV)

maxEVsum=0

for j in range(len(EVlist)):
    tempEVsum=sum(EVlist[j:j+K])
    if maxEVsum<tempEVsum:
        maxEVsum=tempEVsum

print(maxEVsum)

### FIXED CODE ###

N,K=map(int,input().split())
_=input().split()
S=[]
for s in _:
    S.append((int(s)+1)/2) #初めから期待値で配列作成

maxsum=sum(S[0:K])
tempsum=maxsum

for i in range(N-K):
    tempsum=tempsum-S[i]+S[i+K]
    if maxsum<tempsum:
        maxsum=tempsum
    else:
        pass

print(maxsum)
### BUGGY CODE ###

def f(n, D, p, q):
    for i in range(n-2):
        r = p ^ q
        if (r in D) and (D[r] > 0):
            D[r] -= 1
        else:
            return -1
        p, q = q, r
    return p ^ q

def solve(n, a):
    D = {}
    for x in a:
        if not x in D:
            D[x] = 0
        D[x] += 1
    D[a[0]] -= 1
    for i in range(1, n):
        D[a[i]] -= 1
        ok = f(n, D.copy(), a[0], a[i]) == a[0]
        D[a[i]] += 1
        if ok:
            return "Yes"
    return "No"

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

### FIXED CODE ###

def solve(n, a):
    p = 0
    for x in a:
        p ^= x
    return "Yes" if p == 0 else "No"

n = int(input())
a = list(map(int, input().split()))
print(solve(n, a))
### BUGGY CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")



n, m = map(int, input().split())
from collections import defaultdict
ns = defaultdict(set)
pps = [set() for _ in range(n)]
for i in range(n-1+m):
    a,b = map(int, input().split())
    a -= 1
    b -= 1
    ns[a].add(b)
    pps[b].add(a)

for i,s in enumerate(pps):
    if not s:
        r = i
        
ps = [None] * n    
def bfs(start):
    from queue import deque
    q = deque([start])
    seen = [None] * n
    seen[start] = 0
    while q:
        u = q.pop()
        d = seen[u]
        for v in ns[u]:
            if seen[v] is None or seen[v]<d+1:
                seen[v] = d + 1
                q.appendleft(v)
                ps[v] = u+1
    return seen

ds = bfs(r)
ps[r] = 0
write("\n".join(map(str, ps)))

### FIXED CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n, m = map(int, input().split())
from collections import defaultdict
ns = defaultdict(set)
pps = [set() for _ in range(n)]
for i in range(n-1+m):
    a,b = map(int, input().split())
    a -= 1
    b -= 1
    ns[a].add(b)
    pps[b].add(a)

for i,s in enumerate(pps):
    if not s:
        r = i
        
def tps(start):
    q = [start]
    # 行きがけ順
    seen = [None] * n
    # 帰りがけ順
    done = [None] * n
    d0 = 0
    d1 = n
    seen[start] = d0
    while q:
        u = q.pop()
        if u>=0:
            q.append(~u)
            for v in ns[u]:
                if seen[v] is None:
                    d0 += 1
                    seen[v] = d0
                    q.append(v)
        else:
            d1 -= 1
            done[~u] = d1            
    return seen, done

done = [None]*n
val = n
def dfs(u, val):
    for v in ns[u]:
        if done[v] is not None:
            continue
        val = dfs(v, val)
    val = val - 1
    done[u] = val
    return val

# seen, done = tps(r)
dfs(r, n)
ps = [-1] * n
ps[r] = 0
for i in range(n):
    if i==r:
        continue
    val = max(pps[i], key=lambda item: done[item])
    ps[i] = val+1
write("\n".join(map(str, ps)))
### BUGGY CODE ###

n = int(input())
a=1
x=0
for i in range(n-1):
    b=1
    while a*b < n:
        x += 1
        b += 1
    a += 1
print(x)

### FIXED CODE ###

n = int(input())
a=1
x=0
for i in range(n-1):
    x += (n-1)//a
    a += 1
print(x)
### BUGGY CODE ###

# 新ステージでは、一度全部どんぐりに直してから換金を始めるとしてよい

def F(N, A, B):
  # N個のどんぐりを、Aで換金してからBに持っていく
  # Bでどんぐりに直す
  dp = [0] * (N+1)
  for n in range(N+1):
    x = n
    for j in range(3):
      if n >= A[j]:
        y = dp[n-A[j]] + B[j]
        if x < y:
          x = y
    dp[n] = x
  return dp[N]

N = int(input())
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]

answer = F(F(N,A,B),B,A)
print(answer)

### FIXED CODE ###

# 新ステージでは、一度全部どんぐりに直してから換金を始めるとしてよい

def F(N, A, B):
  # N個のどんぐりを、Aで換金してからBに持っていく
  # Bでどんぐりに直す
  dp = [0] * (N+1)
  for n in range(N+1):
    x = n
    for j in range(3):
      if n >= A[j]:
        y = dp[n-A[j]] + B[j]
        if x < y:
          x = y
    dp[n] = x
  return dp[N]

N = int(input())
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]

answer = F(F(N,A,B),B,A)
print(answer)
### BUGGY CODE ###

#!/usr/bin/env python

from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(1000000)

INF = 10 ** 18

N, K = map(int, raw_input().split())
h = map(int, raw_input().split())

DP = [0] + [INF] * N

for i in range(1, N):
    for j in range(min(i, K)):
        DP[i] = min(DP[i], DP[i - j - 1] + abs(h[i] - h[i - j - 1]))

print DP[N - 1]

### FIXED CODE ###

#!/usr/bin/env python

from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(1000000)

INF = 10 ** 18

N, K = map(int, raw_input().split())
h = map(int, raw_input().split())

DP = [0] + [INF] * N

for i in range(1, N):
    for j in range(min(i, K)):
        DP[i] = min(DP[i], DP[i - j - 1] + abs(h[i] - h[i - j - 1]))

print DP[N - 1]
### BUGGY CODE ###

# coding: UTF-8
import sys
#sys.setrecursionlimit(n)
import heapq
import re
import bisect
import random
import math
import itertools
from collections import defaultdict, deque
from copy import deepcopy
from decimal import *

readl= lambda: list(map(int, sys.stdin.readline().split()))
readt= lambda: tuple(map(int, sys.stdin.readline().split()))
read = lambda: sys.stdin.readline().rstrip()
readi = lambda: int(read())
readmi = lambda: map(int, sys.stdin.readline().split())
readms = lambda: map(str, sys.stdin.readline().split())

n, m = readmi()
a = readl()
a.sort()
d = defaultdict(int)
for i in a:
    if d[i]:
        d[i] += 1
    else:
        d[i] = 1

for i in range(m):
    x, y = map(int, input().split())
    for j in sorted(d):
        if y > j:
            w = d[j]
            ww = x
            d[j] -= ww
            x -= w
            d[y] += min(ww, w)
            if d[j] <= 0:
                del d[j]
            if x <= 0:
                break
        else:
            break
count = 0
for i in d:
    count += max(int(d[i]) * int(i),0)
print(count)

### FIXED CODE ###

# coding: UTF-8
import sys
#sys.setrecursionlimit(n)
import heapq
import re
import bisect
import random
import math
import itertools
from collections import defaultdict, deque
from copy import deepcopy
from decimal import *

readl= lambda: list(map(int, sys.stdin.readline().split()))
readt= lambda: tuple(map(int, sys.stdin.readline().split()))
read = lambda: sys.stdin.readline().rstrip()
readi = lambda: int(read())
readmi = lambda: map(int, sys.stdin.readline().split())
readms = lambda: map(str, sys.stdin.readline().split())

n, m = readmi()
a = readl()
d = defaultdict(int)
k = []
for i in a:
    heapq.heappush(k,(-i, 1))
for i in range(m):
    x, y = readmi()
    heapq.heappush(k,(-y, x))
count = 0
while(n > 0):
    x, y = heapq.heappop(k)
    count += min(y * (-x), n * (-x))
    n = max(n - y, 0)
print(count)
### BUGGY CODE ###

N,K = map(int, input().split())
A = [int(i) for i in input().split()]
p = 1
p_hist = []
p_hist_index = [-1] * (N+1)
while p not in p_hist:
    p_hist_index[p] = len(p_hist)
    p_hist.append(p)
    p = A[p-1]
end_loop = p_hist[-1]
end_loop_idx = p_hist_index[end_loop]
start_loop = A[end_loop - 1]
start_loop_idx = p_hist_index[start_loop]
if K < start_loop_idx:
    print(p_hist[K])
else:
    print(p_hist[(K-start_loop_idx)%(end_loop_idx-start_loop_idx+1)+start_loop_idx])


### FIXED CODE ###

N,K = map(int, input().split())
A = list(map(int, input().split()))
p = 1
p_hist = []
p_hist_set = set()
p_hist_index = [-1] * (N+1)
while p not in p_hist_set:
    p_hist_index[p] = len(p_hist)
    p_hist.append(p)
    p_hist_set.add(p)
    p = A[p-1]
end_loop = p_hist[-1]
end_loop_idx = p_hist_index[end_loop]
start_loop = A[end_loop - 1]
start_loop_idx = p_hist_index[start_loop]
if K < start_loop_idx:
    print(p_hist[K])
else:
    print(p_hist[(K-start_loop_idx)%(end_loop_idx-start_loop_idx+1)+start_loop_idx])
### BUGGY CODE ###

num = int(input())
pole_list = sorted([int(item) for item in input().split()])

import numpy as np
pole_list = np.array(pole_list)

cnt = 0

for i in range(num):
    for j in range(i + 1, num):
        cnt += len(pole_list[pole_list < pole_list[i] + pole_list[j]]) - (j + 1)

print(cnt)

### FIXED CODE ###

from bisect import bisect_left
 
N = int(input())
Lmat = [int(n) for n in input().split()]
Lmat.sort()
 
sum = 0

for i in range(N):
    for j in range(i + 1, N):
        sum += bisect_left(Lmat, Lmat[i]+Lmat[j]) - (j + 1)
        
print(sum)
### BUGGY CODE ###

from collections import deque
import math

h, w = list(map(int, input().split()))
SHWs = [input() for i in range(h)]

def bfs(sy, sx, gy, gx):
    visited = [[-1]*w for i in range(h)]
    visited[sy][sx] = 0
    que = deque([[sy, sx]])
    while que:
        
        y,x = que.popleft()
        for i, j in [(1,0),(0,1),(-1,0),(0,-1)]:
            next_y, next_x = y+i, x+j
            # print(visited)
            if next_y < 0 or next_x < 0 or next_y > h-1 or next_x > w-1:
                continue
            if SHWs[next_y][next_x] == '.' and (visited[next_y][next_x] == -1 or visited[next_y][next_x] > visited[y][x]+1):
                visited[next_y][next_x] = visited[y][x] + 1
                que.append([next_y, next_x])
    
    return visited[gy][gx]

            
ans = 0
for sy in range(h):
    for sx in range(w):
        for gy in range(h):
            for gx in range(w):
                if sy == gy and sx == gx or SHWs[sy][sx] == '#' or SHWs[gy][gx] == '#':
                    continue
                count = bfs(sy=sy, sx=sx, gy=gy, gx=gx) 
                if count > ans:
                    ans = count


print(ans)



### FIXED CODE ###

from collections import deque
import numpy as np
import math

h, w = list(map(int, input().split()))
SHWs = [input() for i in range(h)]

def bfs(sy, sx):
    visited = [[-1]*w for i in range(h)]
    visited[sy][sx] = 0
    que = deque([[sy, sx]])
    while que:
        
        y,x = que.popleft()
        for i, j in [(1,0),(0,1),(-1,0),(0,-1)]:
            next_y, next_x = y+i, x+j
            # print(visited)
            if next_y < 0 or next_x < 0 or next_y > h-1 or next_x > w-1:
                continue
            if SHWs[next_y][next_x] == '.' and (visited[next_y][next_x] == -1 or visited[next_y][next_x] > visited[y][x]+1):
                visited[next_y][next_x] = visited[y][x] + 1
                que.append([next_y, next_x])
    
    return np.amax(np.array(visited))

            
ans = 0
for sy in range(h):
    for sx in range(w):
        if SHWs[sy][sx] == '#':
            continue
        count = bfs(sy=sy, sx=sx)

        if count > ans:
            ans = count


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

s = input()
MOD = 2019
a =[0]*MOD
a[0] = 1
c_ = 0
ans = 0
t = 1
for i in reversed(s):
  c = (c_+int(i)*t)%MOD
  a[c] += 1
  t *= 10
#  t %= MOD
  c_ = c
for i in a:
  ans += i*(i-1)//2
print(ans)


### FIXED CODE ###

s = input()
MOD = 2019
a =[0]*MOD
a[0] = 1
c_ = 0
ans = 0
t = 1
for i in reversed(s):
  c = (c_+int(i)*t)%MOD
  a[c] += 1
  t *= 10
  t %= MOD
  c_ = c
for i in a:
  ans += i*(i-1)//2
print(ans)
### BUGGY CODE ###

N, K = map(int, input().split())
H = list(map(int, input().split()))
ans = sum(H)
for n in range(1,min(N+1,K+1)):
    ans -= sorted(H)[-n]
print(ans)


### FIXED CODE ###

N, K = map(int, input().split())
H = list(map(int, input().split()))

cnt = 0
H.sort(reverse=True)

if K >= N:
    print(0)
else:
    print(sum(H[K:]))
### BUGGY CODE ###

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

for q in quiz:
  l = q[0]
  r = q[1]
  print(S[l-1:r].count("AC"))

### FIXED CODE ###

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

t = [0] * (N+1)
for i in range(N):
  t[i+1] = t[i] + (1 if S[i:i+2] == "AC" else 0)

for q in quiz:
  l = q[0]
  r = q[1]
  print(t[r-1] - t[l-1])
### BUGGY CODE ###

class mod_combination:
    def __init__(self, N, mod):
        self.fac = [1] * (N + 1)
        for i in range(1, N + 1):
            self.fac[i] = (self.fac[i - 1] * i) % mod
        self.invmod = [1] * (N + 1)
        self.invmod[N] = pow(self.fac[N], mod - 2, mod)
        for i in range(N, 0, -1):
            self.invmod[i - 1] = (self.invmod[i] * i) % mod
        
    def calc(self, n, k): # nCk
        return self.fac[n] * self.invmod[k] % mod * self.invmod[n - k] % mod


n, m, k = map(int, input().split())
mod = 998244353
C = mod_combination(n, mod)
ans = 0
color = m
for x in reversed(range(n)):
    if x <= k:
        ans += C.calc(n - 1, x) * color
        ans %= mod
    color *= m - 1
print(ans)


### FIXED CODE ###

mod = 998244353

class mod_combination:
    def __init__(self, N):
        self.fac = [1] * (N + 1)
        for i in range(1, N + 1):
            self.fac[i] = (self.fac[i - 1] * i) % mod
        self.invmod = [1] * (N + 1)
        self.invmod[N] = pow(self.fac[N], mod - 2, mod)
        for i in range(N, 0, -1):
            self.invmod[i - 1] = (self.invmod[i] * i) % mod
        
    def calc(self, n, k): # nCk
        return self.fac[n] * self.invmod[k] % mod * self.invmod[n - k] % mod


n, m, k = map(int, input().split())
C = mod_combination(n)
ans = 0
for x in range(k + 1):
    ans = (ans + C.calc(n - 1, n - x - 1) * m * pow(m - 1, n - x - 1, mod) % mod) % mod
print(ans)
### BUGGY CODE ###

n=int(input())
def sqdivlist(n):
    lista=[]
    for i in range(1,int((n**0.5)//1)+1):
        if n%i==0:
            lista.append(str(i))
    return (lista)
lista2=[]
for j in range(len(sqdivlist(n))):
    lista2.append(int(n/int((sqdivlist(n))[j])))
ans=[]
for k in range(len(sqdivlist(n))):
    ans.append(max(int(len(str(sqdivlist(n)[k]))), int(len(str(lista2[k])))))
print(min(ans))


### FIXED CODE ###

from functools import reduce
n=int(input())
def sqdivlist(n):
    lista=[]
    for i in range(1,int((n**0.5)//1)+1):
        if n%i==0:
            lista.append(str(i))
    return (lista)
t=len(sqdivlist(n))
u=(sqdivlist(n))
lista2=[]
ans=[]
for j in range(t):
    lista2.append(int(n/int(u[j])))
    ans.append(max(len(str(u[j])),(len(str(lista2[j])))))
print(min(ans))
### BUGGY CODE ###

import functools
import operator
n = int(input())
a = list(map(int,input().split()))
lim = 10**18
ans = functools.reduce(operator.mul, a)

if ans > lim:
  ans = -1
    
print(ans)

### FIXED CODE ###

import numpy as np
n = int(input())
a = np.array(list(map(int,input().split())))
b = np.sqrt(a)

lim = 10**9
lim_1 = 10**18
ans_1 = np.prod(b)
ans = np.prod(a)

if ans_1 > lim:
  ans = -1
elif ans_1 < 0:
  ans = -1
    
if ans > lim_1:
  ans = -1
elif ans < 0:
  ans = -1
  
print(ans)
### BUGGY CODE ###

while 1:
    n = input()
    if n == 0:
        break
    D = {x**2 % n for x in xrange(1, n)}
    C = [0]*((n-1)/2)
    for p in D:
        for q in D:
            if p == q:
                continue
            g = (p - q) % n
            if g > (n - 1)/2:
                g = n - g
            C[g-1] += 1
    print "\n".join(map(str, C))

### FIXED CODE ###

import sys
readline = sys.stdin.readline
write = sys.stdout.write

def solve():
    N = int(readline())
    if N == 0:
        return False
    if N == 1:
        return True
    *S, = set(i**2 % N for i in range(1, N))
    S.sort()
    L = len(S)
    C = [0]*N
    D = [0]*((N-1)//2)
    for i in range(L):
        a = S[i]
        for b in S[:i]:
            C[a - b] += 2
    for i in range(1, N):
        D[min(i, N-i)-1] += C[i]
    write("\n".join(map(str, D)))
    write("\n")
    return True
while solve():
    ...
### BUGGY CODE ###

import sys 
s=input()
t=input()
n=len(s)
for i in range(n):
        for j in range(i,n):
          if s[i]==s[j] and t[i]!=t[j]:
              print("No")
              exit()
          if s[i]!=s[j] and t[i]==t[j]:
              print("No")
              exit()
print("Yes")

### FIXED CODE ###

s = input()
t = input()
n = len(s)
r=[-1]*26
r2=[-1]*26
abcd = 'abcdefghijklmnopqrstuvwxyz'

def f(l,l2,R):
  for i in range(n):
    if R[abcd.index(l[i])]==-1 or R[abcd.index(l[i])]==l2[i]:
       R[abcd.index(l[i])]=l2[i]
    else:
       print("No")
       exit()

f(s,t,r)
f(t,s,r2)
print("Yes")
### BUGGY CODE ###

# coding: utf-8

def main():
    n = input()
    ans = 0
    for i in n:
        ans += int(n)
    if ans % 9 == 0:
        print('Yes')
    else:
        print('No')

main()


### FIXED CODE ###

# coding: utf-8

def main():
    n = int(input())
    if n % 9 == 0:
        print('Yes')
    else:
        print('No')

main()
### BUGGY CODE ###

import numpy as np
n=int(input())
s=np.zeros((100001,12),dtype='int16')
a=[1,6,9,36,81,216,729,1296,6561,7776,46656,59049]

for i in range(n+1):
    s[i][0]=i
for i in range(1,12):
    for j in range(n+1):
        s[j][i]=s[j][i-1]
        if a[i]<=j:
            if s[j][i]>s[j-a[i]][i]+1:
                s[j][i]=s[j-a[i]][i]+1
print(s[n][11])


### FIXED CODE ###

n=int(input())
s=[i for i in range(n+1)]
a=[1,6,9,36,81,216,729,1296,6561,7776,46656,59049]
for i in range(n+1):
    s[i]=i
for i in range(1,12):
    if a[i]<=n :
        k=a[i]
        for j in range(k,n+1):
            if s[j]>s[j-k]+1:
                s[j]=s[j-k]+1
print(s[n])