Harryxun/stf_run huggingface dataset:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value

## BFS

#入力受け取り
N, Q = mi()
x = li2(N-1)

cnt = [0]*N
for i in range(Q):
    p0, p1 = mi()
    cnt[p0-1] += p1

#隣接リスト作成
adj = [[] for i in range(N)]
for i in range(N-1):
    x[i][0] -= 1
    x[i][1] -= 1
    adj[x[i][0]].append(x[i][1])
    adj[x[i][1]].append(x[i][0])

ans = [0]*N

def dfs(fr, nx):
    global ans
    ans[nx] += ans[fr] + c[nx]
    for v in adj[nx]:
        if v != fr:
            dfs(nx, v)

dfs(0, 0)

for k in ans:
    print(k, '', end='')

### FIXED CODE ###

import sys
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
'''
from collections import deque
N, Q = mi()
D = li2(N-1)
px = li2(Q)
que = deque()

adj = [[] for i in range(N+1)]

for i in range(N-1):
    adj[D[i][0]].append(D[i][1])

ans = [0]*(N+1)
for j in range(Q):
    ind, a = px[j][0], px[j][1]
    que.append(ind)
    while(que!=deque()):
        v = que.popleft()
        ans[v] += a
        for e in adj[v]:
            que.append(e)


for i in range(1, N+1):
    print(ans[i], ' ', end='')
'''

from collections import deque
sys.setrecursionlimit(10**9)

#入力受け取り
N, Q = mi()
x = li2(N-1)
#p = li2(Q)

cnt = [0]*N
for i in range(Q):
    p0, p1 = mi()
    cnt[p0-1] += p1

#隣接リスト作成
adj = [[] for i in range(N)]
for i in range(N-1):
    x[i][0] -= 1
    x[i][1] -= 1
    adj[x[i][0]].append(x[i][1])
    adj[x[i][1]].append(x[i][0])

que = deque()
ans = [0]*N

#for a in range(N):
que.append((0, 0))
num = 0
while que!=deque():
    v = que.popleft()
    ans[v[1]] = ans[v[0]] + cnt[v[1]]
    for next in adj[v[1]]:
        if next != v[0]:
            que.append((v[1], next))

for k in ans:
    print(k, '', end='')
n = int(input())
x = int(input(),2)

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

x_pop = popcount(x)
for i in reversed(range(0,n)):
    bit = x&(1<<i)
    if bit:
        tmp_pop = x_pop - 1
    else:
        tmp_pop = x_pop + 1
    tmp = bit % tmp_pop
    if tmp == 0:
        print(0)
        continue
    if tmp < 0:
        print(1)
        continue
    cnt = 2
    tmp = tmp % popcount(tmp)
    while tmp > 0:
        cnt += 1
        tmp %= popcount(tmp)
    print(cnt)

### 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)
import bisect
a, b, q = map(int, input().split())
inf = 10**18
s = [-inf] + [int(input()) for i in range(a)] + [inf]
t = [-inf] + [int(input()) for i in range(b)] + [inf]

for i in range(q):
  x = int(input())
  b, d = bisect.bisect_right(s, x), bisect.bisect_right(t, x)
  res = inf
  for S in [s[b-1], s[b]]:
    for T in [t[b-1], t[b]]:
      d1, d2 = abs(S-x) + abs(T-S), abs(T-x) + abs(S-T)
      res = min(d1, d2, res)
  print(res)


### FIXED CODE ###

import bisect
a, b, q = map(int, input().split())
inf = 10**18
s = [-inf] + [int(input()) for i in range(a)] + [inf]
t = [-inf] + [int(input()) for i in range(b)] + [inf]

for i in range(q):
  x = int(input())
  b, d = bisect.bisect_right(s, x), bisect.bisect_right(t, x)
  res = inf
  for S in [s[b-1], s[b]]:
    for T in [t[d-1], t[d]]:
      d1, d2 = abs(S-x) + abs(T-S), abs(T-x) + abs(S-T)
      res = min(d1, d2, res)
  print(res)
n = int(input())
x_bin = input()
x = int(x_bin, 2)

def solve(a, pc):
    ans = 0
    while a != 0:
        a = a % pc
        pc = bin(a).count('1')
        ans += 1
    return ans
        
