Harryxun/stf_run huggingface dataset:
N = int(input())
a = list(map(int, input().split()))

t = [0] * N
for i in range(N, -1, -1):
    t[i] = (sum(t[2 * i - 1::i]) % 2) ^ a[i - 1]

print(sum(t))
print(*[i + 1 for i in range(N) if t[i] == 1])


### FIXED CODE ###

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

t = [0] * (N + 1)
for i in range(N, 0, -1):
    t[i] = (sum(t[2 * i::i]) % 2) ^ a[i - 1]

print(sum(t))
print(*[i for i in range(1, N + 1) if t[i] == 1])
stdin = open("sample.txt")

a = int(stdin.readline().rstrip())

b = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]

print(b[a-1])

### FIXED CODE ###

from sys import stdin
# stdin = open("sample.txt")

a = int(stdin.readline().rstrip())

b = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]

print(b[a-1])
S = input()
N = int(input())
count = 0
S = S.split('ABC')
for i in S:
    if i == '':
        count += 1
    else: continue
print (count)

### FIXED CODE ###

N = int(input())
S = input()
print(S.count("ABC"))
list = []
while True:
    if(int(input()) == 0): break
    else: list.append(input())
    
c = 0
for i in list:
    c = c + 1
    print("Case %d:%d" %(c,i))


### FIXED CODE ###

list = []
while True:
    a = int(input())
    if(a == 0): break
    else: list.append(a)
    

for i in range(len(list)):
    print("Case %d: %d" %(i+1,list[i]))
n = input()
iter_ = iter(list(map(int, input().rstrip("\n").split())))
ans = 0

last = next(iter_)
try:
    while True:
        ans += 1
        now = next(iter_)
        while now == last:
            now = next(iter_)
        laststate = (last < now)
        state = laststate
        print(f"out: {last}, {now}")
        while state == laststate:
            last = now
            now = next(iter_)
            while now == last:
                now = next(iter_)
            state = (last < now)
            print(f"in: {last}, {now}")
        last = now
except StopIteration:
    print(ans)

### FIXED CODE ###

n = input()
iter_ = iter(list(map(int, input().rstrip("\n").split())))
ans = 0

last = next(iter_)
try:
    while True:
        ans += 1
        now = next(iter_)
        while now == last:
            now = next(iter_)
        laststate = (last < now)
        state = laststate
        while state == laststate:
            last = now
            now = next(iter_)
            while now == last:
                now = next(iter_)
            state = (last < now)
        last = now
except StopIteration:
    print(ans)
# coding:utf-8

S = input()
K = int(input())

if K == 1:
    print(S[0])
else:
    S5000 = ''
    for i in range(len(S)):
        s = S[i]
        if s == '1':
            continue
        else:
            digit = i
            tmp = s
            break

if K <= digit:
    print('1')
else:
    print(tmp)

### FIXED CODE ###

# coding:utf-8

S = input()
K = int(input())

for i in range(K):
    if S[i] != '1':
        print(S[i])
        break
else:
    print('1')
N , K = map(int, input().split())
A =list(map(int, input().split()))
mod = 10**9 + 7
count =0
for k in range(len(A)):
    if A[k] == 0:
        count +=1
        A[k] = float("inf")
if N-count < K:
    print(0)
    exit()
