Harryxun/stf_run huggingface dataset:
class Node:
    def __init__(self, val):
        self.num = val
        self.nodes = []
        self.distance = []

def set_color(node, color):
    if color_list[node.num] == None:
        color_list[node.num] = color
        for child, dist in zip(node.nodes, node.distance):
            if child != node:
                if dist == 0:
                    set_color(child, color)
                else:
                    set_color(child, not color)

N= int(input())

node_list = [Node(i) for i in range(N)]
color_list = [None for i in range(N)]

for i in range(N-1):
    u, v, w = map(int, input().split())
    x = node_list[u-1]
    y = node_list[v-1]
    w = w % 2
    x.nodes.append(y)
    x.distance.append(w)
    y.nodes.append(x)
    y.distance.append(w)

set_color(node_list[0], True)

for i in color_list:
    if i:
        print(1)
    else:
        print(0)


### FIXED CODE ###

import sys
from collections import deque
input = sys.stdin.readline

class Node:
    def __init__(self):
        self.color = 0
        self.check = False
        self.link = []

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

    nodes = [Node() for i in range(N)]
    
    for i in range(N-1):
        u, v, w = map(int, input().split())
        nodes[u-1].link.append((nodes[v-1], w&1))
        nodes[v-1].link.append((nodes[u-1], w&1))
    
    q = deque()
    q.append((nodes[0], 1))
    while len(q) > 0:
        node, color = q.popleft()
        node.color = color
        node.check = True
        for nex, weight in node.link:
            if not nex.check:
                if weight == 0:
                    q.append((nex, color))
                else:
                    q.append((nex, -color))
    
    for i in range(N):
        print((nodes[i].color + 1) // 2)

if __name__ == "__main__":
    main()
n,k = map(int,input().split())
P = list(map(int,input().split()))

P = [(v+1)/2 for v in P]

acum = [0]*(n+1)
for i in range(n):
  acum[i+1] = acum[i] + P[i]
  
total = [0]*k
for i in range(k):
  total[i] = acum[i+k]-acum[i]  
  
print(max(total))  

### FIXED CODE ###

n,k = map(int,input().split())
P = list(map(int,input().split()))

P = [(v+1)/2 for v in P]

acum = [0]*(n+1)
for i in range(n):
  acum[i+1] = acum[i] + P[i]
  
total = [0]*(n-k+1)
for i in range(n-k+1):
  total[i] = acum[i+k]-acum[i]  
  
print(max(total))
from heapq import*
(N,M),*t=[map(int,s.split())for s in open(0)]
z,*q=[0]*50*M
v=[[]for _ in q]
for a,b in t:v[a-1]+=b,
for i in v[:M]:z-=[heappush(q,-j)for j in i]or heappop(q)
print(z)

### FIXED CODE ###

from collections import*
from heapq import*
n,m,*t=map(int,open(0).read().split())
d=defaultdict(list)
for a,b in zip(t[::2],t[1::2]):d[a].append(b)
q=[]
for i in sorted(d.keys())[::-1]:
    for b in sorted(d[i])[::-1][:m-i+1]:
        if len(q)<=m-i:heappush(q,b)
        elif q and q[0]<b:heappushpop(q,b)
print(sum(q))
K, N = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]

b = A[0]+(K-A[N-1])

for i in range(1,N):
    a = max(A[i]-A[i-1])

c = max(a,b)

print(K-c)


### FIXED CODE ###

k,n = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
c = a[0] + (k - a[n-1])
for i in range(1,n):
  c = max(c,a[i] - a[i-1])
print(k-c)
in = input()
h=in/3600
m=in/60-60*h
s=in%60
print(str(h)+':'+str(m)+':'+str(s))

### FIXED CODE ###

a =int(input())
h=int(a/3600)
m=int(a/60-60*h)
s=a%60
print(str(h)+':'+str(m)+':'+str(s))
S = input()

count=0