pc = bin(x).count('1')
pc_p = pc + 1
pc_m = pc - 1

for i in reversed(range(n)):
    if x_bin[n-i-1] == '1':
        a = (x - pow(2, i)) % pc_m
        print(solve(a, bin(a).count('1')) + 1)
    else:
        a = (x + pow(2, i)) % pc_p
        print(solve(a, bin(a).count('1')) + 1)


### FIXED CODE ###

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

pc = x_bin.count('1')
pc_p = pc + 1
pc_m = pc - 1

if pc == 1:
    for i, v in enumerate(x_bin):
        if v == '1':
            print(0)
        else:
            if i != n-1:
                if x_bin[-1] == '0':
                    print(1)
                else:
                    print(2)
            else:
                print(2)
    exit()

p = {0: 1}
m = {0: 1}
for i in range(1, n):
    p[i] = p[i-1]*2 % pc_p
    m[i] = m[i-1]*2 % pc_m

rest = {0: 0}
for i in range(1, pc + 1):
    rest[i] = rest[i % bin(i).count('1')] + 1

x_p = x % pc_p
x_m = x % pc_m

for i in range(n, 0, -1):
    if x_bin[n-i] == '1':
        a = (x_m - m[i-1]) % pc_m
        print(rest[a] + 1)
    else:
        a = (x_p + p[i-1]) % pc_p
        print(rest[a] + 1)
N = [int(e) for e input().split()]
print(N[0]*N[1])

### FIXED CODE ###

N = [int(e) for e in input().split()]
print(N[0]*N[1])
n = input()
 
d = [0 for i in range(n)]
f = [0 for i in range(n)]
X = [0 for i in range(n)]
M = [[0 for i in range(n)] for j in range(n)]
color = [0 for i in range(n)]
t = 0
 
def DFS_v(u):
    color[u] = 1
    t += 1
    d[u] = t
    for v in range(n):
        if M[u][v] == 1 and color[v] == 0:
            DFS_visit(v)
    color[u] == 2
    t += 1
    f[u] = t
 
def DFS():
    for u in range(n):
        if color[u] == 0:
            DFS_v(u)
    for u in range(n):
        print "%d %d %d" %(u+1, d[u], f[u])
     
for i in range(n):
    X = map(int, raw_input().split())
    for j in range(X[1]):
        M[X[0]-1][X[2+j]-1] = 1
 
DFS()
    

### FIXED CODE ###

n = int(raw_input())
 
d = [0 for i in range(n)]
f = [0 for i in range(n)]
G = [0 for i in range(n)]
M = [[0 for i in range(n)] for j in range(n)]
col = [0 for i in range(n)]
t = [0]
 
def DFS_visit(u):
    col[u] = 1
    t[0] += 1
    d[u] = t[0]
    for v in range(n):
        if M[u][v] == 1 and col[v] == 0:
            DFS_visit(v)
    col[u] = 2
    t[0] += 1
    f[u] = t[0]
 
def DFS():
    for u in range(n):
        if col[u] == 0:
            DFS_visit(u)
    for u in range(n):
        print'{0} {1} {2}'.format(u+1, d[u], f[u])
     
for i in range(n):
    X = map(int, raw_input().split())
    for j in range(X[1]):
        M[X[0]-1][X[2+j]-1] = 1
 
DFS()
n,x=map(int,input().split())
a=list(map(int,input().split()))
dp=[-1]*n
dp[0]=0
if n<x:
    x=n
for i in range(1,x+1):
    dp[i]=abs(a[i]-a[0])

for i in range(x+1,n):
    min1=10**9
    for j in range(i-(x),i):  
        if min1>dp[j]+abs(a[j]-a[i]):               
            min1=dp[j]+abs(a[j]-a[i])
    dp[i]=min1
print(dp[-1])

### FIXED CODE ###

n,x=map(int,input().split())
a=list(map(int,input().split()))
dp=[-1]*n
dp[0]=0
if n<=x:
    x=n-1
for i in range(1,x+1):
    dp[i]=abs(a[i]-a[0])

for i in range(x+1,n):
    min1=10**9
    for j in range(i-(x),i):  
        if min1>dp[j]+abs(a[j]-a[i]):               
            min1=dp[j]+abs(a[j]-a[i])
    dp[i]=min1