A.sort()
A = A[:N-count]
A.sort(reverse=True)
#print(A)
ans = 1
plus = 0
minus = -1
countp = 0
countm = 0
if A[0] >0:
    for k in range(K):
        if abs(A[plus]) >= abs(A[minus]):
            ans = ans*A[plus]%mod
            plus+=1
        else:
            ans = ans*A[minus]%mod
            if A[minus] <0:
                lasm = 0+minus
            minus-=1
            
    if minus%2 == 1:
        print(ans%mod)
    else:
        a = max(A[plus], A[minus])
        print(ans//A[lasm]*a%mod)
else:
    for k in range(K):
        ans = ans*A[k]%mod
    print(ans%mod)

### FIXED CODE ###

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

mod = 10 ** 9 + 7
plus = []
zero = []
minus = []
ans = 1

for k in range(N):
  if A[k] > 0:
    plus.append(A[k])
  elif A[k] < 0:
    minus.append(-1 * A[k])
  else:
    zero.append(A[k])
plus.sort(reverse = True)
minus.sort(reverse = True)
lp = len(plus)
lm = len(minus)

if len(zero) + K > N:
  print(0)
  exit()
elif lp == 0: 
  if K % 2 == 1:
    if len(zero) > 0:
      print(0)
      exit()
    else:
      for k in range(K):
        ans = ans * (-1) * minus[- k - 1] % mod  
      print(ans)
      exit()
  else:
    for k in range(K):
      ans = ans * (-1) * minus[k] % mod
    print(ans)
    exit()
elif lm == 0:
  for k in range(K):
    ans = ans * plus[k] % mod
  print(ans)
  exit()

p = 0
m = 0
for k in range(K):
  if plus[p] >= minus[m]:
    p += 1
    if p == lp:
      m = K - p  
      break
  else:
    m += 1
    if m == lm:
      p = K - m
      break

def main(mp, mm, plus, minus, mod, K):
  ans = 1
  for k in range(mp):
    ans = ans * plus[k] % mod
  for k in range(mm):
    ans = ans * (-1) * minus[k] % mod
  print(ans)
  exit()

if m%2 == 0:
  main(p, m, plus, minus, mod, K)
else:
  if p == lp:
    if m != lm:
      main(p - 1, m + 1, plus, minus, mod, K)
    else:
      if len(zero) > 0:
        print(0)
        exit()
      else:
        main(p, m, plus, minus, mod, K)
  elif m == lm:
    main(p + 1, m - 1, plus, minus, mod, K)
  elif p == 0:
    main(p + 1, m - 1, plus, minus, mod, K)
  else:
    if plus[p] * plus[p - 1] > minus[m - 1] * minus[m]:
      main(p + 1, m - 1, plus, minus, mod, K)
    else:
      main(p - 1, m + 1, plus, minus, mod, K)
d, e = map(int, input().strip().split())
g = list(map(int, input().strip().split()))
print(d, e)
#print(g)
#total = 0
for i in g:
    if i >= e:
        total += 1
print(total)

### FIXED CODE ###

d, e = map(int, input().strip().split())
g = list(map(int, input().strip().split()))
#print(d, e)
#print(g)
total = 0
for i in g:
    if i >= e:
        total += 1
print(total)
import math
tan = int(input())
chou = int(input())
ji = int(input())
hun = int(input())
ans = float(0)
kakudo = abs(((ji*30 + hun*.5) - (hun*6)))

if kakudo > 180:
    kakudo = kakudo-360
kakudo = abs(math.cos(math.radians(kakudo)))
ans =( chou**2 + tan**2 - 2*chou*tan*kakudo)
print((ans)**0.5)

### FIXED CODE ###

import math
chou, tan, ji, hun = map(int,input().split())

kakudo = abs(((ji*30 + hun*.5) - (hun*6)))

if kakudo > 180:
    kakudo = 360 - kakudo

kakudo = abs((math.radians(kakudo)))
ans =( chou**2 + tan**2 - 2*chou*tan*math.cos(kakudo))**.5
print(ans)
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

A = sorted(enumerate(A), key=lambda x: x[1])
B = sorted(enumerate(B), key=lambda x: x[1])

flag = False
for i in range(N):
  if A[i][1] > B[i][1]:
    print('No')
    braek
  elif A[i][0] == B[i][0]:
    flag = True
  elif i > 0 and A[i][1] <= B[i-1][1]:
    flag = True
else:
  if flag:
    print('Yes')
  else:
    print('No')

### FIXED CODE ###

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

A = sorted(enumerate(A), key=lambda x: x[1])
B = sorted(enumerate(B), key=lambda x: x[1])

flag = False
for i in range(N):
  if A[i][1] > B[i][1]:
    print('No')
    break
  elif i > 0 and A[i][1] <= B[i-1][1]:
    flag = True
else:
  if flag:
    print('Yes')
  else:
    D = dict((a[0], b[0]) for a, b in zip(A, B))
    count = 0
    x = D[0]
    while x != 0:
      x = D[x]
      count += 1
    print('Yes' if count < N-1 else 'No')
a = int(input())
s = int(input())
if a > 3199:
  print(s)
else:
  print('red')

### FIXED CODE ###

a = int(input())
s = str(input())
if a > 3199:
    print(s)
else:
    print('red')
s = list(input())
t = ["A", "K", "I", "H", "A", "B", "A", "R", "A"]


if s[-1] != "A":
    s = s + ["A"]
for i in range(len(t)):
    if t[i] != s[i] and t[i] != "A":
        break
    if t[i] != s[i] and t[i] == "A":
        s.insert(i, "A")

if s == t:
    print("YES")
else:
    print("NO")

### FIXED CODE ###

s = list(input())
t = ["A", "K", "I", "H", "A", "B", "A", "R", "A"]


if s[-1] != "A":
    s = s + ["A"]
for i in range(len(t)):
    if len(s) <= i: break
    if t[i] != s[i] and t[i] != "A":
        break
    if t[i] != s[i] and t[i] == "A":
        s.insert(i, "A")

if s == t:
    print("YES")
else:
    print("NO")
AB BC CD = map(int, input().split())

print(int(AB*BC*0.5))

### FIXED CODE ###

AB, BC, CD = map(int, input().split())

print(int(AB*BC*0.5))
N,M = map(int,input().split())
digit = 'zero padding: {:0=6}'
dic = [[] for _ in range(N+1)]

for i in range(M):
    p,y = map(int,input().split())
    dic[p].append((y,i))

for p in dic:
    p.sort()

ans = [None for _ in range(M)]
for k in range(M):
    p = dic[k]
    for j in range(len(p)):
        i = p[j][1]
        ID = str(k).zfill(6)+str(j+1).zfill(6)
        ans[i] = ID

for a in ans:
    print(a)

### FIXED CODE ###

N,M = map(int,input().split())
digit = 'zero padding: {:0=6}'
dic = [[] for _ in range(N+1)]

for i in range(M):
    p,y = map(int,input().split())
    dic[p].append((y,i))

for p in dic:
    p.sort()

ans = [None for _ in range(M)]
for k in range(1,N+1):
    p = dic[k]
    for j in range(len(p)):
        i = p[j][1]
        ID = str(k).zfill(6)+str(j+1).zfill(6)
        ans[i] = ID

for a in ans:
    print(a)
N,M = map(int,input().split())
a = [int(input()) for _ in range(M)]
mod = 10 **9 + 7

import sys
for i in range(M-1):
    flag = a[i+1]-a[i]
    if flag == 1:
        print(0)
        sys.exit()
        
        
dp = [0] * (N+10)
dp[1] = 1
dp[2] = 1
dp[3] = 2
for i in range(3,N+5):
    dp[i+1] = dp[i] + dp[i-1]
    dp[i+1] %= mod
ans = 1
for i in range(M+1):
    if i == 0:
        number = a[i]
    elif i == M:
        number = N - a[i-1]
    else:
        number = a[i]-a[i-1] - 1
    number = max(1,number)
    ans *= dp[number]
    ans %= mod
print(ans)
    

### FIXED CODE ###

N,M = map(int,input().split())
a = [int(input()) for _ in range(M)]
MOD = 10 **9 + 7

import sys
for i in range(M-1):
    flag = a[i+1]-a[i]
    if flag == 1:
        print(0)
        sys.exit()
        
        
dp = [0] * (N+10)
dp[1] = 1
dp[2] = 1
for i in range(1,N+5):
    dp[i+2] = dp[i+1] + dp[i]
    dp[i+2] %= MOD
    
if M == 0:
    print(dp[N+1])
    sys.exit()
ans = 1
for i in range(M+1):
    if i == 0:
        number = a[i]
    elif i == M:
        number = N - a[i-1]
    else:
        number = a[i]-a[i-1] - 1
    number = max(1,number)
    ans *= dp[number]
    ans %= MOD
print(ans)
n = int(input())
s = input()
ans = 0
for i in range(n):
    if s[i] == 'A' and s[i+1] == 'B' and s[i+2] == 'C':
        ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
s = input()

print(s.count('ABC'))
r = input()
s = 3 * a ** 2
print("s")

### FIXED CODE ###

r = int(input())
s = 3 * r * r
print(s)
N, K = map(int, input().split())
S = input()
c = 0
for i in range(1, N):
  if s[i] == s[i - 1]:
    c += 1
print(min(N - 1, c + K * 2))


### FIXED CODE ###

N, K = map(int, input().split())
S = input()
c = 0
for i in range(1, N):
  if S[i] == S[i - 1]:
    c += 1
print(min(N - 1, c + K * 2))
def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0

def modinv(a, m):
    g, x, y = xgcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

import math
N = int(input())
M = 10 ** 9 + 7
A = list(map(int,input().split()))
ans = 0
lcm = A[0]
for i in range(1,N):
    lcm = (lcm * A[i] // int(math.gcd(lcm,A[i] )) ) % M

for i in range(N):
    ans = (ans + modinv(A[i], M) * lcm) % M 
           
print (ans)

### FIXED CODE ###

import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N = NI()
    A = LI()
    d = [0] * (max(A)+1)

    for x in A:
        for i in range(2,int(math.sqrt(x))+1):
            cnt = 0
            while x % i == 0:
                cnt += 1
                x //= i
            d[i] = max(d[i],cnt)
            if x == 1: break
        else:
            d[x] = max(1,d[x])
    m = 1
    for i in range(2,len(d)):
        m = (m * i ** d[i]) % MOD
    ans = 0
    for x in A:
        ans += (m * pow(x,MOD-2,MOD)) % MOD
    print(ans % MOD)


if __name__ == '__main__':
    main()
a,b,c = map(int,input())
if a+b>c:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

a,b,c = map(int,input().split())
if a+b>=c:
  print("Yes")
else:
  print("No")
a,b=map(int,input().split())
c,d==map(int,input().split())
e=int(input())
if abs(a-c)>e*abs(b-d):
  print('YES')
else:
  print('NO')

### FIXED CODE ###

a,b=map(int,input().split())
c,d=map(int,input().split())
e=int(input())
if abs(a-c)<=e*(b-d):
  print('YES')
else:
  print('NO')
import sys
sys.setrecursionlimit(10**5)

n,m=map(int,input().split())
g=[[] for i in range(10**5+10)]
for i in range(m):
  a,b=map(lambda x:int(x)-1, input().split())
  g[a].append(b)
  g[b].append(a)
chk=[-1]*n

def dfs(s,v,cnt):
  for u in g[s]:
    if u==v: continue;
    chk[u]=cnt
    dfs(u,s,cnt)

cnt=0
for i in range(n):
  if chk[i]==-1:
    chk[i]=cnt
    dfs(i,-1,cnt)
    cnt+=1
    
print(max(chk))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**5)

n,m=map(int,input().split())
g=[[] for i in range(10**5+10)]
for i in range(m):
  a,b=map(lambda x:int(x)-1, input().split())
  g[a].append(b)
  g[b].append(a)
chk=[-1]*n

def dfs(s,cnt):
  for u in g[s]:
    if chk[u]>-1: continue;
    chk[u]=cnt
    dfs(u,cnt)

cnt=0
for i in range(n):
  if chk[i]==-1:
    chk[i]=cnt
    dfs(i,cnt)
    cnt+=1
    
print(max(chk))
a,b = map(int,input().split())

for i in range(10000,-1,-1):
  tax1 = int(i*0.08)
  tax2 = int(i*0.1)
  if tax1 = a and tax2 == b:
    print(i)

### FIXED CODE ###

a,b = map(int,input().split())
ans = -1 
  
for i in range(10000,-1,-1):
  tax1 = int(i*0.08)
  tax2 = int(i*0.1)
  if tax1 == a and tax2 == b:
    ans = i
print(ans)
import numpy as np


def solve(*args: str) -> str:
    h, w, k = map(int, args[0].split())
    white = np.array([[n for n in map(int, S)] for S in args[1:]])

    ret = h*w
    for b in range(2**(h-1)):
        h_cuts = set(i+1 for i in range(h-1) if (b >> i) & 1 == 1)
        count = len(h_cuts)
        if ret < count:
            continue

        A = np.array(tuple(x.sum(axis=0) for x in np.vsplit(white, h_cuts)))
        if (k < A).any():
            continue

        S = np.zeros((1, len(A)), dtype=int)
        for x in range(w):
            S += A[:, x]
            if (k < S).any():
                S = A[:, x]
                count += 1
                if ret < count:
                    break

        ret = min(ret, count)

    return str(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))