for i in range(len(S) // 2):
    if S[i] != RS[-1-i]:
        count += 1

print(count)


### FIXED CODE ###

S = input()


count=0

for i in range(len(S) // 2):
    if S[i] != S[-1-i]:
        count += 1

print(count)
def main():
    from collections import Counter
    from bisect import bisect
    import sys
    input = sys.stdin.buffer.readline

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

    ans = 0
    A.sort(reverse=True)
    c = Counter(A)
    bi = [2**i for i in range(1, 15)]

    for b in A:
        a = (bi[bisect(bi, b)]) - b
        if a == b:
            ans += c[b]//2
            c[b] %= 2
        else:
            if a in c.keys():
                cur = min(c[a], c[b])
                ans += cur
                c[b] -= cur
                c[a] -= cur
        # print(a, b, c, ans)

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    from collections import Counter
    import sys
    input = sys.stdin.buffer.readline

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

    ans = 0
    A.sort(reverse=True)
    c = Counter(A)

    for b in A:
        if c[b] == 0:
            continue
        a = (2 ** b.bit_length()) - b
        if a == b:
            cur = c[b]//2
        else:
            cur = min(c[a], c[b])
        ans += cur
        c[b] -= cur
        c[a] -= cur
        # print(a, b, c, ans)

    print(ans)


if __name__ == '__main__':
    main()
a , b = map(int(),input().split())

X = 0
Y = 0

if a < b:
	for i in b:
		X = 'X' + 'a'
    print(X)

else:
	for v in a:
		Y = 'Y' + 'b'
	print(Y)

### FIXED CODE ###

a , b =input().split()
 
if a <= b:
    print(a*int(b))
else:
	print(b*int(a))
a,b,c = map(int, input().split())
print(min(c, b//a)

### FIXED CODE ###

a,b,c = map(int, input().split())
print(min(c, b//a))
patterns = ['dream', 'dreamer' , 'erase', 'eraser'] 

def check(string):
  l = len(string)

  if l == 0:
    return True
  
  if l < 5:
    return False

  if string[0:5] == 'dream':
    if check(string[5:]):
      return True
    if l >= 7 and check(string[7:]):
      return True
  elif string[0:5] == 'erase':
    if check(string[5:]):
      return True
    if l >= 6 and check(string[6:]):
      return True
  else:
    return False
  
  return False

S = input()
if check(S):
  print("YES")
else:
  print("NO")


### FIXED CODE ###

# dream = list(reversed('dream'))
# dreamer = list(reversed('dreamer'))
# erase = list(reversed('erase'))
# eraser = list(reversed('eraser'))

# def check(string):
#   l = len(string)

#   if l == 0:
#     return True
  
#   if l < 5:
#     return False

#   if string[0:5] == dream:
#     return check(string[5:])
#   if l >= 7 and string[0:7] == dreamer:
#     return check(string[7:])
#   if string[0:5] == erase:
#     return check(string[5:])
#   if l >= 6 and string[0:6] == eraser:
#     return check(string[6:])
      
#   return False

# S = input()
# S = list(reversed(S))
# if check(S):
#   print("YES")
# else:
#   print("NO")

s = input()
 
while len(s) > 4:
    if s[-5:] == 'dream':
        s = s[:-5]
    elif s[-7:] == 'dreamer':
        s = s[:-7]
    elif s[-5:] == 'erase':
        s = s[:-5]
    elif s[-6:] == 'eraser':
        s = s[:-6]
    else:
        break
 
print('NO' if len(s) > 0 else 'YES')
import sys
def main():
  input = sys.stdin.readline
  h, w = map(int, input().split())
  A = []
  AB = []
  A_append = A.append
  AB_append = AB.append
  for i in range(h):
    row = list(map(int, input().split()))
    A_append(row)
  for i in range(h):
    row = [abs(A[i][j] - int(b)) for j, b in enumerate(input().split())]
    AB_append(row)
 
  dp_cur = [set([]) for _ in range(w)]
  dp_cur[0].add(AB[0][0])
  for i in range(h):
    dp_next = [set([]) for _ in range(w)]
    for j in range(w):
      if j < w - 1:
        add1 = dp_cur[j+1].add
        dif1 = AB[i][j+1]
      if i < h - 1:
        add2 = dp_next[j].add
        dif2 = AB[i+1][j]
      for item in dp_cur[j]:
        if j < w - 1:
          add1(item+dif1)
          add1(abs(item-dif1))
        if i < h - 1:
          add2(item+dif2)
          add2(abs(item-dif2))
    dp_cur = dp_next
  print(min(dp_cur[w-1]))
if __name__ == '__main__':
  main()


### FIXED CODE ###

import sys
def main():
  input = sys.stdin.readline
  h, w = map(int, input().split())
  A = []
  AB = []
  A_append = A.append
  AB_append = AB.append
  for i in range(h):
    row = list(map(int, input().split()))
    A_append(row)
  for i in range(h):
    row = [abs(A[i][j] - int(b)) for j, b in enumerate(input().split())]
    AB_append(row)
 
  dp_cur = [set([]) for _ in range(w)]
  dp_cur[0].add(AB[0][0])
  for i in range(h):
    dp_next = [set([]) for _ in range(w)]
    for j in range(w):
      if j < w - 1:
        add1 = dp_cur[j+1].add
        dif1 = AB[i][j+1]
      if i < h - 1:
        add2 = dp_next[j].add
        dif2 = AB[i+1][j]
      for item in dp_cur[j]:
        if j < w - 1:
          add1(item+dif1)
          add1(abs(item-dif1))
        if i < h - 1:
          add2(item+dif2)
          add2(abs(item-dif2))
    if i == h - 1:
      break
    dp_cur = dp_next
  print(min(dp_cur[w-1]))
if __name__ == '__main__':
  main()
print(len(set(input() for i in range(int(input()))))

### FIXED CODE ###

print(len(set(input() for i in range(int(input())))))
n = int(input())
a = [int(i) for i in input().split()]
a.sort()
out = 0
if n == 1:
    if a[0] != 0:
        out = 1
elif a[0] == 0:
    for i in range(1,n//2+1):
        if a[2*i-1] == a[2*i] and a[2*i] == 2*i:
            None
        else:
            out = 1
elif a[0] == 1:
    for i in range(n//2):
        if a[2*i] == a[2*i+1] == 2*i+1:
            None
        else:
            out = 1
else:
    out = 1
if out:
    print(0)
else:
    print(2**(n//2)%(10**9+7))


### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split()]
a.sort()
out = 0
if n == 1:
    if a[0] != 0:
        out = 1
elif a[0] == 0:
    if n%2 == 0:
        out = 1
    else:
        for i in range(1,n//2+1):
            if a[2*i-1] == a[2*i] and a[2*i] == 2*i:
                None
            else:
                out = 1
elif a[0] == 1:
    if n%2 == 1:
        out = 1
    else:
        for i in range(n//2):
            if a[2*i] == a[2*i+1] == 2*i+1:
                None
            else:
                out = 1
else:
    out = 1
if out:
    print(0)
else:
    a = 1
    for i in range(n//2):
        a *= 2
        a = a%(10**9+7)
    print(a)
x,y = map(int, input().split())
cnt2 = 0
cnt4 = 0
for i in range(x+1):
    cnt2 = 2*(i)
    cnt4 = 4*(x-i)
    if cnt2 + cnt4 == y:
        print("Yes")
        exit()

print("No")


### FIXED CODE ###

a,b,c,d,e = map(int, input().split())
if a ==0:
    print(1)
    exit()
elif b ==0:
    print(2)
    exit()
elif c ==0:
    print(3)
    exit()
elif d ==0:
    print(4)
    exit()
else:
    print(5)
n,k = map(int,input().split())
r = [int(i) for i in input().split()]
t = list(input())
for i in range(n):
    if t[i]=='r':
        t[i]=0
    elif t[i]=='s':
        t[i]=1
    else:
        t[i]=2
#グーを０にチョキを１にパーを2に書き換える
ans = 0
dasite = []
for i in range(n):
    if i<k:
        ans = func(t[i],ans)
    elif i>=n-k:
        if dasite[i-k]==(t[i]+2)%3:
            print(i,t[i])
            continue
        else:
            ans = func(t[i],ans)
    else:
        if dasite[i-k]==(t[i]+2)%3:
            if t[i]==t[i+k]:
                dasite.append(t[i])
            elif t[i]==(t[i+k]+1)%3:
                dasite.append((t[i+k]+1)%3)
            else:
                dasite.append(t[i])
        else:
            ans = func(t[i],ans)
print(ans)

### FIXED CODE ###

n,k = map(int,input().split())
r = [int(i) for i in input().split()]
t = list(input())
def func(d,ans):
    if d==0:
        ans += r[2]
        dasite.append(2)
    elif d==1:
        ans += r[0]
        dasite.append(0)
    else:
        ans += r[1]
        dasite.append(1)
    return ans

for i in range(n):
    if t[i]=='r':
        t[i]=0
    elif t[i]=='s':
        t[i]=1
    else:
        t[i]=2
#グーを０にチョキを１にパーを2に書き換える
ans = 0
dasite = []
for i in range(n):
    if i<k:
        ans = func(t[i],ans)
    elif i>=n-k:
        if dasite[i-k]==(t[i]+2)%3:
            continue
        else:
            ans = func(t[i],ans)
    else:
        if dasite[i-k]==(t[i]+2)%3:
            if t[i]==t[i+k]:
                dasite.append(t[i])
            elif t[i]==(t[i+k]+1)%3:
                dasite.append(t[i+k])
            else:
                dasite.append((t[i]+1)%3)
        else:
            ans = func(t[i],ans)
print(ans)
import os 
a,b = os.read(0,100).split(b' ')
a = int(a.decode())
b = int(b.decode())
print(max(a-b,0))
os.write(1,' '.join(str(a),str(b)).encode())

### FIXED CODE ###

import os 
a,b = os.read(0,100).split(b' ')
a = int(a.decode())
b = int(b.decode())
print(max(a-b,0))
N = int(input())
A = list(map(int, input().split()))
C=0
while True:
  for i in A:
    if i%2 != 0::
        print(C)
        exit()
    A[i]/=2
    C+=1

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
count = 0
while True:
  for i in range(N):
    if A[i]%2 != 0:
      print(count)
      exit()
    A[i] /= 2
  count+=1
import math

N = int(input())
A = N
S = []
for i in range(N):
    S += [input()]
for j in range (1, N):
    for k in range(j):
        if S[k] == S[j]:
            A -= 1
            break
print(A)


### FIXED CODE ###

S, W = map(int, input().split())

if S > W:
    print('safe')
else:
    print('unsafe')
inp = [int(i) for i in raw_input().split()]

sorted_inp = sorted(inp)

diff = 0

for i in range(len(inp)):
  if inp[i] != sorted_inp[i]:
    diff += 1

if diff ==  or diff==2:
  print "YES"
else:
  print "NO"

### FIXED CODE ###

N = int(raw_input())
inp = [int(i) for i in raw_input().split()]

sorted_inp = sorted(inp)

diff = 0

for i in range(len(inp)):
  if inp[i] != sorted_inp[i]:
    diff += 1

if diff == 0 or diff==2:
  print "YES"
else:
  print "NO"
n, m = map(int, input().split())
a = []
dp = [0]*(n+1)
mod = 10**9+7

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

if 1 in a and 2 in a:
    print(0)
    exit()
elif 1 in a and 2 not in a:
    dp[1] = 0
    dp[2] = 1
elif 1 not in a and 2 in a:
    dp[1] = 1
    dp[2] = 0
else:
    dp[1] = 1
    dp[2] = 2

for i in range(3, n+1):
    if i in a:
        dp[i] = 0
    else:
        dp[i] = (dp[i-1] + dp[i-2]) % mod

print(dp[n])






### FIXED CODE ###

n, m = map(int, input().split())
a = []
# dp = [0]*(n+1)
dp = [None]*(10**5+1)
mod = 10**9+7
dp[0] = 0

for i in range(m):
    ng = int(input())
    a.append(ng)
    dp[ng] = 0

if 1 in a and 2 in a:
    print(0)
    exit()
elif 1 in a and 2 not in a:
    dp[1] = 0
    dp[2] = 1
elif 1 not in a and 2 in a:
    dp[1] = 1
    dp[2] = 0
else:
    dp[1] = 1
    dp[2] = 2

for i in range(3, n+1):
    if dp[i] is None:
        dp[i] = (dp[i-1] + dp[i-2]) % mod

print(dp[n])
mozi = str(input())
for i in mozi:
  i == chr(x)
  print(i)

### FIXED CODE ###

mozi = str(input())
s = str()
for i in range(len(mozi)):
  s += str("x")
print(s)
# 1. 最大公約数を求める(ユークリッドの互除法)
# 2. 最大公約数を素因数分解する。
# 3. 2.の結果に含まれる素因数の種類の数＋１が答え

def main():
  a, b = sorted(list(map(int, input().split())), reverse = True)
  while b! = 0:
    a, b = b, a % b
  print(num_facto(a) + 1)  
  
def num_facto(n):
  ans = 0
  max_n = int((n ** 0.5) // 1) + 1
  is_prime = [True for x in range(max_n + 1)]
  is_prime[0], is_prime[1] = False, False
  for cursor in two_and_odds(max_n):
    if is_prime[cursor]:
      if n % cursor == 0:
        ans += 1
        while n % cursor == 0:
          n = n // cursor
      for i in range(cursor, max_n, cursor):
        is_prime[i] = False
  if n != 1:
    ans += 1
  return ans

def two_and_odds(max_n):
  if max_n >= 2:
  	yield 2
  for i in range(3, max_n, 2):
    yield i
    
if __name__ == "__main__":
  main()


### FIXED CODE ###

# 1. 最大公約数を求める(ユークリッドの互除法)
# 2. 最大公約数を素因数分解する。
# 3. 2.の結果に含まれる素数＋１が答え

import itertools
from fractions import gcd
from math import ceil

def main():
  a, b = map(int, input().split())
  fac = facto(gcd(a,b))
  print(len(fac))  
  
def facto(n):
  fac = [1]
  if n == 1:
    return [1]
  elif n % 2 == 0:
    fac = [1, 2]
    while n % 2 == 0:
      n = n // 2
  
  max_n = ceil(n ** 0.5) + 1
  
  is_prime = [True for x in range(max_n)]
  for cursor in range(3, max_n, 2):
    if is_prime[cursor]:
      if n % cursor == 0:
        fac.append(cursor)
        while n % cursor == 0:
          n = n // cursor
        if n == 1:
          break
      for i in range(cursor, max_n, cursor):
        is_prime[i] = False
  if n != 1:
    fac.append(n)
  return fac

if __name__ == "__main__":
  main()
import copy 

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

N = int(input())
T = list(map(int,input().split()))
LIS = [0]*N
LIS[0] += T[0]
for i in range(N-1):
    LIS[i+1] += gcd(LIS[i],T[i+1])
F = LIS.index(min(LIS))
if F == 1:
    U = copy.copy(T)
    V = copy.copy(T)
    U.pop(1)
    V.pop(0)
    LU = [0]*(N-1)
    LU[0] = U[0]
    LV = [0]*(N-1)
    LV[0] = V[0]
    ANSU = 0
    ANSV = 0
    for i in range(N-2):
        LU[i+1] += gcd(LU[i],U[i+1])
    ANSU = LU[N-2]
    for i in range(N-2):
        LV[i+1] += gcd(LV[i],V[i+1])
    ANSV = LV[N-2]
    ANS = max(ANSU,ANSV)
else:
    S = copy.copy(T)
    S.pop(F)
    LS = [0]*(N-1)
    LS[0] += S[0]
    for i in range(N-2):
        LS[i+1] += gcd(LS[i],S[i+1])
        ANS = LS[N-2]

print(ANS)

### FIXED CODE ###

import copy 

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

N = int(input())
T = list(map(int,input().split()))
T.sort()
LIS = [0]*N
LIS[0] += T[0]
for i in range(N-1):
    LIS[i+1] += gcd(LIS[i],T[i+1])
F = LIS.index(min(LIS))
if len(T) == 2:
    ANS = max(T[0],T[1])
elif F == 0:
    U = copy.copy(T)
    V = copy.copy(T)
    U.pop(1)
    V.pop(0)
    LU = [0]*(N-1)
    LU[0] = U[0]
    LV = [0]*(N-1)
    LV[0] = V[0]
    for i in range(N-2):
        LU[i+1] += gcd(LU[i],U[i+1])
    ANSU = LU[N-2]
    for i in range(N-2):
        LV[i+1] += gcd(LV[i],V[i+1])
    ANSV = LV[N-2]
    ANS = max(ANSU,ANSV)
    
else:
    U = copy.copy(T)
    V = copy.copy(T)
    U.pop(F)
    V.pop(0)
    LU = [0]*(N-1)
    LU[0] = U[0]
    LV = [0]*(N-1)
    LV[0] = V[0]
    ANSU = 0
    ANSV = 0
    for i in range(N-2):
        LU[i+1] += gcd(LU[i],U[i+1])
    ANSU = LU[N-2]
    for i in range(N-2):
        LV[i+1] += gcd(LV[i],V[i+1])
    ANSV = LV[N-2]
    ANSP = max(ANSU,ANSV)
    ANS = max(ANSP,LIS[N-1])
        
print(ANS)
a,b,c=map(int,input().split())

if a<c<b or b<c<a:
    print("Yes")
else
    print("No")




### FIXED CODE ###

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

if a<c<b or b<c<a:
    print("Yes")
else:
    print("No")
from math import *
PI = 3.1415926535898
pool = []
pool.append("1100000011")
pool.append("1000000010000000100000001")
pool.append("1111")
pool.append("1000000110000001")
pool.append("11000000011")
pool.append("100000001100000001")
pool.append("110000011")
while True:
	try:
		pat = ""
		for i in range(8):
			pat += str(raw_input())
		flag = False
		tp = ""
		for x in pat:
			if x != '0':
				flag = True
			if flag:
				tp += x
		pat = reversed(tp)
		flag = False
		tp = ""
		for x in pat:
			if x != '0':
				flag = True
			if flag:
				tp += x
		pat = tp
		print chr(pool.index(pat) + ord('A'))
	except EOFError:
		break

### FIXED CODE ###

from math import *
PI = 3.1415926535898
pool = []
pool.append("1100000011")
pool.append("1000000010000000100000001")
pool.append("1111")
pool.append("1000000110000001")
pool.append("11000000011")
pool.append("100000001100000001")
pool.append("110000011")
while True:
	try:
		pat = ""
		for i in range(8):
			s = str(raw_input())
			while len(s) == 0:
				s = str(raw_input())
			pat += s
		flag = False
		tp = ""
		for x in pat:
			if x != '0':
				flag = True
			if flag:
				tp += x
		pat = reversed(tp)
		flag = False
		tp = ""
		for x in pat:
			if x != '0':
				flag = True
			if flag:
				tp += x
		pat = tp
		print chr(pool.index(pat) + ord('A'))
	except EOFError:
		break
N = int(input())
A = list(map(int, input().split()))
res = 1

if 0 in A :
    res = 0
    N = 0

for x in range(N) :
    res *= A[x]
    if res > 10**18
        res = -1
        break

print(res)

### FIXED CODE ###

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

limit = 10 ** 18
A.sort()
result = A[0]
for a in A[1:]:
    result *= a
    if result > limit:
        print(-1)
        exit()
print(result)
a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())
q = int(input())

f = [a,b,c,d,e]
f.sort()

g = f[1]-f[0]
h = f[2]-f[0]
i = f[3]-f[0]
j = f[4]-f[0]
k = f[2]-f[1]
l = f[3]-f[1]
m = f[4]-f[1]
n = f[3]-f[2]
o = f[4]-f[2]
p = f[4]-f[3]

if g<q and h<q and i<q and j<q and k<q and l<q and m<q and m<q and n<q and o<q p<q:
  print("Yay!")

else:
  print(":(")
  
  













### FIXED CODE ###

a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())
q = int(input())
 
f=e-d
g=e-c
h=e-b
i=e-a
j=d-c
k=d-b
l=d-a
m=c-b
n=c-a
o=b-a

 
 
if f<=q and g<=q and h<=q and i<=q and j<=q and k<=q and l<=q and m<=q and n<=q and o<=q:
  print("Yay!")
 
else:
  print(":(")
n,k=map(int,input().split())
h=list(map(int,input().split()))
flog=[-1]*n
#初期値は0
def Num(dest):
    if flog[dest-1]!=-1:
        return flog[dest-1]
    if dest<k+2:
        res=abs(h[dest-1]-h[0])
        flog[dest-1]=res
        return res
    else:
        min=10**4*n
        for i in range(1,k+1):
            tmp=Num(dest-i)+abs(h[dest-1]-h[dest-i-1])
            if min>tmp:
                min=tmp
        flog[dest-1]=min
        return min
          

    
print(Num(n))

### FIXED CODE ###

import sys
sys.setrecursionlimit(400000000)
def main():
    n,k=map(int,input().split())
    h=tuple(map(int,input().split()))
    flog=[-1]*n
    for i in range(n):#dest=i 0が１
        if i<k+1:#0~k
            flog[i]=abs(h[i]-h[0])
        else:
            min=10**9
            for j in range(1,k+1):#1~k
                tmp=flog[i-j]+abs(h[i]-h[i-j])
                if tmp<min:
                    min=tmp
            flog[i]=min
    print(flog[n-1])
   # print(flog)
if __name__=="__main__":
    main()
n = int(input())
d = sorted([int(input()) for _ in range(n)])
cnt = 1
for a, b in zip(cnt[1:], cnt):
    if a > b:
        cnt += 1
print(cnt)


### FIXED CODE ###

N = int(input())
d = set([int(input()) for _ in range(N)])
print(len(d))
n=int(input())
a=[0]+list(map(int,input().split()))+[0]

ans=0
x=0

for i in a:
  ans+=abs(i-x)
  x=i

for i in range(1,len(a)-1):
  pin=ans
  if a[i-1]<=a[i]<=a[i+1] or a[i-1]>=a[i]>=a[i+1]:
      print(pin)

  else:
      pin-=abs(a[i]-a[i-1])
      pin-=abs(a[i+1]-a[i])
      pin+-abs(a[i+2]-a[i])
  
      print(pin)

### FIXED CODE ###

n=int(input())
a=[0]+list(map(int,input().split()))+[0]

dist=[]

for i in range(len(a)-1):
  dist.append(abs(a[i+1]-a[i]))
  
xxx=sum(dist)

for i in range(n):
  ans=xxx
  ans-=dist[i]
  ans-=dist[i+1]
  ans+=abs(a[i+2]-a[i])
  print(ans)
import fractions

n=int(input())
t=list(int(input()) for i in range(n))

for i in range(n-1):
    ans=t[i]*t[i+1]//fractions.gcd(t[i],t[i+1])
    
print(ans)
        

### FIXED CODE ###

import fractions

n=int(input())
t=list(int(input()) for i in range(n))
ans=t[0]
for i in range(n-1):
    ans=ans*t[i+1]//fractions.gcd(ans,t[i+1])
    
    
print(ans)
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
tmp = 0

for i in range(n):
    if a[i+1] == a[i]+1:
        tmp += c[a[i]-1]

print(sum(b)+tmp)

### FIXED CODE ###

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

for i in range(n-1):
    if a[i+1] == a[i]+1:
        b.append(c[a[i]-1])

print(sum(b))
import functools, fractions
 
def lcm(a, b):
    return a * b // fractions.gcd(a, b)
 
def check(L, NM):
    res = []
    for i in range(NM):
        res.append(int(i*(L/NM)+1))
    return res
 
def check2(x, L, NM):
    return int((x-1)*NM/L)
 
 
def main():
    N,M = map(int,input().split())
    S = input()
    T = input()
    L = lcm(N,M)
    ans = L
 
 
    a = list(set(check(L, N)) & set(check(L, M)))
    for i in a:
        if S[check2(i, L, N)] != T[check2(i, L, M)]:
            ans = -1
            break
    print(ans)
if __main__ == '__main__':
  main()

### FIXED CODE ###

import functools, fractions

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

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

def check(L, NM):
    res = []
    for i in range(NM):
        res.append(int(i*(L/NM)+1))
    return res

def check2(x, L, NM):
    return int((x-1)*NM/L)

L = lcm(N,M)
ans = L


a = list(set(check(L, N)) & set(check(L, M)))
for i in a:
    if S[check2(i, L, N)] != T[check2(i, L, M)]:
        ans = -1
        break
print(ans)