print(dp[-1])
N = int(input())
T = [int(input() for _ in range(N))]

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

def lcm(a,b):
    return a*b//gcd(a,b)

ans=1
for i in range(T):
    ans = lcm(ans,i)
    
print(ans)


### FIXED CODE ###

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

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

def lcm(a,b):
    return a*b//gcd(a,b)

ans=1
for i in T:
    ans = lcm(ans,i)

print(ans)
N,X,D=map(int,input().split())
f,c,r={},[0]*9**8,0
for x,y,z in sorted((((N-k)*j+~-k)*k//2+k*X//D,j,k*X%D) if D else(0,j,k*(X!=0))for k in range(N+1)for j in[0,2]):
 if c[z]+y<1:
  f[z]=x
 r+=(x-f[z]+1)*(c[z]<y)
 c[z]-=y-1
print(r)

### FIXED CODE ###

N, X, D = map(int, input().split())
if D == 0:
    r = N+1
    if X == 0:
        r = 1
    print(r)
else:
    if D < 0:
        X, D = -X, -D
    d = dict()
    for k in range(N+1):
        M = (k*X) % D
        F = (k*X)//D + ((k-1)*k)//2 #(1..k-1)
        L = (k*X)//D + (2*N-k-1)*k//2# (N-k..N-1)
        if M not in d:
            d[M] = list()
        d[M].append((F, 0))
        d[M].append((L, 1))
    r = 0
    for m in d:
        d[m] = sorted(d[m])
        fc = 0
        f = 0
        for x in d[m]:
            if not x[1]:
                fc += 1
                if fc == 1:
                    f = x[0]
            if x[1]:
                fc -= 1
                if fc == 0:
                    r += x[0] - f + 1
    print(r)
n, r = map(int, input().split())
print(r + 100*max(10-k, 0))

### FIXED CODE ###

n, r = map(int, input().split())
print(r + 100*max(10-n, 0))
N = int(input())
edges = [[] for _ in range(N)]
for _ in range(N-1):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    edges[a].append((b, c))
    edges[b].append((a, c))

depth = [0] * N

def dfs(v, p, d):
    depth[v] = d
    for e in edges[v]:
        if e[0] == p:
            continue
        dfs(e[0], v, d + e[1])


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

dfs(K, -1, 0)

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



### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 7)

N = int(input())
edges = [[] for _ in range(N)]
for _ in range(N-1):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    edges[a].append((b, c))
    edges[b].append((a, c))

depth = [0] * N

def dfs(v, p, d):
    depth[v] = d
    for e in edges[v]:
        if e[0] == p:
            continue
        dfs(e[0], v, d + e[1])


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

dfs(K, -1, 0)

for i in range(Q):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    print(depth[x] + depth[y])
import math
a,b,n = map(int, input().split())

c = b-1

ans = math.floor(a * c /b) - a * floor(c/b)

print(ans)

### FIXED CODE ###

import math
a,b,n = map(int, input().split())
if b > n:
    c = n
else:
    c = b-1
ans = math.floor(a * c /b) - a * math.floor(c/b)

print(ans)
import sys
import math

a,b,k = list(map(int, input().split()))
lis = range(a,a+k) + range(b-k+1, b+1)
for i in range(len(lis)):
    print(lis[i])

### FIXED CODE ###

import sys
import math

a,b,k = list(map(int, input().split()))
if b-a+1 <= k:
    for i in range(a,b+1):
        print(i)
else:
    lis = list(range(a,a+k))
    lis.extend(list(range(b-k+1, b+1)))
    lis = list(set(lis))
    lis.sort()
    for i in range(len(lis)):
        print(lis[i])
n,q=map(int,input().split())
l=[[] for i in range(n)]
for i in range(n-1):
  a,b=map(int,input().split())
  l[a-1].append(b-1)
  l[b-1].append(a-1)
ans=[0 for i in range(n)]
for i in range(q):
  p,x=map(int,input().split())
  ans[p-1]+=x
def dsf(index,u):
  for i in l[index]:
    if i==u:continue
    ans[i]+=ans[index]
    dsf(i,index)
dsf(0,0)
print(' '.join(str(j) for j in ans))

### FIXED CODE ###

import sys
sys.setrecursionlimit(500000)
input = sys.stdin.readline
n,q=map(int,input().split())
l=[[] for i in range(n)]
for i in range(n-1):
  a,b=map(int,input().split())
  l[a-1].append(b-1)
  l[b-1].append(a-1)
px=[0]*n
for i in range(q):
  p,x=map(int,input().split())
  px[p-1]+=x
ans=[0]*n
def dsf(index,u):
  ans[index]=ans[u]+px[index]
  for i in l[index]:
    if i==u:continue
    dsf(i,index)
dsf(0,-1)
print(*ans)
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)

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

@lru_cache(maxsize=None)
def rec(n):
    if n == 0:
        return 0
    elif n == 1:
        return abs(h[1]-h[0])
    return min(abs(h[n]-h[n-1]) + rec(n-1), abs(h[n]-h[n-2]) + rec(n-2))

print(rec(n-1))


### FIXED CODE ###

n = int(input())
h = list(map(int, input().split()))
res = [0] * n

res[1] = abs(h[1] - h[0])
for i in range(2, n):
    res[i] = min(res[i-2] + abs(h[i] - h[i-2]),
                 res[i-1] + abs(h[i] - h[i-1]))

print(res[-1])
n, m = input().split()
print((n-1)*(m-1))

### FIXED CODE ###

n, m = map(int, input().split())
print((n-1)*(m-1))
import bisect
n,k = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
zero = bisect.bisect_left(a,0)
cnt = (10**8)*(10**5)
cnt = min(sum(a[zero:n]),-sum(a[0:zero]))
for i in range(1,zero):
    if cnt > -2*a[zero-i]+a[n-i]:
        cnt = -2*a[zero-i]+a[n-i]
    else:
        break
for i in range(1,zero):
    if cnt > -a[i]+2*a[zero+i]:
        cnt = -a[i]+2*a[zero+i]
    else:
        break
print(cnt)

### FIXED CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
c=10**10
for i in range(n-k+1):
    c=min(c,-a[i]+a[i+k-1]\
          +min(abs(a[i]),abs(a[i+k-1])))
print(c)
s = input().rstrip().split()
N,M = int(s[0]),int(s[1])

a=[]
for i in range(M):
  a.append(input().rstrip().split())

pen =0
AClist =[]
ACflag= [0]*N
#print(a,len(a))

for i in range(len(a)):
  if a[i][1] == "AC" and ACflag[int(a[i][0])] == 0:
    AClist.append(a[i])
    ACflag[int(a[i][0])] = 1
  if a[i][1] == "WA" and ACflag[int(a[i][0])] == 0:
    pen += 1

print(len(AClist),pen)

### FIXED CODE ###

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

lac = [0]*(N+1)
lpcnt = [0]*(N+1)

for i in range(M):
  s = input().split()
  n = int(s[0])
  if s[1] == "AC":
    lac[n] =1
    continue
  if s[1] == "WA" and lac[n] == 0:
    lpcnt[n] += 1

cnt = 0
for i in range(N+1):
  if lac[i] == 1:
    cnt += lpcnt[i]
  
print(sum(lac), end=" ")
print(cnt)
n, m = map(int, input().split())
friends = [set() for i in range(n)]


def dfs(i):
    ans[-1] += 1
    flg[i] = 1
    for j in friends[i]:
        if not flg[j]:
            dfs(j)
    return


for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    friends[a].add(b)
    friends[b].add(a)

flg = [0]*n
ans = []

for i in range(n):
    ans.append(0)
    if not flg[i]:
        dfs(i)

print(max(ans))


### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)

n, m = map(int, input().split())
friends = [[] for i in range(n)]


def dfs(i):
    ans[-1] += 1
    flg[i] = 1
    for j in friends[i]:
        if not flg[j]:
            dfs(j)
    return


for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    friends[a].append(b)
    friends[b].append(a)

flg = [0]*n
ans = []

for i in range(n):
    ans.append(0)
    if not flg[i]:
        dfs(i)

print(max(ans))
N = int(input())
nums =[]
count = 0
switch = False
for i in range(N):
    nums.append([int(x) for x in input().split()])

for j in nums:
    if j[0] == j[1]:
        count += 1
    elif j[0] != j[1]:
        count = 0
    if count == 3:
        switch = True
if switch == True:
    print("Yes")
elif switch == False:
    print("No")


### FIXED CODE ###

S = input()
if S[-1:] == "s":
  print(S+"es")
else:print(S+"s")
x = [input() for i in range(2)]
S = list(x[0])
T = list(x[1])
n = 0
n = len(S) - len(T) + 1
min = len(T)
 
for a in range(n):
  count = 0 
	for b in range(len(T)):
      if S[a+b] != T[b]:
        count += 1
  if count < min:
    min = count
print(min)

### FIXED CODE ###

x = [input() for i in range(2)]
S = x[0]
T = x[1]
moji = len(T)

for a in range(len(S) - len(T) + 1):
  count = 0
  for b in range(len(T)):
    
    if S[a+b] != T[b]:
      count += 1
  if count < moji:
    moji = count

print(moji)
import itertools
n = int(input())
p =[int(i) for i in input().split()]
q =[int(i) for i in input().split()]
a = 0
b = 0
cnt = 0

n_list = list(itertools.permutations(p1))
for i in n_list:
    if list(i)==p:
        a = cnt +1
    elif list(i)==q:
        b = cnt +1
    cnt += 1
        
print(abs(a-b))

### FIXED CODE ###

import itertools
n = int(input())
p =[int(i) for i in input().split()]
q =[int(i) for i in input().split()]
a = 0
b = 0
cnt = 0
p1= p.copy()
p1.sort()
n_list = list(itertools.permutations(p1))
for i in n_list:
    if list(i)==p:
        a = cnt +1
    if list(i)==q:
        b = cnt +1
    cnt += 1
        
print(abs(a-b))
C = int(input())

ans = ['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']
ans2 = int(ans.index(C)) + 1
print(ans[ans2])

### FIXED CODE ###

C = input()

ans = ['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']
ans2 = int(ans.index(C)) + 1
print(ans[ans2])
H,N=map(int,input().split())

L=[]
for i in range(N):
    a,b=map(int,input().split())
    L.append([a,b])
L.sort()
import math
X=math.ceil(H/L[i][0]*L[i][1])
dp=[10**20 for i in range(10**4)]
dp[0]=0
for i in range(N):
    for j in range(len(dp)):
        if j%L[i][0]==0:
            Y=j//L[i][0]
        else:
            Y=j//L[i][0]+1
        if j-L[i][0]>=0:
            dp[j]=min(dp[j],Y*L[i][1],dp[j-L[i][0]]+L[i][1])
        else:
            dp[j]=min(dp[j],Y*L[i][1])
print(dp[H])

### FIXED CODE ###

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

L=[]
for i in range(N):
    a,b=map(int,input().split())
    L.append([a,b])
L.sort()
import math
X=math.ceil(H/L[i][0]*L[i][1])
dp=[10**20 for i in range(10**4+100)]
dp[0]=0
for i in range(N):
    for j in range(len(dp)):
        if j%L[i][0]==0:
            Y=j//L[i][0]
        else:
            Y=j//L[i][0]+1
        if j-L[i][0]>=0:
            dp[j]=min(dp[j],Y*L[i][1],dp[j-L[i][0]]+L[i][1])
        else:
            dp[j]=min(dp[j],Y*L[i][1])
print(dp[H])
from scipy.misc import comb
N=input()
K=int(input())
if len(N)<K:
    print(0)
    exit()
if K !=1:
    ans = 0
elif len(N)<2:
    print(int(N))
    exit()
else:
    ans = 9
for i in range(2,len(N)):
    ans += 9*comb(i-1,K-1)*(9**(K-1))
ans += (int(N[0])-1)*comb(len(N)-1,K-1)*9**(K-1)
if K==1:
    ans += 1
elif K==2:
    ans += 9*(len(N)-2)+int(N[1])
else:
    ans += int(N[2])+(len(N)-3)*9+(int(N[1])-1)*(len(N)-2)*9+comb(len(N)-2,2)*81
print(ans)

### FIXED CODE ###

N=input()
K=int(input())
dp_0 = [[0]*(len(N)) for i in range(K+1)]
dp_1 = [[0]*(len(N)) for i in range(K+1)]
dp_0[0][0]=1
dp_0[1][0]=int(N[0])-1
dp_1[1][0]=1
for i in range(len(N)-1):
    for j in range(K+1):
        if j==K:
            dp_0[j][i+1] += dp_0[j][i]
        elif j==0:
            dp_0[j][i+1] =dp_0[j][i]
            dp_0[j+1][i+1] += dp_0[j][i]*9
        else:
            dp_0[j][i+1] += dp_0[j][i]
            dp_0[j+1][i+1] += dp_0[j][i]*9
        if j != K and N[i+1] != '0':
            dp_0[j+1][i+1] += (int(N[i+1])-1)*dp_1[j][i]
            dp_0[j][i+1] += dp_1[j][i]
            dp_1[j+1][i+1] = dp_1[j][i]
        elif N[i+1] =='0':
            dp_1[j][i+1] = dp_1[j][i]
        else:

            dp_0[j][i+1] += dp_1[j][i]

print(dp_0[K][len(N)-1]+dp_1[K][len(N)-1])
N = int(input())
T = [[] for _ in range(N)]
for _ in range(N - 1):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    T[a].append(b)
    T[b].append(a)


colors = [-1] * N
stack = [(0, 0)]
while stack:
    n, color = stack.pop()
    colors[n] = color
    for to in T[n]:
        if colors[to] != -1:
            continue
        stack.append((to, color ^ 1))


# あまり１、あまり２、あまり０になるように並び替え
X = [[] for _ in range(3)]
for n in range(1, N + 1):
    X[n % 3].append(n)
X.append(X[0])
del X[0]


ans = []
for color in colors:
    if X[color]:
        ans.append(X[color].pop())
    else:
        ans.append(X[2].pop())

print(' '.join(map(str, ans)))


### FIXED CODE ###

N = int(input())
T = [[] for _ in range(N)]
for _ in range(N - 1):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    T[a].append(b)
    T[b].append(a)


colors = [-1] * N
stack = [(0, 0)]
while stack:
    n, color = stack.pop()
    colors[n] = color
    for to in T[n]:
        if colors[to] != -1:
            continue
        stack.append((to, color ^ 1))


# あまり１、あまり２、あまり０になるように並び替え
X = [[] for _ in range(3)]
for n in range(1, N + 1):
    X[n % 3].append(n)
X.append(X[0])
del X[0]


ans = []
x12, x3 = X[0] + X[1], X[2]
if colors.count(0) <= N // 3:
    for color in colors:
        if color == 0:
            ans.append(x3.pop())
        elif x12:
            ans.append(x12.pop())
        else:
            ans.append(x3.pop())

elif colors.count(1) <= N // 3:
    for color in colors:
        if color == 1:
            ans.append(x3.pop())
        elif x12:
            ans.append(x12.pop())
        else:
            ans.append(x3.pop())

else:
    for color in colors:
        if X[color]:
            ans.append(X[color].pop())
        else:
            ans.append(X[2].pop())

print(' '.join(map(str, ans)))
n =int(input())

if n ==0:
    print(0)
    exit()

l = [(-2)**_ for _ in range(100) if abs((-2)**_) <= 10**10]

if n > 0:
    x = [1]
    for i in range(len(l)):
        if abs(l[i]) < abs(n):
            x.append(l[i+1])

elif n < 0:
    x = []
    for j in range(len(l)):
        if abs(l[j]) < abs(n):
            x.append(l[j])

#print(len(x))

y = []
from itertools import combinations
for __ in range(len(x)):
    y += list(combinations(x, __))

for k in y:
    if sum(k) == n:
        z = list(k)

#print(y)
#print(z)

p = []
for q in range(len(x)):
    if x[q] in z:
        p.append(1)
    else:
        p.append(0)

p.reverse()
print(p)


### FIXED CODE ###

def f_10_to_m2(n):
    if n == 0:
        return 0 

    digits = []
    i = 0
    base = 1
    while n != 0:
        if n % (base*2) == 0:
            digits.append(0)
        else:
            digits.append(1)
            n -= base
        i += 1
        base *= -2
    return ''.join(map(str, reversed(digits)))

print(f_10_to_m2(int(input())))