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

import math
import itertools

# a = 6
# b = 4
#
# print(math.gcd(a, b))
k = int(input())
kk = k + 1
ans = 0
for i in range(1, kk):
    # print(i)
    for ii in range(1, kk):
        # print(ii)
        for iii in range(1, kk):
            # print((i,ii,iii))
            gcd2 = math.gcd(ii, iii)
            gcd3 = math.gcd(i, gcd2)
            ans += gcd3

print(ans)


### FIXED CODE ###

import math
import itertools

# a = 6
# b = 4
#
# print(math.gcd(a, b))
k = int(input())
kk = k + 1
ans = 0
for i in range(1, kk):
    # print(i)
    for ii in range(1, kk):
        # print(ii)
        for iii in range(1, kk):
            # print((i,ii,iii))
            gcd2 = math.gcd(ii, iii)
            gcd3 = math.gcd(i, gcd2)
            ans += gcd3

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

def resolve():
    import itertools

    n = int(input())
    A = list(map(int, input().split()))
    B = itertools.combinations(A, 2)
    ans = 0
    for b in B:
        ans += b[0] * b[1]

    print(ans % (10**9 + 7))

resolve()

### FIXED CODE ###

def resolve():
    n = int(input())
    A = list(map(int, input().split()))
    sm = sum(A) % (10**9 + 7)

    ans = 0
    for a in A:
        sm -= a
        ans += sm * a
        ans %= (10**9 + 7)
    print(ans)

resolve()
### BUGGY CODE ###

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

from heapq import heappop, heappush
push = lambda x,i: heappush(BB,(-x,i))
BB=[]

for i in range(n):
  push(B[i],i)

ans=0
chk=0
while chk<n:
  b,ind=heappop(BB)
  b,ai=-b,A[ind]
  if b<ai:
    ans=-1
    break
  d=B[(ind-1)%n]+B[(ind+1)%n]
  dd=(b-ai)//d
  if dd==0:
    if b==ai:
      chk+=1
      continue
    ans=-1
    break
  ans+=dd
  B[ind]-=d*dd
  push(b-d*dd,ind)
  
print(ans)


### FIXED CODE ###

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

from heapq import heappop, heappush
push = lambda x,i: heappush(BB,(-x,i))
BB=[]

for i,b in enumerate(B):
  push(b,i)

ans=0
while BB:
  b,ind=heappop(BB)
  b,ai=-b,A[ind]
  if b<ai:
    ans=-1
    break
  d=B[(ind-1)%n]+B[(ind+1)%n]
  dd=(b-ai)//d
  if dd==0:
    if b==ai:
      continue
    ans=-1
    break
  ans+=dd
  B[ind]-=d*dd
  push(b-d*dd,ind)
  
print(ans)
### BUGGY CODE ###

from itertools import product


X, Y, Z, K = map(int, input().split())
lst_A = list(map(int, input().split()))
lst_B = list(map(int, input().split()))
lst_C = list(map(int, input().split()))
lst_C = lst_C[:K]

lst_AB = [a + b for a, b in product(lst_A, lst_B)]
lst_AB.sort(reverse=True)
K_ = min(3000, X*Y*Z)
lst_ABC = [ab + c for ab, c in list(product(lst_AB[:K_], lst_C))]
lst_ABC.sort(reverse=True)


print(*lst_ABC[:K], sep="\n")


### FIXED CODE ###

import sys
from itertools import product


X, Y, Z, K = map(int, input().split())
lst_A = list(map(int, input().split()))
lst_B = list(map(int, input().split()))
lst_C = list(map(int, input().split()))
lst_A.sort(reverse=True)
lst_B.sort(reverse=True)
lst_C.sort(reverse=True)

# lst_A_K = lst_A[:K]
# lst_B_K = lst_B[:K]
lst_C_K = lst_C[:K]


lst_AB = sorted([a+b for a, b in product(lst_A, lst_B)], reverse=True)
lst_AB_K = lst_AB[:K]

