Harryxun/stf_run huggingface dataset:
#input = raw_input

res = None
G = None

def dfs(jibun_v, p, jibun_c):
    global res
    global G

    res[jibun_v] = jibun_c
    #print(jibun_v, p, jibun_c)

    tonari_nodes = G[jibun_v]
    for tonari_v, w in tonari_nodes:
        #if tonari_v == p or res[tonari_v] != -1:
        if tonari_v == p or res[tonari_v] != -1:
            continue

        if w % 2 == 0:
            tonari_c = jibun_c
        else:
            tonari_c = 1 - jibun_c

        dfs(tonari_v, jibun_v, tonari_c)
    

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

    global G
    G = [[] for _ in range(N)]

    for i in range(N-1):
        u, v, w = map(int, input().split(" "))
        u -= 1
        v -= 1
        w = w % 2
        G[u].append([v, w])
        G[v].append([u, w])

    global res
    res = [-1 for _ in range(N)]
    
    jibun_v = 0
    p = -1
    jibun_c = 0
    dfs(jibun_v, p, jibun_c)

    for i in range(N):
        print(res[i])

main()
        

### FIXED CODE ###

import sys
if sys.version_info[0] == 2:
    input = raw_input
sys.setrecursionlimit(2 ** 31 -1)

res = None
G = None

def dfs(jibun_v, p, jibun_c):
    global res
    global G

    res[jibun_v] = jibun_c
    #print(jibun_v, p, jibun_c)

    tonari_nodes = G[jibun_v]
    for tonari_v, w in tonari_nodes:
        #if tonari_v == p: # only no loop
        #if tonari_v == p or res[tonari_v] != -1:
        if res[tonari_v] != -1:
            continue

        else:
            if w % 2 == 0:
                tonari_c = jibun_c
            else:
                tonari_c = 1 - jibun_c

            dfs(tonari_v, jibun_v, tonari_c)
    

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

    global G
    G = [[] for _ in range(N)]

    for i in range(N-1):
        u, v, w = map(int, input().split(" "))
        u -= 1
        v -= 1
        w = w % 2
        G[u].append([v, w])
        G[v].append([u, w])

    global res
    res = [-1 for _ in range(N)]
    
    jibun_v = 0
    p = -1
    jibun_c = 0
    dfs(jibun_v, p, jibun_c)

    for i in range(N):
        print(res[i])

main()
def solve(a, b, c):
    if (a, b, c) in s:
        return -1
    if (a % 2) or (b % 2) or (c % 2):
        return 0
    a >>= 1
    b >>= 1
    c >>= 1
    return 1 + solve(b + c , c + a, a + b)

if __name__ == '__main__':
    a, b, c = map(int, input().split())
    s = set()
    print(solve(a, b, c))



### FIXED CODE ###

def solve(a, b, c, ans):
    if (a, b, c) in s:
        return -1
    if (a % 2) or (b % 2) or (c % 2):
        return ans
    s.add((a, b, c))
    a >>= 1
    b >>= 1
    c >>= 1
    return solve(b + c , c + a, a + b, ans + 1)

if __name__ == '__main__':
    a, b, c = map(int, input().split())
    s = set()
    print(solve(a, b, c, 0))
n = input ()
N = str(n)
if 7 in N:
    print(yes)
else:
    print(no)
    

### FIXED CODE ###

n = input()
N = str(n)
if "7" in N:
    print("Yes")
else:
    print("No")
import itertools
import heapq
import sys
import functools
import operator
input = sys.stdin.readline
n,k = map(int,input().split())
a = list(map(int,input().split()))
if n>=2*k:
  a_plus = heapq.nlargest(k, a)
  a_minus = heapq.nsmallest(k, a)
  a_new = a_plus+a_minus
  comb = itertools.combinations(a_new,k)
else:
  comb = itertools.combinations(a,k)
  
l = [list(i) for i in comb]
  
A = [functools.reduce(operator.mul,l[i]) for i in l]
 
l_max = max(A)
waru = 10**9 + 7
 
mod = l_max % waru
print(mod)