### FIXED CODE ###

import numpy as np


def solve(*args: str) -> str:
    h, w, k = map(int, args[0].split())
    white = np.array([[n for n in map(int, S)] for S in args[1:]])

    ret = h*w
    for b in range(2**(h-1)):
        h_cuts = list(i+1 for i in range(h-1) if (b >> i) & 1 == 1)
        count = len(h_cuts)
        if ret < count:
            continue

        A = np.array(list(x.sum(axis=0) for x in np.vsplit(white, h_cuts)))
        if (k < A).any():
            continue

        S = np.zeros((1, len(A)), dtype=int)
        for x in range(w):
            S += A[:, x]
            if (k < S).any():
                S = A[:, x]
                count += 1
                if ret < count:
                    break

        ret = min(ret, count)

    return str(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))
N = int(input())
data = []
for _ in range(N):
    x, y, h = list(map(int, input().split()))
    data.append([x,y,h])
for x in range(101):
    flag2 = True
    for y in range(101):
        result = abs(data[0][0] - x) + abs(data[0][1] - y) + data[0][2]
        flag = True
        for dat in data:
            if result != abs(dat[0] - x) + abs(dat[1] - y) + dat[2]:
                flag = False
                break
        if flag == True and result >= 0:
            print(x,y,result)
            Flag2 = False
            break
    if flag2 == False:break

