Harryxun/stf_run huggingface dataset:
#!/usr/bin/env python3
import sys


def count_linear_process(lis):
    length = len(lis)
    return [l // length for l in lis]


def linear_process(lis):
    length = len(lis)
    return [l % length for l in lis]


def check_end(lis):
    return max(lis) < len(lis)


def add_processed(lis, counts):
    sum_cnt = sum(counts)
    return [l + sum_cnt - cnt for l, cnt in zip(lis, counts)]


def update(lis, n_process=0):
    if check_end(lis):
        return n_process
    next_lis = linear_process(lis)
    counts = count_linear_process(lis)
    return update(
        add_processed(next_lis, counts), 
        n_process + sum(counts)
    )


def solve(N: int, a: "List[int]"):
    print(update(a))
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, a)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys

sys.setrecursionlimit(2000000)


def count_linear_process(lis):
    length = len(lis)
    return [l // length for l in lis]


def linear_process(lis):
    length = len(lis)
    return [l % length for l in lis]


def check_end(lis):
    return max(lis) < len(lis)


def add_processed(lis, counts):
    sum_cnt = sum(counts)
    return [l + sum_cnt - cnt for l, cnt in zip(lis, counts)]


def update(lis, n_process=0):
    if check_end(lis):
        return n_process
    next_lis = linear_process(lis)
    counts = count_linear_process(lis)
    return update(
        add_processed(next_lis, counts), 
        n_process + sum(counts)
    )


def solve(N: int, a: "List[int]"):
    print(update(a))
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, a)

if __name__ == '__main__':
    main()
S = input()
S = int(S)
for i in range(len(S)):
  if S[i] == 9:
    S[i] = 1
  elif S[i] == 1:
    S[i] = 9
S = str(S)
print(S)

### FIXED CODE ###

S = input()
c = ''
if S[0] == '1':
  c += '9'
elif S[0] == '9':
  c += '1'
else:
  c += S[0]
if S[1] == '1':
  c += '9'
elif S[1] == '9':
  c += '1'
else:
  c += S[1]
if S[2] == '1':
  c += '9'
elif S[2] == '9':
  c += '1'
else:
  c += S[2]
print(c)
import numpy as np

N = int(input())
s = []
for i in range(N):
  s.append(input())
    
M = int(input())
t = []
for i in range(M):
  t.append(input())
    
s = np.unique(s, return_counts=True)
t = np.unique(t, return_counts=True)

ans = 0
#for i,ch_s in enumerate(s[0]):
#  ans_tmp = s[1][i]
#  for j,ch_t in enumerate(t[0]):
#    if ch_s == ch_t:
#      ans_tmp -= t[1][j]
#  if ans_tmp > ans:
#    ans = ans_tmp
print(int(ans))

### FIXED CODE ###

import numpy as np

N = int(input())
s = []
for i in range(N):
  s.append(input())
    
M = int(input())
t = []
for i in range(M):
  t.append(input())

s = np.array(s)
t = np.array(t)
s_uni = np.unique(s)

ans = 0
for i,ch_s in enumerate(s_uni):
  ans_tmp = (s==ch_s).sum()
  ans_tmp -= (t==ch_s).sum()
  if ans_tmp > ans:
    ans = ans_tmp
print(int(ans))
n = int(input())
a = list(map(int,input().split()))
a.sort()
b = [0]*8
over = 0

for i in a:
    if i < 400:
        b[0] += 1
    elif i < 800:
        b[1] += 1
    elif i < 1200:
        b[2] += 1
    elif i < 1600:
        b[3] += 1
    elif i < 2000:
        b[4] += 1
    elif i < 2400:
        b[5] += 1
    elif i < 2800:
        b[6] += 1
    elif i < 3200:
        b[7] += 1
    else:
        over += 1

#bの中で、０ではない要素数をカウントする
low = 0
for i in b:
    if i >= 0:
        low += 1

if low == 0:
    mini = 1
else:
    mn = low