### FIXED CODE ###

import sys
 
n, k = map(int, input().split())
a = [int(x) for x in input().split()]
mod = pow(10, 9)+7
zero = 0
plus = []
minus = []
for i in range(n):
  if a[i] == 0:
    zero += 1
  elif a[i] > 0:
    plus.append(a[i])
  else:
    minus.append(a[i])
 
P, M = len(plus), len(minus)
plus.sort(reverse=True)
minus.sort()
ans = 1
if n == k:
  for i in range(n):
    ans *= a[i]
    ans %= mod
elif P+M < k:
  ans = 0
elif P == 0:
  if zero and k%2:
    ans = 0
  else:
    if k%2:
      minus.reverse()
    for i in range(k):
      ans *= minus[i]
      ans %= mod
else:
  q = 0
  if k%2:
    ans *= plus[0]
    ans %= mod
    q = 1
  judge = []
  for i in range((len(plus)-q)//2):
    judge.append(plus[2*i+q]*plus[2*i+q+1])
  for i in range(len(minus)//2):
    judge.append(minus[2*i]*minus[2*i+1])
  judge.sort(reverse=True)
  for i in range(k//2):
    ans *= (judge[i]%mod)
    ans %= mod
 
print(ans)
import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, random, time, copy, functools
N, M = [int(_) for _ in input().split()]
AB = [[int(_) for _ in input().split()] for _ in range(N - 1 + M)]

G = [set() for _ in range(N + 1)]
P_cand = [set() for _ in range(N + 1)]
for a, b in AB:
    G[a].add(b)
    P_cand[b].add(a)
for p in range(1, N):
    if len(P_cand[p]) == 0:
        break
D = [[0, -1] for _ in range(N + 1)]
D[p] = [0, 0]


def dfs(p):
    for _ in range(len(G[p])):
        for c in G[p]:
            if D[c][1] < D[p][1] + 1:
                D[c][1] = D[p][1] + 1
                D[c][0] = p
                dfs(c)


dfs(p)
[print(_[0]) for _ in D[1:]]


### FIXED CODE ###

import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, random, time, copy, functools
N, M = [int(_) for _ in input().split()]
AB = [[int(_) for _ in input().split()] for _ in range(N - 1 + M)]

G = [set() for _ in range(N + 1)]
count = [0] * (N + 1)
ans = [0] * (N + 1)
for a, b in AB:
    G[a].add(b)
    count[b] += 1
for i in range(1, N):
    if count[i] == 0:
        root = collections.deque([i])
        break
while root:
    p = root.popleft()
    for c in G[p]:
        count[c] -= 1
        if count[c] == 0:
            ans[c] = p
            root.append(c)
print(*ans[1:], sep='\n')
n = int(input())

l = [False] * (n + 1)
p = [n]
b = bin(n)[2:][::-1]

pw = 0
for i in b:
    if i == '1':
        p.append(2 ** int(pw))
        l[2 ** pw] = True
    pw += 1

q = []
xr = 0
for i in range(1, n):
    if not l[i]:
        xr ^= i
        q.append(i)

# print(xr)
# print(p)
# print(q)

res1 = []
for i in p:
    res1.append(i)
for i in p:
    res1.append(i + n)
res2 = []
if xr == 0:
    res2 = [n]
    for i in q:
        res2.append(i)
    for i in q:
        res2.append(i + n)
else:
    res2 = []
    for i in q:
        res2.append(i)
    if xr not in p:
        print('!!!')
        exit(1)
    res2.append(xr)
    for i in q:
        res2.append(i + n)

res = []
for i,j in zip(res1, res1[1:]):
    res.append([i, j])
    if i == j:
        print('No')
        exit()
    # print(i, j)
for i,j in zip(res2, res2[1:]):
    res.append([i, j])
    if i == j:
        print('No')
        exit()
    # print(i, j)

if len(res) != 2 * n - 1:
    print('No')
else:
    print('Yes')
    for i in res:
        print(*i)

### FIXED CODE ###

n = int(input())
nn = n
f = lambda x, y: x + y * nn
g = lambda x: x if x % 2 == 1 else x + nn

# 2の累乗はむり
b = bin(n)
if b.count('0') == len(b) - 2:
    print('No')
    exit(0)

ret = [
    [f(1, 0), f(2, 0)],
    [f(2, 0), f(3, 0)],
    [f(3, 0), f(1, 1)],
    [f(1, 1), f(2, 1)],
    [f(2, 1), f(3, 1)],
]

if n % 2 == 0:
    p = 2 ** (len(b) - 3)
    q = n ^ 1 ^ p
    ret.append([g(p), f(n, 0)])
    ret.append([g(q), f(n, 1)])
    n -= 1

# nは奇数
while n > 3:
    ret.append([f(n - 1, 0), f(n, 0)])
    ret.append([f(n, 0), f(1, 1)])
    ret.append([f(1, 1), f(n - 1, 1)])
    ret.append([f(n - 1, 1), f(n, 1)])
    n -= 2

print('Yes')
for x, y in ret:
    # x = x if x <= nn else x - nn
    # y = y if y <= nn else y - nn
    print(x, y)
N = int(input())
A = [int(s) for s in input().split()]
ans = 0
temp = [0] * (max(A) + 1)
for i in range(N):
    for d in range(1, int(A[i]/2)):
        if A[i] % d == 0:
            temp[d] += 1
    temp[A[i]] += 1
for i in range(max(A), 0, -1):
    if N - 1 <= temp[i]:
        ans = i
        break
print(ans)


### FIXED CODE ###

from fractions import gcd
N = int(input())
A = [int(s) for s in input().split()]
ans = 0
L = [0] * (N)
R = [0] * (N)
for n in range(0, N):
    if n != N-1:
        L[n+1] = gcd(A[n], L[n])
        R[-(n+2)] = gcd(A[-(n+1)], R[-(n+1)])
for n in range(0, N):
    temp = gcd(L[n], R[n])
    ans = max(temp, ans)
print(ans)
O = input()
E = input()
Answer = ''
for i in range(len(O)):
  Answer = Answer + O[i]
  Answer = Answer + E[i]
print(Answer)

### FIXED CODE ###

O = input()
E = input()
Answer = ''
for i in range(len(O)-1):
  Answer = Answer + O[i]
  Answer = Answer + E[i]
if len(E)==len(O):
  Answer = Answer + O[len(O)-1]
  Answer = Answer + E[len(E)-1]
else:
  Answer = Answer + O[len(O)-1]

print(Answer)
a, b = map(int, input().split())
if a == b:
  print("H")
else:
  print("D")


### FIXED CODE ###

a, b = map(str, input().split())
if a == b:
	print("H")
else:
	print("D")
import math
from functools import reduce

n = int(input())
li = list(map(int,input().split()))
ans = 0

def gcd_list(numbers):
    return reduce(math.gcd,numbers)

def gcd_list2(li):
    a = math.gcd(li[0],li[1])
    for i in range(n-1):
        a = math.gcd(a,li[i])
    return a

for i in range(n):
    li2 = li[:i] + li[i+1:]
    a = gcd_list2(li2)
    if a > ans:
        ans = a

print(ans)


### FIXED CODE ###

n = int(input())
li = list(map(int,input().split()))
ans = 0
lgcd = [0]*n
rgcd = [0]*n
lgcd[0] = li[0]
rgcd[-1] = li[-1]

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

for i in range(n-1):
    lgcd[i+1] = gcd(lgcd[i],li[i+1])
    rgcd[-i-2] = gcd(rgcd[-i-1],li[-(i+2)])

gcd_list = [gcd(lgcd[i],rgcd[i+2]) for i in range(n-2)]

gcd_list.append(lgcd[-2])
gcd_list.append(rgcd[1])

print(max(gcd_list))
A,B=map(int,input().split)
print(max(A+B,A-B,A*B))

### FIXED CODE ###

A,B=map(int,input().split())
print(max(A+B,A-B,A*B))
from scipy.special import comb

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

a = []

for i in range(M):
    a.append(int(input()))

    # 隣接してる場合は、0出力で終了
    if a[i] == a[i - 1] + 1:
        print(0)
        exit(0)

dp = [0] * (N + 1)

dp[0] = 1

if 1 in a:
    dp[1] = 0
else:
    dp[1] = 1

for i in range(2, N + 1):
    if i in a:
        continue
    else:
        dp[i] = dp[i - 1] + dp[i - 2]

print(dp[-1] % 1000000007)




### FIXED CODE ###

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

# a = [int(input()) for _ in range(M)]
a = set([int(input()) for _ in range(M)])

dp = [0] * (N + 1)
dp[0] = 1

if 1 in a:
    dp[1] = 0
else:
    dp[1] = 1

for i in range(2, N + 1):
    if i in a:
        continue
    else:
        dp[i] = dp[i - 1] + dp[i - 2]
        dp[i] %= 1000000007

print(dp[-1])
def resolve():
    a, b = list(map(int, input().split()))
    l = list(range(a, b + 1))
    l.sort()
    minus = list(filter(lambda x: x < 0, l))
    minus = len(minus)

    if a <= 0 and b >= 0:
        print('Zero')
        return

    if a < 0 and b < 0:
        minus = len(range(a, b + 1))

    if minus % 2 == 1:
        print('Negative')
        return
    else:
        print('Positive')
        return
    return


resolve()

### FIXED CODE ###

def resolve():
    a, b = list(map(int, input().split()))

    if a <= 0 and b >= 0:
        print('Zero')
    elif b < 0 and (b - a + 1) % 2 == 1:
        print('Negative')
    else:
        print('Positive')
    return


resolve()
L = list(map(int,input().split()))
K = int(input())
m = max(L)
print(L-m + m* (2 ** K))


### FIXED CODE ###

L = [list(map(int,input().split()))]
K = int(input())
import copy

def peice_double(L):
    l = []
    for x in L:
        tmp = copy.copy(x)
        for i in range(3):
            tmp[i] = tmp[i] * 2
            l.append(copy.copy(tmp))
            tmp[i] = tmp[i] // 2
    return l
for i in range(K):
    L = peice_double(L)
ans = 0
for x in L:
    ans = max(ans, sum(x))
print(ans)
n=int(input())

i=1
k=0

while n>=i:
  f[i]=int(input())
  i+=1
  
while n>=i:
  k+=1/f[i]
  i+1
  
print(1/k)

### FIXED CODE ###

n = int(input())
an = list(map(int, input().split()))
i=0
k=0
 
 

  
while n>i:
  k+=1/an[i]
  i+=1
  
print(1/k)
n,k=map(int,input().split())
c=list(map(int,input().split()))
dp=[0]
if n>1:
    dp.append(abs(c[1]-c[0]))
    for i in range(2,n):
        m=10**9+1
        for j in range(1,k+1):
            m=min(m,dp[max(n-k-1,0)]+abs(c[i]-c[max(0,i-j)]))
        dp.append(m)
print(dp[-1])


### FIXED CODE ###

def main():
    n, k = map(int, input().split())
    h = list(map(int, input().split()))
    a = [0] * n
    a[0] = 0
    for i in range(1, n):
        a[i] = min([a[j] + abs(h[i] - h[j]) for j in range(max(0, i - k), i)])
    print(a[-1])
 
if __name__ == '__main__':
    main()
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#include <bits/stdc++.h>
using namespace std;

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n; cin >> n;
    vector<int> ans(n+1);
    for (int x = 1; x <= 100; x++)
    {
        for (int y = 1; y <= 100; y++)
        {
            for (int z = 1; z <= 100; z++)
            {
                int m = x * x + y * y + z * z + x * y + y * z + z * x;
                if (m <= n)
                {
                    ans[m]++;
                }
                else
                {
                    break;
                }
            }
        }
    }
    rep(i,n){
        cout << ans[i+1] << "\n";
    }
}

### FIXED CODE ###

import math
n = int(input())
ans = [0] * n
a = math.floor(n**0.5)
b = 0
for x in range(1, a):
    for y in range(1, a):
        for z in range(1, a):
            m = x * x + y * y + z * z + x * y + y * z + z * x
            if m <= n:
                ans[m - 1] += 1

for i in range(n):
    print(ans[i])
N = int(input())
result = N * (N + 1) // 2
print(f'{result}')

### FIXED CODE ###

N = int(input())
result = N * (N + 1) // 2
print('{}'.format(result))
N, M = map(int, input().split())
S = list(input())

n = 0
move = []
while n != N:
    for i in range(M, 0, -1):
        if n + i > N:
            continue

        if S[n + i] != '1':
            n = n + i
            move.append(i)
            break
    else:
        print(-1)
        exit()


i = len(move) - 1
move.sort()
n = N
ans = []
while move:
    if S[n - move[i]] != '1':
        ans.append(move[i])
        n -= move[i]
        del move[i]
        i = len(move) - 1
    else:
        i -= 1

print(*ans[::-1])


### FIXED CODE ###

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


# 後ろから貪欲
ans = []
position = N
while position > 0:
    for move in range(M, 0, -1):
        if position - move < 0:
            continue

        if S[position - move] == '1':
            continue

        ans.append(move)
        position -= move
        break
    else:
        print(-1)
        exit()

print(*ans[::-1])
n,k = map(int,input().split())
A = list(map(int,input().split()))
B = []
b = 1
ans = 1
while ans:
  b = A[b-1]
  B.append(b)
  if len(A) == len(B):
    ans = 0
B = B*1000000000
print(B[k-1])

### FIXED CODE ###

N,K = map(int,input().split())
A = list(map(int,input().split()))
pos = 0
visit = [0] * N
move = []
roop = []
while visit[pos]!=2:
    if visit[pos]==0:
        move.append(pos)
    else:
        roop.append(pos)
    visit[pos] += 1
    pos = A[pos] - 1
if len(move)>K:
    print(move[K]+1)
else:
    print(roop[(K-(len(move)-len(roop)))%len(roop)]+1)
ans=-1
n,m=map(int,input().split())
l=[list(map(int,input().split())) for i in range(m)]
for k in range(10**(n-1)-1,10**n):
    for i in range(m):
        if str(k)[l[i][0]-1]!=str(l[i][1]) or len(str(k))!=n:
            break
    else:
        ans=k
        break
print(ans)

### FIXED CODE ###

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

for x in range(1000):
    if len(str(x))==n:
        for i in range(m):
            if str(x)[sc[i][0]-1]==str(sc[i][1]):
                continue
            else:
                break
        else:
            print(x)
            break
else:
    print(-1)
p,q,r = map(int, input().split())
print(min(p+q, q+r, r+s))

### FIXED CODE ###

p,q,r = map(int, input().split())
print(min(p+q, q+r, r+p))
,y = map(int,input().split())

ans = 0
for i in range(1000):
    if ans != 0:
        break
    else:
        for j in range(1000):
            for k in range(1000):
                if (i + k + j)== n and (10000*i + 5000*j + 1000*k) == y:
                    print(i,j,k)
                    ans +=1
                else:
                    continue
                
if ans == 0:
    print('-1','-1','-1')

### FIXED CODE ###

n,y = map(int,input().split())

ans = 0
for i in range(2001):
    if ans != 0:
        break
    else:
        for j in range(2001-i):
            if (10000*i + 5000*j + 1000*(n-(i + j))) == y and ((n-(i + j)) >=0):       
                print(i,j,n-(i + j))
                ans +=1
            else:
                continue
                
if ans == 0:
    print('-1','-1','-1')
from functools import lru_cache
dan,ana=map(int,input().split())
l=[int(input()) for _ in range(ana)]
@lru_cache(maxsize=float('inf'))
def f(x,*li):
  if x in li:return 0
  elif x==1:return 1
  elif x==2:return f(1,*li)+1
  else:return (f(x-1,*li)+f(x-2,*li))%(10**9+7)

print(f(dan,*l))

### FIXED CODE ###

n,m=map(int,input().split())
l={int(input()) for i in range(m)}
dp=[0 for i in range(n+1)]
dp[0]=1
for i in range(1,1+n):
    if i not in l:dp[i]+=dp[i-1]+dp[i-2];dp[i]%=10**9+7
print(dp[n])
a,b,k=map(int,input().split())
"""
if b-a+1<=2*k:
            for i in range(a,b+1):
                        print(i)
else:
            for i in range(a,a+k):
                        print(i)
            for i in range(b-k+1,b+1):
                        print(i)

"""
for i in range(a,b+1):
            #print("i",i)
            if i<a+k:
                        print(i)
            elif b-k<i:
                        print(i)
"""                    
            
                        


### FIXED CODE ###

a,b,k=map(int,input().split())

if b-a+1<=2*k:
            for i in range(a,b+1):
                        print(i)
else:
            for i in range(a,a+k):
                        print(i)
            for i in range(b-k+1,b+1):
                        print(i)

"""
for i in range(a,b+1):
            #print("i",i)
            if i<a+k:
                        print(i)
            elif b-k<i:
                        print(i)
"""
n, m = map(int, input().split())

adj = [[] for _ in range(m)]

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

from collections import deque
q = deque()

dist = [-1]*n
ans = [0]*n

q.append(0)
while len(q) != 0:
    now = q.popleft()
    for to in adj[now]:
        if dist[to] != -1: continue
        dist[to] = dist[now] + 1
        q.append(to)
        ans[to] = now 
    
print("Yes")
for i in range(1,n):
    print(ans[i]+1)


### FIXED CODE ###

n, m = map(int ,input().split())
 
adj = [[] for _ in range(n)]
 
for i in range(m):
    a, b = map(int, input().split())
    a-=1
    b-=1
    adj[a].append(b)
    adj[b].append(a)
 
from collections import deque
q = deque()
 
dist = [-1] * n
ans = [0] * n
 
q.append(0)
while len(q) != 0:
    now = q.popleft()
    for to in adj[now]:
        if dist[to] != -1:continue
        dist[to] = dist[now] + 1
        q.append(to)
        ans[to] = now
 
print("Yes")
for i in range(1, n):
    print(ans[i] + 1)
list = []
n = input()
for i in range(n):
    a,b=input().split()
    list.append((int(a), int(b)))
for i in n-2:
  if list[i][0] == list[i][1] and list[i+1][0] == list[i+1][1] and list[i+2][0] == list[i+2][1]:
	print("Yes")
  return 0

print("No")


### FIXED CODE ###

ans = "No"
count = 0
n = int(input())
for i in range(n):
  a,b=map(int,input().split())
  if a == b:
    count += 1
    if count >= 3:
        ans ="Yes"
  else:
    count = 0

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

cost = [2,5,5,4,5,6,3,7,6]


def solve(N, num=0):
    if N < 0:
        return -1
    if N == 0:
        return num
    ans = 0
    for a in A:
        tmp_num = num
        if tmp_num == 0:
            tmp_num += a
        else:
            tmp_num += a*(10**len(str(tmp_num)))
        ans = max(solve(N-cost[a-1],tmp_num),ans)
    return ans

print(solve(N))

### FIXED CODE ###

N, M = map(int,input().split())
A = list(map(int, input().split()))
cost = [2,5,5,4,5,6,3,7,6]

dp = [-1 for _ in [0]*(N+10)]
dp[0] = 0

for i in range(N+1):
    for a in A:
        if i-cost[a-1] < 0 or dp[i-cost[a-1]] < 0:
            continue
        if dp[i-cost[a-1]]*10 + a > dp[i]:
            dp[i] = dp[i-cost[a-1]]*10 + a
print(dp[N])
import math

def fact(N):
    total = 1
    for i in range(1, N+1):
        total = total * i
    return total

def comb(a, b):
    return fact(a) / (fact(a-b) * fact(b))

def main():
    N, K = list(map(int, input().split(" ")))
    for i in range(1, K+1):
        #blue cluster
        comb1 = int(comb(N-K+1, i))
        comb2 = int(comb(K-1, i-1))
        total_comb = comb1 * comb2
        ans = total_comb%(10**9+7)
        print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import math

def fact(N):
    total = 1
    for i in range(1, N+1):
        total = total * i
    return total

def comb(a, b):
    return fact(a) // (fact(a-b) * fact(b))


def main():
    N, K = list(map(int, input().split(" ")))
    a = N - K + 1
    b = 1
    mod = 1000000007
    ans = ((a % mod) * (b % mod)) % mod
    print(ans)
    for i in range(1, K):
        tmp_a = (N-K+1-i)
        if tmp_a == 0:
            tmp_a = 1
        tmp_b = (K-1-i+1)
        if tmp_b == 0:
            tmp_b = 1
        a = (a * tmp_a) // (i+1)
        b = (b * tmp_b) // i
        ans = ((a % mod) * (b % mod)) % mod
        print(ans)

if __name__ == '__main__':
    main()
nk = list(input().split())
n = nk[0]
k = nk[1]
a = []
c = 0
for i in range(k):
  d = int(input())
  b = list(input().split())
  a.extend(b)
for j in range(1,n+1):
  if j not in a:
    c = c+1
print(c)

### FIXED CODE ###

nk = list(input().split())
n = nk[0]
k = nk[1]
a = []
c = 0
for i in range(int(k)):
  d = int(input())
  b = list(input().split())
  a.extend(b)
for j in range(1,int(n)+1):
  if str(j) not in a:
    c = c+1
print(c)
n, m = map(int, input().split())
a = list(map(int, input().split()))
ticket_num = m
a_sorted = sorted(a, reverse=True)

if n > 1:
    while ticket_num > 0:
        first = a_sorted[0]
        second = a_sorted[1]
        fi_bin = bin(first)
        se_bin = bin(second)
        sa = len(fi_bin)-len(se_bin)
        if sa == 0:
            sa = 1
        first = first >> sa
        ticket_num -= sa
        if first == second:
            first = first >> 1
            ticket_num -= 1
        index = 1
        while a_sorted[index] > first:
            index += 1
        a_sorted[:index-1] = a_sorted[1:index]
        a_sorted[index-1] = first
else:
    a_sorted[0] = a_sorted[0]>>m

print(sum(a_sorted))

### FIXED CODE ###

import heapq
import math
n, m = map(int, input().split())
a = list(map(int, input().split()))
a = list(map(lambda x: x*(-1), a))
ticket_num = m
heapq.heapify(a)

if n > 1:
    for i in range(m):
        MAX = heapq.heappop(a)
        MAX = math.ceil(MAX / 2)
        heapq.heappush(a,MAX)
        
else:
    MAX = heapq.heappop(a)
    MAX = math.ceil(MAX / (2**m))
    heapq.heappush(a,MAX)

print(sum(a)*(-1))
from math import abs
def main():
	n = int(input())
	costs = list(map(int, input().split()))
	
	# each cur represents minimum cost needed to reach the step
	two_before = 0
	one_before = costs[1] - costs[0]
	for step in range(2, n):
		two_before, one_before = one_before, min(one_before + abs(costs[step] - costs[step-1]), two_before + abs(costs[step] - costs[step - 2]))
	return one_before
main()

### FIXED CODE ###

def main():
	n = int(input())
	costs = list(map(int, input().split()))
	
	if n==1: return 0
	# each cur represents minimum cost needed to reach the step
	two_before = 0
	one_before = abs(costs[1] - costs[0])
	for step in range(2, n):
		two_before, one_before = one_before, min(one_before + abs(costs[step] - costs[step-1]), two_before + abs(costs[step] - costs[step - 2]))
	return one_before


print(main())
def f(a):
  if a%2 == 0:
    return a//2
  else:
    return 3*a+1

s = int(input())
a = [s]
i=2
 
while(True):
  a.append(f(a[i-2]))
  if a[i-1] in a[:i-1]:
    print(i)
    break
  i=i+1


### FIXED CODE ###

a, b, _ = input().split()

print(int(a) * int(b) // 2)