### FIXED CODE ###

x = input()
if int(x) == 1:
    print("Hello World")
else:
    a = int(input())
    b = int(input())
    print(a + b)
N,M= map(int, input().split())
A=list(map(int, input().split()))
A.sort()
A.reverse()
K=sum(A)
answer=0
breakflag=0
for i in range(0,N):
    if  A[i]*M*4>=K:
    	if i==N-1:
        	breakflag=1
      	continue
    else:
      	answer=i
      	break
if breakflag==1:
  answer=N
if answer>=M:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

N,M=map(int, input().split())
A=list(map(int, input().split()))
A.sort()
A.reverse()
K=sum(A)
answer=0
breakflag=0
for i in range(0,N):
  if  A[i]*M*4>=K:
    if i==N-1:
      breakflag=1
    continue
  else:
    answer=i
    break
if breakflag==1:
  answer=N
if answer>=M:
    print("Yes")
else:
    print("No")
T = int(input())

for i in range(T):
    N = int(input())
    A = list(map(int, input().split()))
    S = input().rstrip()

    if S[-1] == '1':
        print('1')

    win = set()
    win.add(0)
    for j in range(len(S)-1, -1, -1):
        tmp = set()
        if S[j] == '0':
            for v in win:
                tmp.add(v ^ A[j])
            win += tmp
        else:
            for v in win:
                if v ^ A[j] not in win:
                    tmp.add(v)
            win -= tmp

    if 0 in win:
        print('0')
    else:
        print('1')