lst_ABC = sorted([ab+c for ab, c in product(lst_AB_K, lst_C_K)], reverse=True)
lst_ABC_K = lst_ABC[:K]

print(*lst_ABC_K, sep="\n")
### BUGGY CODE ###

from bisect import bisect_left

n = int(input())
a = [int(input()) for _ in range(n)]
res = [a[0]]
for x in a[1:]:
    if x <= res[0]:
        res.insert(0, x)
    else:
        res[bisect_left(res, x) - 1] = x

print(len(res))



### FIXED CODE ###

from bisect import bisect_left
from collections import deque

n = int(input())
a = [int(input()) for _ in range(n)]
res = deque([a[0]])
for x in a[1:]:
    if x <= res[0]:
        res.appendleft(x)
    else:
        res[bisect_left(res, x) - 1] = x

print(len(res))
### BUGGY CODE ###

import collections as c
n = int(input())
s = [sorted(input()) for _ in range(n)]

cnt = 0
for i in range(n-1):
    for j in range(i+1,n):
        if s[i] == s[j]:
            cnt += 1

print(cnt)

### FIXED CODE ###

import collections as c

N = int(input())
S = sorted(["".join(sorted(input())) for _ in range(N)])

D = c.Counter(S)

D_value = []

for a in D.values():
	D_value.append(a)

ans = 0

for i in D_value:
	if i == 0:
		continue
	ans += (i * (i-1)) // 2

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

from itertools import accumulate

class BinaryIndexedTree:
    def __init__(self, As):
        self.numPow2 = 2 ** (len(As)-1).bit_length()
        self.data = [0] * (self.numPow2+1)
        for iA, A in enumerate(As):
            self.addValue(iA, A)

    def addValue(self, iA, A):
        iA += 1
        while iA <= self.numPow2:
            self.data[iA] += A
            iA += iA & -iA

    def getSum(self, iA):
        iA += 1
        ans = 0
        while iA > 0:
            ans += self.data[iA]
            iA -= iA & -iA
        return ans


N, K = map(int, input().split())
As = [int(input()) for _ in range(N)]

Bs = list(accumulate([0]+[A-K for A in As]))
iBs = list(range(N+1))
iBs.sort(key=lambda iB: Bs[iB])

BIT = BinaryIndexedTree([0]*(N+1))

ans = 0
for iB in iBs:
    BIT.addValue(iB, 1)
    ans += BIT.getSum(iB-1)

print(ans)


### FIXED CODE ###

from itertools import accumulate

class BinaryIndexedTree:
    def __init__(self, As):
        self.numPow2 = 2 ** (len(As)-1).bit_length()
        self.data = [0] * (self.numPow2+1)
        for iA, A in enumerate(As):
            self.addValue(iA, A)

    def addValue(self, iA, A):
        iA += 1
        while iA <= self.numPow2:
            self.data[iA] += A
            iA += iA & -iA

    def getSum(self, iA):
        iA += 1
        ans = 0
        while iA > 0:
            ans += self.data[iA]
            iA -= iA & -iA
        return ans


N, K = map(int, input().split())
As = [int(input()) for _ in range(N)]

Bs = list(accumulate([0]+[A-K for A in As]))
iBs = list(range(N+1))
iBs.sort(key=lambda iB: Bs[iB])

BIT = BinaryIndexedTree([0]*(N+1))

ans = 0
for iB in iBs:
    BIT.addValue(iB, 1)
    ans += BIT.getSum(iB-1)

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

a = 0
for i in range(int(input())):
    a += i
    
print(a)

### FIXED CODE ###

a = int(input())