mx = c + over
print(mini,mx)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
a.sort()
b = [0 for i in range(9)]
red = 0
for i in a:
	if i < 400:
		b[0] += 1
	elif i < 800:
		b[1] += 1
	elif i < 1200:
		b[2] += 1
	elif i < 1600:
		b[3] += 1
	elif i < 2000:
		b[4] += 1
	elif i < 2400:
		b[5] += 1
	elif i < 2800:
		b[6] += 1
	elif i < 3200:
		b[7] += 1
	else:
		red += 1
c = 0
for i in b:
	if i > 0:
		c += 1
if c == 0:
	mn = 1
else:
	mn = c
mx = c + red
print (mn, mx)
import math

A, B, C, D = map(int, input().split())

def lcm(x, y):
    return (x * y) // math.gcd(x, y)

LCM=lcm(C,D)

Cwari=(B//C)-((A-1)//C)
Dwari=(B//D)-((A-1)//D)
CDwari=(B//LCM)-(A//LCM)

print((B-A+1)-(Cwari+Dwari-CDwari))



### FIXED CODE ###

from fractions import gcd

A, B, C, D = map(int, input().split())
l = C * D // gcd(C, D)
x = (A - 1) - (A - 1) // C - (A - 1) // D + (A - 1) // l
y = B - B // C - B // D + B // l
print(y - x)
a,b,c = map(int, input().split())
cnt = 0
for i in range(a,b)
 if c%i != 0 :
 else : cnt += 1

print(cnt)
  

### FIXED CODE ###

a,b,c = map(int, input().split())
cnt = 0
for i in range(a,b+1):
 if c%i == 0 : cnt += 1
print(cnt)
S=input()
N=len(S)
ans='Yes'
if N=3:
    if S[0]!=S[2]:
        ans='No'
else:
    if int((N-1)/2)%2==1:
        for i in range((N-3)//4):
            if S[i] != S[(N-3)//2-i] or S[(N+1)//2+i] != S[N-i-1]:
                ans='No'
    else:
        for i in range((N-1)//4):
            if S[i]!=S[(N-3)//2-i] or S[(N-1//2)+i]!=S[N-i-1]:
                ans='No'

print(ans)

### FIXED CODE ###

S=input()
N=len(S)
ans='Yes'

for i in range((N-1)//2):
    if S[i] != S[N-i-1]:
        ans='No'

if int((N-1)/2)%2==1:
    for i in range((N-3)//4):
        if S[i] != S[((N-3)//2)-i] or S[((N+1)//2)+i] != S[N-i-1]:
            ans='No'
else:
    for i in range((N-1)//4):
        if S[i] != S[((N-3)//2)-i] or S[((N+1)//2)+i] != S[N-i-1]:
            ans='No'
 
print(ans)
N = int(input())
x = list(input())[::-1]
print(x)
num = 0
nump = 0
numm = 0
pop_num = 0
for i in range(N):
        if x[i] == "1":
            pop_num += 1
for i in range(N):
    if x[i] == "1":
        num += pow(2,i,pop_num)
        num %= pop_num 
        nump += pow(2,i,pop_num+1)
        nump %= pop_num  + 1
        numm += pow(2,i,pop_num - 1)
        if pop_num != 0:
            numm %= pop_num - 1



def popcnt(n):
    c = (n & 0x5555555555555555) + ((n>>1) & 0x5555555555555555)
    c = (c & 0x3333333333333333) + ((c>>2) & 0x3333333333333333)
    c = (c & 0x0f0f0f0f0f0f0f0f) + ((c>>4) & 0x0f0f0f0f0f0f0f0f)
    c = (c & 0x00ff00ff00ff00ff) + ((c>>8) & 0x00ff00ff00ff00ff)
    c = (c & 0x0000ffff0000ffff) + ((c>>16) & 0x0000ffff0000ffff)
    c = (c & 0x00000000ffffffff) + ((c>>32) & 0x00000000ffffffff)
    return c

x = x[::-1]
def calc(i,depth,n):
    if depth == 0:
        if x[i] == "1":
            tmp = numm
            tmp -= pow(2,N-i-1,pop_num-1)
            tmp %= (pop_num - 1)
            return calc(i,depth+1,tmp)
        else:
            tmp = nump
            tmp += pow(2,N-i-1,pop_num+1)
            tmp %= (pop_num + 1)
            return calc(i,depth+1,tmp)
    else:
        if n == 0: return depth
        return calc(i,depth+1, n % popcnt(n))
        

for i in range(N):
    exit()
    print(calc(i,0,0))



### FIXED CODE ###

N = int(input())
x = list(input())[::-1]
num = 0
nump = 0
numm = 0
pop_num = 0
for i in range(N):
        if x[i] == "1":
            pop_num += 1
for i in range(N):
    if x[i] == "1":
        num += pow(2,i,pop_num)
        num %= pop_num 
        nump += pow(2,i,pop_num+1)
        nump %= pop_num  + 1
        if pop_num-1 != 0:
            numm += pow(2,i,pop_num - 1)
            numm %= pop_num - 1



def popcnt(n):
    c = (n & 0x5555555555555555) + ((n>>1) & 0x5555555555555555)
    c = (c & 0x3333333333333333) + ((c>>2) & 0x3333333333333333)
    c = (c & 0x0f0f0f0f0f0f0f0f) + ((c>>4) & 0x0f0f0f0f0f0f0f0f)
    c = (c & 0x00ff00ff00ff00ff) + ((c>>8) & 0x00ff00ff00ff00ff)
    c = (c & 0x0000ffff0000ffff) + ((c>>16) & 0x0000ffff0000ffff)
    c = (c & 0x00000000ffffffff) + ((c>>32) & 0x00000000ffffffff)
    return c

x = x[::-1]
def calc(i,depth,n):
    if depth == 0:
        if x[i] == "1":
            tmp = numm
            if pop_num - 1 != 0:
                tmp -= pow(2,N-i-1,pop_num-1)
                tmp %= (pop_num - 1)
            else:
                return 0
            return calc(i,depth+1,tmp)
        else:
            tmp = nump
            tmp += pow(2,N-i-1,pop_num+1)
            tmp %= (pop_num + 1)
            return calc(i,depth+1,tmp)
    else:
        if n == 0: return depth
        return calc(i,depth+1, n % popcnt(n))
        

for i in range(N):
    print(calc(i,0,0))
while True:
    a,b = list(map(int, input().split()))
    if a == b == 0:
        break
    for i in range(1,a+1):
        if i % 2 != 0:
            if b % 2 == 0:
                print('#.' * (b / 2))
            else:
                print('#.' * ((b -1) /2) + '#')
        else:
            if b % 2 == 0:
                print('.#' * (b / 2))
            else:
                print('.#' * ((b -1) /2) + '.')
    print()

### FIXED CODE ###

while True:
    a = list(map(int, input().split()))
    b = a[0]
    c = a[1]
    if b == c == 0:
        break
    for i in range(1, b+1):
        if i % 2 != 0:
            if c % 2 == 0:
                print('#.' * (c // 2))
            else:
                print('#.' * (c // 2) + '#')
        else:
            if c % 2 == 0:
                print('.#' * (c // 2))
            else:
                print('.#' * (c // 2) + '.')
    print()
#include<stdio.h>

int main(void){
    int a,b;
    scanf("%d",&a);
    scanf("%d",&b);
    if(a==b){
        printf("EQUAL\n");
    }else{
        if (a>b){
            printf("GREATER\n");
        }
        else{
            printf("LESS\n");
        }
    }
}


### FIXED CODE ###

# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

a = int(input())
b = int(input())
if a == b:
    print("EQUAL")
elif a < b:
    print("LESS")
else:
    print("GREATER")
A = int(input())
B = int(input())
if a < 9 and b < 9:
  print('Yay!')
else:
  print(':(')

### FIXED CODE ###

A, B = map(int, input().split())
if A < 9 and B < 9:
    print('Yay!')
else:
    print(':(')
#from functools import lru_cache
import sys
from itertools import product,combinations,accumulate
from functools import reduce,lru_cache
import heapq

def vfunc(f): return lambda *lst, **kwargs: list(map(lambda *x:f(*x,**kwargs),*lst))

def rvfunc(f): return lambda *lst, **kwargs: list(map(lambda *x:rvfunc(f)(*x,**kwargs) if all(vfunc(lambda y:isinstance(y,list))(x)) else f(*x,**kwargs),*lst))

def reader():return vfunc(lambda l:l.split())(sys.stdin.readlines())

s = rvfunc(int)(reader())
n,k=s[0]
p=s[1]
c=s[2]

def pnt(i):
    out = []
    current=i
    for j in range(n):
        current=p[current-1]
        out.append(c[current-1])
    return out
def loc(i):
    out = []
    current=i
    for j in range(n):
        current=p[current-1]
        out.append(current)
    return out
    
def acc(i):    
    p,l=pnt(i),loc(i)
    sp = sum(p)
    print(p,sp)
    init = l.index(i)
    pini = p[init:]+p[:init]
    last = p[(init+int((k-1)%n))%n]
    plst = p[:last]
    if k+1<n:
        return max(list(accumulate(pini[:k-1])))
    else:
        if sp<0:
            return max(list(accumulate(p)))
        else:
            return max(list(accumulate(p)))+sum(p[:last])+sp*int((k-1)/n)

print(max(vfunc(acc)(range(1,n+1))))


### FIXED CODE ###

import sys
from itertools import product,combinations
from functools import reduce,lru_cache
import heapq

def vfunc(f): return lambda *lst, **kwargs: list(map(lambda *x:f(*x,**kwargs),*lst))

def rvfunc(f): return lambda *lst, **kwargs: list(map(lambda *x:rvfunc(f)(*x,**kwargs) if all(vfunc(lambda y:isinstance(y,list))(x)) else f(*x,**kwargs),*lst))

def reader():return vfunc(lambda l:l.split())(sys.stdin.readlines())

s=reader()

print(max(vfunc(len)(s[0][0].split('S'))))
import sys
import math
import numpy as np

def main():
    dish = np.array(sys.stdin.read().split())

    minute = [int(dish[i][-1]) for i in range(5) ]
    m = min(x for x in minute if x > 0)

    res = (np.ceil(dish.astype(np.int64) / 10) * 10).sum() - 10 + m

    print(int(res))

if __name__ == "__main__":
    main()


### FIXED CODE ###

# 2019-11-12 22:40:44(JST)
import sys
# import collections
# import math
# from string import ascii_lowercase, ascii_uppercase, digits
# from bisect import bisect_left as bi_l, bisect_right as bi_r
# import itertools
# from functools import reduce
# import operator as op
# from scipy.misc import comb # float
# import numpy as np 

def main():
    dishes = [int(x) for x in sys.stdin.read().split()]
    

    total = 0
    for i in range(5):
        if dishes[i] % 10 != 0:
            total += (dishes[i] // 10 + 1) * 10
        else:
            total += dishes[i]
    

    remainder = [dishes[i] % 10 for i in range(5) if dishes[i] % 10 != 0]
    if remainder:
        ans = total - (10 - min(remainder))
    else:
        ans = total
    print(ans)

if __name__ == "__main__":
    main()
# -*- coding: utf-8 -*-
 
# スペース区切りの整数の入力
a = input()
b = 0
for i in range(3):
	if a[i] =='1':
    	b += 1
print(b)

### FIXED CODE ###

# -*- coding: utf-8 -*-
 
a = input()
b = 0
for i in range(3): 
    if a[i] =='1':
        b += 1
print(str(b))
N,K=map(int, input().split())
A=list(map(int, input().split()))
D,E=[],[]
zcnt,scnt,fcnt=0,0,0
for i in A:
  if i==0:
    zcnt+=1
    D.append(0)
  elif i>0:
    D.append(i)
    scnt+=1
  else:
    E.append(i)
    fcnt+=1
mod=10**9+7
ans=1
if K==N:
  for i in A:
    ans*=i
    ans%=mod
  print(ans)
  exit()
if K%2==1 and max(A)<0:
  A=sorted(A)[::-1]
  for i in range(K):
    ans*=A[i]
    ans%=mod
  print(ans)
  exit()
if K>scnt+fcnt:
  print(0)
  exit()
D,E=sorted(D)[::-1],sorted(E)
#print(D,E)
ans=1
a,b=0,0
for i in range(K//2):
  if len(D)>=2 and len(E)>=2:
    d,e=D[a]*D[a+1],E[b]*E[b+1]
    if d>e:
      ans*=d
      a+=2
      ans%=mod
    else:
      ans*=e
      b+=2    
      ans%=mod
  elif len(D)>=2 and len(E)<2:
    d=D[a]*D[a+1]
    ans*=d
    a+=2
    ans%=mod
  elif len(D)<2 and len(E)>=2:
    e=E[b]*E[b+1]
    ans*=e
    b+=2
    ans%=mod

if K%2==1:
  Z=[]
  if a!=scnt:
    Z.append(D[a])
  if b!=fcnt:
    Z.append(E[-1])
  if 0 in A:
    Z.append(0)
  ans*=max(Z)
  ans%=mod
print(ans)

### FIXED CODE ###

N,K=map(int, input().split())
A=list(map(int, input().split()))
D,E=[],[]
zcnt,scnt,fcnt=0,0,0
for i in A:
  if i==0:
    zcnt+=1
    D.append(0)
  elif i>0:
    D.append(i)
    scnt+=1
  else:
    E.append(i)
    fcnt+=1
mod=10**9+7
ans=1
#全て使う場合は問答無用でかける
if K==N:
  for i in A:
    ans*=i
    ans%=mod
  print(ans)
  exit()
#マイナスを奇数個絶対かける→確実に答えはマイナス
if K%2==1 and max(A)<0:
  A=sorted(A)[::-1]
  for i in range(K):
    ans*=A[i]
    ans%=mod
  print(ans)
  exit()
#絶対0をかけなきゃいけない
if K>scnt+fcnt:
  print(0)
  exit()
D,E=sorted(D)[::-1],sorted(E)
#print(D,E)
ans=1
cnt=0
a,b=0,0
while K-cnt>1:
  if a+1<=len(D)-1 and b+1<=len(E)-1:
    d,e=D[a]*D[a+1],E[b]*E[b+1]
    if d>e:
      ans*=D[a]
      a+=1
      cnt+=1
      ans%=mod
    else:
      ans*=e
      b+=2    
      ans%=mod
      cnt+=2
  elif a+1<=len(D)-1:
    d=D[a]*D[a+1]
    ans*=D[a]
    a+=1
    cnt+=1
    ans%=mod
  elif b+1<=len(E)-1:
    e=E[b]*E[b+1]
    ans*=e
    b+=2
    cnt+=2
    ans%=mod

if K-cnt==1:
  Z=[]
  if a!=scnt:
    Z.append(D[a])
  if b!=fcnt:
    Z.append(E[-1])
  if 0 in A:
    Z.append(0)
  ans*=max(Z)
  ans%=mod
print(ans)
# summer vacations, number of assignments
N, M = list(map(int, input().split()))
# each entry in A represents number of days to do the assignment
A = list(map(int, input().split()))

number_of_days_required = sum(A)
maximum_hangout_days = N - number_of_days_required
if maximum_hangout_days >= 0:
    print(maximum_hangout_days)
else:
    print(-1)

### FIXED CODE ###

import math
r = int(input())
print(2 * r * math.pi)
X, N = map(int, input().split())

try:
  p = set(map(int, input().split()))
  num = set(range(1,101))
  mem = []
  result = -1

  ref = sorted(list(num - p))

  for item in ref:
    mem.append(abs(X - item))

  print(ref[mem.index(min(mem))])

except EOFError:
  print(X)
  


### FIXED CODE ###

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

try:
  p = set(map(int, input().split()))
  num = set(range(-100,201))
  mem = []

  ref = sorted(list(num - p))

  for item in ref:
    mem.append(abs(item - X))
  
  print(ref[mem.index(min(mem))])

except EOFError:
  print(X)
N = int(input())
a = list(map(int,input().split()))
q = int(input())
num = []
summ = 0
for i in range(10**5):
  num.append(0)
for i in range(N):
  num[a[i]-1] += 1
  summ += 1
for i in range(q):
  b,c = map(int,input().split())
  summ += (c-b)*a[b-1]
  a[c-1] += a[b-1]
  a[b-1] = 0
  print(summ)


### FIXED CODE ###

N = int(input())
a = list(map(int,input().split()))
q = int(input())
num = []
summ = 0
for i in range(10**5):
  num.append(0)
for i in range(N):
  num[a[i]-1] += 1
  summ += a[i]
for i in range(q):
  b,c = map(int,input().split())
  summ += (c-b)*num[b-1]
  num[c-1] += num[b-1]
  num[b-1] = 0
  print(summ)
A = []
for _ in range(N):
    t, a = map(int, input().split())
    T.append(t)
    A.append(a)
curT = T[0]
curA = A[0]
for i in range(1, N):
    if curT > curA:
        if curT % T[i] != 0:
            curT += T[i] - curT % T[i]
        curA = curT // T[i] * A[i]
    else:
        if curA % A[i] != 0:
            curA += A[i] - curA % A[i]
        curT = curA // A[i] * T[i]
print(curT+curA)

### FIXED CODE ###

def ceil(a, b):
    return (a + b - 1) // b

N = int(input())
T = []
A = []
for _ in range(N):
    t, a = map(int, input().split())
    T.append(t)
    A.append(a)
curT = T[0]
curA = A[0]
for i in range(1, N):
    m1 = ceil(curT, T[i])
    m2 = ceil(curA, A[i])
    m = max(m1, m2)
    curT = m * T[i]
    curA = m * A[i]
print(curT+curA)
N = int(input())
h = [int(i) for i in input().split()]
DP = [0]
DP.append(abs(h[0] - h[1]))

for i in range(2,len(h)):
    if DP[i-1] + abs(h[i-1] - h[i]) > DP[i-2] + abs(h[i-2] - h[i]):
        DP.append(DP[i-2] + abs(h[i-2] - h[i]))
    else:
        DP.append(DP[i-1] + abs(h[i-1] - h[i]))

print(DP[len(N)-1])


### FIXED CODE ###

N = int(input())
h = [int(i) for i in input().split()]
DP = [0]
DP.append(abs(h[0] - h[1]))

for i in range(2,len(h)):
    if DP[i-1] + abs(h[i-1] - h[i]) > DP[i-2] + abs(h[i-2] - h[i]):
        DP.append(DP[i-2] + abs(h[i-2] - h[i]))
    else:
        DP.append(DP[i-1] + abs(h[i-1] - h[i]))

print(DP[N-1])
import numpy as np
import sys

mod = 10 ** 9 + 7

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

if N == K:
    ans = 1
    for i in range(N):
        ans *= A[i]
        ans %= mod
    print(ans)
    sys.exit()

A = np.array(A)

plus = A[A>0]
minus = A[A<0]
zero = A[A==0]

if len(zero) > N - K:
    print(0)
    sys.exit()

if len(minus) == N:
    if K % 2 == 0:
        minus = np.sort(minus)
    else:
        minus = np.sort(minus)[::-1]
    ans = 1
    for i in range(K):
        ans *= minus[i]
        ans %= mod
    print(ans)
    sys.exit()

plus = np.sort(plus)[::-1]
minus *= -1
minus = np.sort(minus)[::-1]

if K % 2 == 1:
    ans = plus[0]
    K -= 1
    p = (len(plus)-1) // 2
    m = len(minus) // 2
    
    n_p = [plus[2*i+1] * plus[2*i+2] for i in range(p)]
    n_m = [minus[2*i] * minus[2*i+1] for i in range(m)]
else:
    ans = 1
    p = len(plus) // 2
    m = len(minus) // 2
    
    n_p = [plus[2*i] * plus[2*i+1] for i in range(p)]
    n_m = [minus[2*i] * minus[2*i+1] for i in range(m)]

K //= 2

p_index = 0
m_index = 0
for i in range(K):
    if p_index == len(n_p):
        ans *= n_m[m_index]
        ans %= mod
        m_index += 1
    elif m_index == len(n_m):
        ans *= n_p[p_index]
        ans %= mod
        p_index += 1
    else:
        if n_p[p_index] > n_m[m_index]:
            ans *= n_p[p_index]
            ans %= mod
            p_index += 1
        else:
            ans *= n_m[m_index]
            ans %= mod
            m_index += 1
print(ans)

### FIXED CODE ###

import sys

mod = 10 ** 9 + 7

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

A.sort(reverse = True)

if A[0] < 0 and K % 2 == 1:
    ans = 1
    for i in range(K):
        ans *= A[i]
        ans %= mod
    print(ans)
    sys.exit()

l = 0
r = N-1

ans = 1
if K % 2 == 1:
    ans *= A[0]
    l += 1

for _ in range(K // 2):
    if A[l] * A[l+1] > A[r] * A[r-1]:
        ans *= A[l] * A[l+1]
        ans %= mod
        l += 2
    else:
        ans *= A[r] * A[r-1]
        ans %= mod
        r -= 2

print(ans)
s = input().sort()
print("Yes") if s == "abc" else print("No")

### FIXED CODE ###

s = input()
L = [s[0], s[1], s[2]]
L.sort()
S = "".join(L)
print("Yes") if S == "abc" else print("No")
N = int(input())
a = [[] for i in range(N)]
edge = {}
for i in range(N-1):
  A, B, C = map(int, input().split())
  a[A-1].append([B-1, C])
  a[B-1].append([A-1, C])
dist = [-1]*N
Q, K = map(int, input().split())
dist[K-1] = 0

def  dfs(now):
  for i, dis_e in a[now]:
    if dist[i] == -1:
      dist[i] = dist[now] + dis_e
      dfs(i)

def main():
  dfs(K-1)
  ans = []
  for i in range(Q):
    x, y = map(int, input().split())
    ans.append(dist[x-1]+dist[y-1])
  print(*ans, sep = "\n")

if __name__ == "__main__":
  main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**8)
N = int(input())
a = [[] for i in range(N)]
for i in range(N-1):
  A, B, C = map(int, input().split())
  a[A-1].append([B-1, C])
  a[B-1].append([A-1, C])
dist = [-1]*N
Q, K = map(int, input().split())
dist[K-1] = 0

def dfs(now):
  for i, dis_e in a[now]:
    if dist[i] == -1:
      dist[i] = dist[now] + dis_e
      dfs(i)

def main():
  dfs(K-1)
  ans = []
  for i in range(Q):
    x, y = map(int, input().split())
    print(dist[x-1]+dist[y-1])
  #print(*ans, sep = "\n")

if __name__ == "__main__":
  main()
from collections import Counter
s=input()
t=input()
c1=Counter(s)
c2=Counter(t)
c1.sort()
c2.sort()
print('Yes' if c1==c2 else 'No')

### FIXED CODE ###

from collections import Counter
s=input()
t=input()
cntS=list(Counter(s).values())
cntT=list(Counter(t).values())
cntS.sort()
cntT.sort()
print('Yes' if cntS==cntT else 'No')
L=lambda:list(map(int,input().split()))
n=int(input())
a=L()
b=0
for i in a:b+=1/a
print(1/b)

### FIXED CODE ###

L=lambda:list(map(int,input().split()))
n=int(input())
a=L()
b=0
for i in a:b+=1/i
print(1/b)
S = input()
if s[2] == s[3] and s[4] == s[5]:
    print(Yes)
else:
    print(No)

### FIXED CODE ###

S = input()
if S[2] == S[3] and S[4] == S[5]:
    print("Yes")
else:
    print("No")
N, M = map(int, input().split())
S = str(input())
T = str(input())

def lcm(x, y):
    def gcd(a, b):
        while b:
            a, b = b, a % b
        return a
    return (x * y) // gcd(x, y)
X = lcm(N ,M)

if S[0] != T[0]:
    print(-1)
elif X == N*M:
    print(N*M)
else:
    for i in range(1,(N*M//X)+1):
        L = X * i
        counter = L
        y = L // N
        z = L // M
        match = lcm( y, z)
        for j in range(1, (L // match) ):
            if S[j * N * match // L] != T[l = j * M * match // L]:
                counter = -1
                break
        if counter == L:
            break
    print(counter)




### FIXED CODE ###

N, M = map(int, input().split())
S = str(input())
T = str(input())
def gcd(a, b):
	while b:
		a, b = b, a % b
	return a
 
def lcm(x, y):
    return (x * y) // gcd(x, y)
X = lcm(N ,M)
 
if S[0] != T[0]:
    print(-1)
elif X == N*M:
    print(N*M)
else:
        L = X
        match = lcm(  L // N,  L // M)
        for j in range(1, (L // match) ):
            if S[j * N * match // L] != T[ j * M * match // L]:
                L = -1
                break
        if L == X :
            print(L)
        else:
            print(-1)