### FIXED CODE ###

T = int(input())

for i in range(T):
    N = int(input())
    A = list(map(int, input().split()))
    S = input().rstrip()

    win = set()
    win.add(0)
    for j in range(len(S)-1, -1, -1):
        base = A[j]
        for v in win:
            base = min(base, base ^ v)

        if S[j] == '0':
            win.add(base)
        else:
            if base:
                print('1')
                break
    else:
        print('0')
input(a)
 print(a + a * 2 + a * 3 = Z)

### FIXED CODE ###

a = int(input())
print(a + a**2 + a**3)
import numpy as np

ipt =np.array(input()[3:])

np.pad(ipt,1,'#')

### FIXED CODE ###

h, w = [int(n) for n in input().split()]

ans=''
for i in range(h):
    ans+='#'+input()+'#'+'\n'
print('#'*(w + 2))
print(ans+'#'*(w + 2))
a=list(map(input(). split() ) )
if(a[0]==a[5]&&a[1] ==a[4] & & a[2] ==a[3] ):
       print ("Yes" )
else:
print("No" ) 

### FIXED CODE ###

x = input()
y = input()
z = x[::-1]
if y==z:
        print("YES")
else:
        print("NO")
# This program computes GCD and LCM
# -*- coding: utf-8
import sys


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


def lcm(a, b):
    for i in range(max([a, b]), a*b + 1):
        if(i % a == 0 and i % b == 0):
            return i
    return a*b


for i in sys.stdin:
    try:
        line = [int(k) for k in i.split(" ")]
        g = gcd(max(line), min(line))
        print(str(g) + " " + str(line[0]*line[1]/g))  # + str(lcm(line[0], line[1]))
    except:
        raise
        exit()

### FIXED CODE ###

# This program computes GCD and LCM
# -*- coding: utf-8
import sys


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