print(a*(a-1)//2)
### BUGGY CODE ###

n,m = map(int,input().split())
uf = [-1]*n
def root(x):
    if uf[x] < 0:
        return x
    uf[x] = root(uf[x])
    return uf[x]
def unite(x,y):
    rx, ry = root(x), root(y)
    if rx==ry: return False
    if rx > ry: rx, ry = ry, rx
    uf[rx] += uf[ry]
    uf[ry] = rx
    return True

edge = [[-1]*n for i in range(n)]
for i in range(m):
    l,r,d = map(int, input().split())
    edge[l-1][r-1] = d
    edge[r-1][l-1] = -d
    unite(l-1, r-1)

dist = [0]*n
visited = [False]*n
ans = True

def bfs(p, d=0):
    global ans
    if not visited[p]:
        visited[p] = True
        dist[p] = d
        for ind, j in enumerate(edge[p]):
            if j>= 0:
                bfs(ind, d+j)
    else:
        if dist[p] != d:
            ans = False

for i in range(n):
    if uf[i] >= 0:
        continue
    bfs(i, 0)
    if not ans:
        break

if ans:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

from collections import defaultdict, deque

n,m = map(int,input().split())
edge = [[] for i in range(n)]
for i in range(m):
    l,r,d = map(int, input().split())
    edge[l-1].append((r-1,d))
    edge[r-1].append((l-1,-d))

dist = [0]*n
visited = [False]*n

for i in range(n):
    if visited[i]:
        continue
    q = deque()
    q.append((i,0))
    while q:
        to, d = q.popleft()
        if visited[to]:
            if dist[to] != d:
                print("No")
                exit()
        else:
            visited[to] = True
            dist[to] = d
            for ind, j in edge[to]:
                q.append((ind,d+j))

print("Yes")
### BUGGY CODE ###

import sys
sys.setrecursionlimit(2147483647)
INF = float("inf")
MOD = 10**9 + 7 # 998244353
input = lambda:sys.stdin.readline().rstrip()
from itertools import accumulate
def resolve():
    n = int(input())
    # dp[i][j] : i まで見て末尾が j のもの (i <= j)
    dp = [0] * n
    dp[0] = 1
    for i, c in enumerate(input(), 1):
        S = list(accumulate([0] + dp))
        dp = [0] * n
        if c == '<':
            # ndp[j] = dp[0] + ... + dp[j - 1] # j <= i
            for j in range(i + 1):
                dp[j] = S[j]
        elif c == '>':
            # ndp[j] = dp[j] + ... + dp[i - 1] # j <= i
            for j in range(i + 1):
                dp[j] = S[i] - S[j]

    print(sum(dp) % MOD)
resolve()

### FIXED CODE ###

import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n=int(input())
    s=input()
    dp=[1]*n
    for i in range(1,n):
        ndp=[0]*n
        S=[0]*(n+1)
        for j in range(n):
            S[j+1]=S[j]+dp[j]
        for less in range(n-i):
            if(s[i-1]=='<'): ndp[less]=S[less+1]
            else: ndp[less]=S[n]-S[less+1]
            ndp[less]%=MOD
        dp=ndp
    print(dp[0])
resolve()
### BUGGY CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()

n, p = [int(c) for c in input().split()]
s = input()    

if p in (2,5):
    a = tuple(int(c)%p for c in s)
    out = 0
    for i,x in enumerate(a):
        if x==0:
            out += (i + 1)
else:
    a = [0]*n
    tmp = 0
    for i in reversed(range(n)):
        tmp = (tmp + pow(10, n-i-1) * int(s[i])) % p
#         tmp = (tmp + 10**(n-i-1) * int(s[i])) % p
        a[i] = tmp
    d = {i: 0 for i in range(p)}
    d[0] = 1
    out = 0
    for x in a[::-1]:
        out += d[x]
        d[x] += 1
print(out)

### FIXED CODE ###


def hoge():

    n, p = [int(c) for c in input().split()]
    s = input()    

    if p in (2,5):
        a = tuple(int(c)%p for c in s)
        out = 0
        for i,x in enumerate(a):
            if x==0:
                out += (i + 1)
    else:
        a = [0]*n
        tmp = 0
        for i in reversed(range(n)):
            tmp = (tmp + pow(10, n-i-1, p) * int(s[i])) % p
    #         tmp = (tmp + 10**(n-i-1) * int(s[i])) % p
            a[i] = tmp
        d = {i: 0 for i in range(p)}
        d[0] = 1
        out = 0
        for x in a[::-1]:
            out += d[x]
            d[x] += 1
    print(out)
hoge()
### BUGGY CODE ###

#-*- coding: utf_8 -*-

data = []
data.append([int(input())])
length = 2
while length != 1:
    r = [int(x) for x in input().split(",")]
    data.append(r)
    length = len(r)

first = data[:int(len(data)/2) + 1]
mx_arr = [0] * 100

def dfs(n, i, mx):
    if n == len(first) - 1:
        s = mx * 2 + data[n][i]
        mx_arr[i] = max(s, mx_arr[i])
        return

    mx += data[n][i]
    dfs(n + 1, i, mx)
    dfs(n + 1, i + 1, mx)

dfs(0, 0, 0)

print(max(mx_arr))

### FIXED CODE ###

#-*- coding: utf_8 -*-

data = []
data.append([int(input())])
length = 2
counter = 0
while length != 1:
    r = [int(x) for x in input().split(",")]
    data.append(r)
    length = len(r)
    counter += 1

N = int((counter + 1 )/ 2) + 1
dp = [[0 for i in range(N)] for j in range(N)]
data_arr = [[0 for i in range(N)] for j in range(N)]

left = data[:N]
right = data[N:]

i = 0
for v in left:
    for idx, r in enumerate(v):
        data_arr[i - idx][idx] = r
    i += 1
right.reverse()
for i, v in enumerate(right):
    for idx, r in enumerate(v):
        data_arr[N - 1 - idx][N - 1 - i + idx] = r


dp[0][0] = data_arr[0][0]

for i in range(1, N):
    dp[0][i] = dp[0][i - 1] + data_arr[0][i]
    dp[i][0] = dp[i - 1][0] + data_arr[i][0]

for i in range(1, N):
    for j in range(1, N):
        dp[i][j] += data_arr[i][j] + max(dp[i - 1][j], dp[i][j - 1])

print(dp[N - 1][N - 1])
### BUGGY CODE ###

def union_set(x, y):
    return x if len(x) > len(y) else y

s = input()
t = input()

table = ['' for j in range(len(t) + 1)]
table_pre = ['' for j in range(len(t) + 1)]

for i, si in enumerate(s):
    for j, tj in enumerate(t):
        if si == tj:
            table[j + 1] = table_pre[j] + si
        else:
            table[j + 1] = union_set(table[j], table_pre[j + 1])
    table, table_pre = table_pre, table
print(table_pre[-1])


### FIXED CODE ###

s = input()
t = input()

table = [[0 for j in range(len(t) + 1)] for i in range(len(s) + 1)]

for i, si in enumerate(s):
    table_pre = table[i]
    table_cur = table[i + 1]
    for j, tj in enumerate(t):
        if si == tj:
            table_cur[j + 1] = table_pre[j] + 1
        else:
            table_cur[j + 1] = max(table_cur[j], table_pre[j + 1])

ls, lt = len(s), len(t)
ans = ''
while ls and lt:
    if table[ls][lt] == table[ls][lt - 1]:
        lt -= 1
    elif table[ls][lt] == table[ls - 1][lt]:
        ls -= 1
    else:
        ans = s[ls - 1] + ans
        ls -= 1
        lt -= 1
print(ans)
### BUGGY CODE ###

N = int(input())

syohin = []
kind = 0

for i in range(N):
    S = input()
    if S not in syohin:
        kind += 1
        syohin.append(S)

print(kind)

### FIXED CODE ###

N = int(input())

S = []

for i in range(N):
    S.append(input())

print(len(set(S)))
### BUGGY CODE ###

#Union Find
 
#xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
#xとyの属する集合の併合
def unite(x,y):
    x = find(x)
    y = find(y)
    
    if x == y:
        return False
    else:
        #sizeの大きいほうがx
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        par[y] = x
        return True

#xとyが同じ集合に属するかの判定
def same(x,y):
    return find2(x) == find2(y)

def find2(x):
  if pa[x] < 0:
      return x
  else:
      pa[x] = find2(pa[x])
      return pa[x]

#根なら-size,子なら親の頂点
n,k,l = [int(i) for i in input().split()]
par = [-1]*n
pa = [-1]*n
ans = [0]*n
pq = []

for i in range(k):
  p,q = [int(i) for i in input().split()]
  unite(p-1,q-1)
  pq_append = pq.append
  pq_append([p-1,q-1])

def unite2(x,y):
    x = find2(x)
    y = find2(y)
    if x == y:
        return False
    else:
        if pa[x] > pa[y]:
            x,y = y,x
        pa[x] += pa[y]
        pa[y] = x
        return True
  
for i in range(l):
  r,s = [int(i) for i in input().split()]
  unite2(r-1,s-1)

#print(par,pa)
chk = []
for i in range(n):
  chk_append = chk.append
  chk_append((find(i),find2(i)))
  
import collections
for i in range(n):
  c = collections.Counter(chk)
  ans[i] += c[chk[i]]
  
ans = list(map(str,ans))
print(' '.join(ans))

### FIXED CODE ###

def main():  
  #Union Find

  #xの根を求める
  def find(x):
      if par[x] < 0:
          return x
      else:
          par[x] = find(par[x])
          return par[x]
  #xとyの属する集合の併合
  def unite(x,y):
      x = find(x)
      y = find(y)

      if x == y:
          return False
      else:
          #sizeの大きいほうがx
          if par[x] > par[y]:
              x,y = y,x
          par[x] += par[y]
          par[y] = x
          return True

  def find2(x):
    if pa[x] < 0:
        return x
    else:
        pa[x] = find2(pa[x])
        return pa[x]

  import sys
  input = sys.stdin.readline

  n,k,l = [int(i) for i in input().split()]
  par = [-1]*n
  pa = [-1]*n
  ans = [0]*n

  for i in range(k):
    p,q = [int(i) for i in input().split()]
    unite(p-1,q-1)

  def unite2(x,y):
      x = find2(x)
      y = find2(y)
      if x == y:
          return False
      else:
          if pa[x] > pa[y]:
              x,y = y,x
          pa[x] += pa[y]
          pa[y] = x
          return True

  for i in range(l):
    r,s = [int(i) for i in input().split()]
    unite2(r-1,s-1)

  dic = {}
  chk = []
  for i in range(n):
      p1 = find(i)
      p2 = find2(i)
      chk.append((p1,p2))
      if (p1,p2) in dic:
          dic[(p1,p2)] += 1
      else: 
          dic[(p1,p2)] = 1
  print(' '.join([str(dic[chk[i]]) for i in range(n)]))
  
if __name__ == '__main__':
    main()
### BUGGY CODE ###

H,N = map(int,input().split())
A = []
for i in range(N):
    a,b = map(int,input().split())
    A.append((a,b))
MAXH = H+10**4
DP = [float("inf")]*(MAXH)
DP[0] = 0
for i in range(MAXH):
    for j in range(N):
        if i+A[j][0]>MAXH-1:continue
        DP[i+A[j][0]] = min(DP[i]+A[j][1],DP[i+A[j][0]])
print(min(DP[H:]))

### FIXED CODE ###

H,N = map(int,input().split())
MAXH = H+10000
DP = [float("inf")]*MAXH
DP[0] = 0
for i in range(N):
    a,b = map(int,input().split())
    for j in range(MAXH-a):
        if j>H+a:break
        DP[j+a] = min(DP[j+a],DP[j]+b)
print(min(DP[H:]))
### BUGGY CODE ###

def main():
    S = input()
    result = 0
    L = len(S)
    for i in range(L-3):
        work = int(S[i:i+3])
        j = i + 3
        for _ in range(10**6):
            if j >= L:
                break
            work = work * 10 + int(S[j])
            if work % 2019 == 0:
                result += 1
            j += 1
    print(result)
main()

### FIXED CODE ###

def main():
    S = input()
    work, temp = [0] * 2019, 0
    work[0] = 1
    a = 1
    for s in S[::-1]:
        temp += int(s) * a
        work[temp%2019] += 1
        a *= 10
        a %= 2019
    print(sum([w*(w-1)//2 for w in work]))
main()
### BUGGY CODE ###

S = list(input())
T = list(input())
i = 0
counter = 0

if S == T:
  print(counter)
  exit()
  
while i <= len(S) - 1:
  if T[i] != S[i]:
    S[i] = T[i]
    counter += 1
    if S == T:
      break
  i += 1
  
print(counter)

### FIXED CODE ###

S = list(input())
T = list(input())
i = 0
counter = 0

if S == T:
  print(counter)
  exit()
  
for i in range(len(S)):
  if T[i] != S[i]:
    counter += 1
    if S == T:
      break
      
print(counter)
### BUGGY CODE ###

#!/usr/bin/env PyPy
from collections import deque
from math import inf


def bfs(maze, visited, Ch, Cw, Dh, Dw, H, W):
    queue = deque([[Ch, Cw]])
    visited[Ch][Cw] = 0

    while queue:
        y, x = queue.popleft()
        if [y, x] == [Dh, Dw]:
            break
        for j in range(-2, 3):
            for k in range(-2, 3):
                new_y, new_x = y + j, x + k
                if 0 <= new_y < H and 0 <= new_x < W:
                    if maze[new_y][new_x] == "." and j**2 + k**2 == 1 and visited[y][x] < visited[new_y][new_x]:
                        visited[new_y][new_x] = visited[y][x]
                        queue.appendleft([new_y, new_x])
                    elif maze[new_y][new_x] == "." and visited[new_y][new_x] == inf:
                        visited[new_y][new_x] = visited[y][x] + 1
                        queue.append([new_y, new_x])
    return visited[Dh][Dw]


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    maze = [input() for i in range(H)]
    visited = [[inf] * W for i in range(H)]

    dist = bfs(maze, visited, Ch - 1, Cw - 1, Dh - 1, Dw - 1, H, W)
    print(dist if dist != inf else -1)


if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
from collections import deque
from math import inf


def input(): return sys.stdin.readline().strip()


def bfs(maze, Ch, Cw, Dh, Dw, H, W):
    visited = [[inf] * W for i in range(H)]
    queue = deque([[Ch, Cw]])
    visited[Ch][Cw] = 0

    dy_dx0 = [[0, 1], [1, 0], [0, -1], [-1, 0]]
    dy_dx1 = [[2, 2], [2, 1], [2, 0], [2, -1], [2, -2], [1, 2], [1, 1], [1, -1], [1, -2], [0, 2],
              [0, -2], [-1, 2], [-1, 1], [-1, -1], [-1, -2], [-2, 2], [-2, 1], [-2, 0], [-2, -1], [-2, -2]]

    while queue:
        y, x = queue.popleft()
        if [y, x] == [Dh, Dw]:
            break
        for j, k in dy_dx0:
            new_y, new_x = y + j, x + k
            if 0 <= new_y < H and 0 <= new_x < W and maze[new_y][new_x] == "." and visited[y][x] < visited[new_y][new_x]:
                visited[new_y][new_x] = visited[y][x]
                queue.appendleft([new_y, new_x])
        for j, k in dy_dx1:
            new_y, new_x = y + j, x + k
            if 0 <= new_y < H and 0 <= new_x < W and maze[new_y][new_x] == "." and visited[new_y][new_x] == inf:
                visited[new_y][new_x] = visited[y][x] + 1
                queue.append([new_y, new_x])
    return visited[Dh][Dw]


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    maze = [input() for i in range(H)]

    dist = bfs(maze, Ch - 1, Cw - 1, Dh - 1, Dw - 1, H, W)

    print(dist if dist != inf else -1)


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

import sys


def input():
    return sys.stdin.readline().strip()


def dijkstra(s, n, w, cost):
    # 始点sから各頂点への最短距離
    # n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0

    while True:
        v = -1
        # まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v == -1):
                v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
            break
        used[v] = True
        for j in range(n):
            d[j] = min(d[j], d[v] + cost[v][j])
    return d


def main():
    N = int(input())
    cost = [[float("inf") for i in range(N)] for i in range(N)]

    for i in range(N - 1):
        u, v, w = map(int, input().split())
        cost[u - 1][v - 1] = w
        cost[v - 1][u - 1] = w
    D = dijkstra(0, N, N - 1, cost)
    for d in D:
        if d % 2 == 0:
            print(0)
        else:
            print(1)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
import heapq


def input():
    return sys.stdin.readline().strip()


def dijkstra(start, n_nodes, edge):
    dist = [float("inf")] * n_nodes
    dist[start] = 0
    # 優先度キューの準備
    q = [(dist[start], start)]
    heapq.heapify(q)
    while q:
        # スタートから最も最短距離のものを取り出す
        d, i = heapq.heappop(q)
        # 記録してある情報よりも，取り出した要素に入っている距離情報の方が大きければ
        # 打ち切り．次の要素を取り出す操作に戻る
        if dist[i] < d:
            continue
        # そこから移動できる頂点を探し，最短距離が更新できるものがあれば，
        # 距離を更新して，その頂点への距離と頂点の方法を優先度キューにpush
        for cost, j in edge[i]:
            if dist[j] > dist[i] + cost:
                dist[j] = dist[i] + cost
                heapq.heappush(q, (dist[j], j))
    return dist


def main():
    N = int(input())
    edge = [[] for _ in range(N)]
    for i in range(N - 1):
        u, v, w = map(int, input().split())
        edge[u - 1].append([w, v - 1])
        edge[v - 1].append([w, u - 1])
    D = dijkstra(0, N, edge)
    for d in D:
        if d % 2 == 0:
            print(0)
        else:
            print(1)


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

def main():
    K = int(input())

    lunlun_number_memo = {}

    # def is_lunlun(str_n):
    #     while True:
    #         if lunlun_number_memo.get(str_n):
    #             return True
    #         elif len(str_n) == 1:
    #             return True
    #         else:
    #             if abs(int(str_n[0]) - int(str_n[1])) <= 1:
    #                 str_n = str_n[1:]
    #             else:
    #                 return False


    lunlun_number_count = 0
    i = 0
    while lunlun_number_count < K:
        i += 1
        # if is_lunlun(str(i)):
        str_i = str(i)
        while True:
            if lunlun_number_memo.get(str_i) or len(str_i) == 1:
                lunlun_number_memo[str(i)] = True
                lunlun_number_count += 1
                break
            else:
                if abs(int(str_i[0]) - int(str_i[1])) <= 1:
                    str_i = str_i[1:]
                else:
                    break

            # print(i)
            # print(lunlun_number_count)
            # print("running")

    print(i)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
import queue

def main():
    K = int(input())
    q = queue.Queue()
    for i in range(1, 10):
        q.put(i)

    i = 0
    while True:
        i += 1

        n = q.get()
        center_num = (10 * n) + (n % 10)
        
        if n % 10 != 0:
            q.put(center_num - 1)
        
        q.put(center_num)

        if n % 10 != 9:
            q.put(center_num + 1)

        if i >= K:
            # print(q.queue)
            print(n)
            sys.exit()

if __name__ == '__main__':
    main()