for i in sys.stdin:
    try:
        line = [int(k) for k in i.split(" ")]
        g = gcd(min(line), max(line))
        print(str(g) + " " + str(line[0]*line[1]//g))
    except:
        exit()
from fractions import gcd
N, M = map(int, input().split())
S = input()
T = input()
gcd_ = gcd(len(S), len(T))
saisho = len(S) * len(T) // gcd_
s_ = saisho//len(S)
t_ = saisho//len(T)

X = ["0"] * (saisho*2)
for i in range(len(S)):
    #print(i, i * s_)
    X[i * s_] = S[i]
ans = True
for i in range(len(T)):
    if X[i * t_] != "0" and T[i] != X[i * t_]:
        ans = False
    else:
        X[i * t_] = T[i]
if ans:
    print(saisho)
else:
    print("-1")
"""
ans = True
if gcd_ != 1:
    for i in range(gcd_):
        # print(i)
        if S[s_ * i] != T[t_ * i]:
            ans = False
            # break
if ans:
    print(saisho)
else:
    print(-1)
"""


### FIXED CODE ###

#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N,M=MI()
    S=ST()
    T=ST()
    lcm = N*M//(gcd(N,M))
    ans = defaultdict(str)
    for i,s in enumerate(S):
        ans[i*lcm//N] = s
    for i,t in enumerate(T):
        if(ans[i*lcm//M] not in (t,"")):
            print(-1)
            return 
    print(lcm)
if __name__ == '__main__':
    main()
import math
N = int(input())
A = list(map(int, input().split()))
x = A[0]
for i in range(len(A)-1):
    x= math.gcd(x,A[i+1])
print(x)

### FIXED CODE ###

import fractions
N = int(input())
A = list(map(int, input().split()))
x = A[0]
for i in range(len(A)-1):
    x= fractions.gcd(x,A[i+1])
print(x)
"""
NTC here
"""
import sys
input= sys.stdin.readline
# import t  hreading
# setrecursionlimit(10**6)
# threading.stack_size(2**26)

def iin(): return int(input())
def lin(): return list(map(int, input().split()))

# range = xrange
# input = raw_input

def main():
    n, k= lin()
    h=lin()
    ans=[0]*(n)
    for i in range(n-2,-1,-1):
        ans[i]=min(
            [abs(h[i]-h[j+i+1])+ans[i+j+1] for j in range(min(n-i-1,k))]
            )
    print(ans[0])
        



                









        
main()
#threading.Thread(target=main).start()


### FIXED CODE ###

"""
NTC here
"""
import sys
input= sys.stdin.readline
# import t  hreading
# setrecursionlimit(10**6)
# threading.stack_size(2**26)

def iin(): return int(input())
def lin(): return list(map(int, input().split()))

# range = xrange
# input = raw_input

def main():
    n = iin()
    Q = [lin() for i in range(n)]
    ans = [[0, 0, 0] for i in range(n+1)] 
   # print(ans)
    for i in range(n-1, -1, -1):
        for j in range(3):
            ans[i][j]=Q[i][j]+max([
                ans[i+1][k] for k in range(3) if k!=j
            ])
  #  print(ans)
    print(max(ans[0]))

        



                









        
main()
#threading.Thread(target=main).start()
a=input()
b=input()
c=input()
d=input()
e=input()
k=input()
c[0]=b-a
c[1]=c-b
c[2]=d-c
c[3]=e-d
if((c[0]>k) or (c[1]>k) or (c[2]>k)or (c[3]>k)):
  print(':(')
else if(((c[0]+c[1])>k)or ((c[1]+c[2])>k)or ((c[2]+c[3])>k)):
  print(':(')
else if(((c[0]+c[1]+c[2])>k) or((c[1]+c[2]+c[3])>k)):
  print(':(')
else if((e-a)>k):
  print(':(')
else:
  print('Yay!')

### FIXED CODE ###

a=int(input())
b=int(input())
c=int(input())
d=int(input())
e=int(input())
k=int(input())
f=[b-a,c-b,d-c,e-d]
 
if((f[0]>k) or (f[1]>k) or (f[2]>k)or (f[3]>k)):
  print(':(')
elif(((f[0]+f[1])>k)or ((f[1]+f[2])>k)or ((f[2]+f[3])>k)):
  print(':(')
elif(((f[0]+f[1]+f[2])>k) or((f[1]+f[2]+f[3])>k)):
  print(':(')
elif((e-a)>k):
  print(':(')
else:
  print('Yay!')