Harryxun/stf_run huggingface dataset:
import sys,bisect as bs,collections as cl,heapq as hq
sys.setrecursionlimit(100000)
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

n = onem()
a = []
for i in range(n):
    a.append(onem())
a.sort()
bbb = a[n//2+(n%2):]
bbb.reverse()

bbbb = a[n//2:]

bbbb = [bbbb[0]] + bbbb[2:] + [bbbb[1]]

aaa = a[:n//2+(n%2)]
aaa = [aaa[-1]] + aaa[:-2] + [aaa[-2]]

aaaa = a[:n//2]

lll = []
llll = []

for i in range(n):
    if i % 2 == 0:
        lll.append(aaa[i//2])
        llll.append(bbbb[i//2])
    else:
        lll.append(bbb[i//2])
        llll.append(aaaa[i//2])
ans = 0
an = 0
for i in range(n):
    if i == 0:
        st = lll[0]
        stt = llll[0]
    else:
        ans += abs(lll[i] - st)
        st = lll[i]
        an += abs(llll[i] - stt)
        stt = llll[i]
print(max(ans,an))







### FIXED CODE ###

import sys,bisect as bs,collections as cl,heapq as hq
sys.setrecursionlimit(100000)
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

n = onem()
a = []
for i in range(n):
    a.append(onem())
a.sort()
bbb = a[n//2+(n%2):]
bbb.reverse()

bbbb = a[n//2:]

if len(bbb) >= 3:
    bbbb = [bbbb[0]] + bbbb[2:] + [bbbb[1]]


aaa = a[:n//2+(n%2)]
if len(aaa) >= 3:
    aaa = [aaa[-1]] + aaa[:-2] + [aaa[-2]]

aaaa = a[:n//2]

lll = []
llll = []

for i in range(n):
    if i % 2 == 0:
        lll.append(aaa[i//2])
        llll.append(bbbb[i//2])
    else:
        lll.append(bbb[i//2])
        llll.append(aaaa[i//2])
ans = 0
an = 0
for i in range(n):
    if i == 0:
        st = lll[0]
        stt = llll[0]
    else:
        ans += abs(lll[i] - st)
        st = lll[i]
        an += abs(llll[i] - stt)
        stt = llll[i]
print(max(ans,an))
n = int(input())
def gcd(a,b):
    if b==0:
        return a
    return gcd(b,a%b)
        
def lcm(a,b):
    return a/gcd(a,b)*b
    
ans=1

for i in range(n):
    t = int(input())
    ans = lcm(ans,t)
    
print(int(ans))

### FIXED CODE ###

n = int(raw_input())

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

def lcm(a,b):
    g = gcd(a,b)
    return a/g * b

x = 1
for i in range(n):
    ti = int(raw_input())
    x = lcm(x, ti)

print x
a, b, c = map(int, input().split())
if a == b and b == c:
  return True
return False

### FIXED CODE ###

a, b, c = map(int, input().split())
if a == b and b == c:
	print('Yes')
else:
	print('No')
weather_list = ["sunny", "cloudy", "rainy"]
a = input("")
print( wether_list[ weather_list.index(a) + 1 ] )

### FIXED CODE ###

weather_list = ["Sunny", "Cloudy", "Rainy"]
a = input("")
print( weather_list[ ( weather_list.index(a) + 1 ) % 3  ] )
print"vowel"*(c in"aiueo")or"consonant"

### FIXED CODE ###

print("vowel"*(input()in"aiueo")or"consonant")
S = input()
T = input()
if S == T[:-1]:
    return 'Yes'
else:
    return 'No'

### FIXED CODE ###

S = input()
T = input()
if S == T[:-1]:
    print('Yes')
else:
    print('No')
n = int(raw_input)
a = map(int, raw_input().split())
a.reverse()
for i in a:
    print i,

### FIXED CODE ###

n = int(raw_input())
a = map(int, raw_input().split())
a.reverse()
print (" ".join(map(str, a)))
s=[0]*25
s[11]=1
d=[0]*13
d[0]+=1
n=int(input())
a=list(map(int,input().split()))
d=[a.count(i)for i in range(12)]
if max(d[0],d[12])<2 and max(d[1:12])<3:
    if d[12]==1:
        s[0]=1
        s[-1]=1
    t=[]
    for i in range(1,12):
        if d[i]==2:
            s[12-i]=1
            s[12+i]=1
        elif d[i]==1:
            t.append(i)
    k=0
    for i in range(s**len(t)):
        p=bin(i)[2:]
        p="0"*(len(t)-len(p))+p
        r=s[:]
        for j in range(len(t)):
            if p[j]=="0":
                r[12-t[j]]=1
            else:
                r[12+t[j]]=1
        r=2*r
        h=0
        q=0
        ans=0
        for j in r:
            if j==1:
                if h==0:
                    q=1
                    h=1
                else:
                    ans=min(q,ans)
                    q=1
            else:
                q+=1
        k=max(ans,k)
    print(k)
else:
    print(0)

### FIXED CODE ###

s=[0]*24
s[12]=1
n=int(input())
a=list(map(int,input().split()))
d=[a.count(i)for i in range(13)]
d[0]+=1
if max(d[0],d[12])<2 and max(d[1:-1])<3:
    if d[12]==1:
        s[0]=1
    t=[]
    for i in range(1,12):
        if d[i]==2:
            s[12-i]=1
            s[12+i]=1
        elif d[i]==1:
            t.append(i)
    k=0
    for i in range(2**len(t)):
        p=bin(i)[2:]
        p="0"*(len(t)-len(p))+p
        r=s[:]
        for j in range(len(t)):
            if p[j]=="0":
                r[12-t[j]]=1
            else:
                r[12+t[j]]=1
        h=0
        q=0
        ans=30
        for j in 2*r:
            if j==1:
                if h==0:
                    q=1
                    h=1
                else:
                    ans=min(q,ans)
                    q=1
            else:
                q+=1
        k=max(ans,k)
    print(k)
else:
    print(0)
import sys
input = sys.stdin.readline

l=["A",'B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z',"A",'B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z']
n=int(input())
s=input()
ans=""
for i in range(len(s)):
    ans+=l[l.index(s[i])+n]
print(ans)

### FIXED CODE ###

l=["A",'B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z',"A",'B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z']
n=int(input())
s=input()
ans=""
for i in range(len(s)):
    ans+=l[l.index(s[i])+n]
print(ans)
n, m = map(int, input().split())

a = [0] * m

for i in range(m):
    a[i] = int(input())

div = 10 ** 9 + 7
f = [0] * n

f[0] = 1
f[1] = 2

for i in range(2, n):
    f[i] = (f[i - 1] + f[i - 2]) % div
    if i + 1 in a:
        f[i] = 0

print(f[n - 1])


### FIXED CODE ###

def main():
    N, M, *a = map(int, open(0).read().split())
    div = 1000000007
    broken = set(a)
 
    comb_list = [0] * (N + 1)
    comb_list[0] = 1
    if 1 not in broken:
        comb_list[1] = 1
 
    for i in range(2, N + 1):
        if i in broken:
            continue
        comb_list[i] = (comb_list[i - 1] + comb_list[i - 2]) % div
 
    print(comb_list[-1])
 
 
if __name__ == "__main__":
    main()
import os
import sys
from collections import defaultdict

import numpy as np
from functools import lru_cache

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18

N, M = list(map(int, sys.stdin.readline().split()))
UV = [list(map(int, sys.stdin.readline().split())) for _ in range(M)]
S, T = list(map(int, sys.stdin.readline().split()))

graph = np.zeros((N + 1, N + 1), dtype=bool)
for u, v in UV:
    graph[u][v] = True


@lru_cache(maxsize=None)
def dest(v, count):
    if count <= 1:
        return graph[v]
    ret = np.zeros((N + 1), dtype=bool)
    for u in np.where(graph[v])[0]:
        ret |= dest(u, count - 1)
    return ret


checked = np.zeros(N + 1, dtype=bool)
vs = np.zeros(N + 1, dtype=bool)
vs[S] = True
i = 0
prev = 0
while True:
    i += 1
    s = np.zeros(N + 1, dtype=bool)
    for v in np.where(vs)[0]:
        s |= dest(v, 3)
    checked |= vs
    if s[T]:
        print(i)
        break
    if checked.sum() == prev:
        print(-1)
        break
    vs = s ^ checked
    prev = checked.sum()


### FIXED CODE ###

import bisect
import heapq
import itertools
import math
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18

N, M = list(map(int, sys.stdin.readline().split()))
UV = [list(map(int, sys.stdin.readline().split())) for _ in range(M)]
S, T = list(map(int, sys.stdin.readline().split()))

graph = [[] for _ in range(N + 1)]
for u, v in UV:
    graph[u].append(v)

que = deque()
que.append((S, 0))
reached = np.zeros((N + 1, 3), dtype=bool)
reached[S, 0] = True

while que:
    u, step = que.popleft()
    for v in graph[u]:
        s = step + 1
        if not reached[v, s % 3]:
            reached[v, s % 3] = True
            que.append((v, s))
        if v == T and s % 3 == 0:
            print(s // 3)
            exit()
print(-1)
S = input()
S_list = list(S)
answers = []
acgt = 0
for s in S_list:
    if s == 'A' or s == 'C' or s == 'G' or s == 'T':
        acgt += 1
    else:
        answers.append(acgt)
        acgt = 0
print(max(answers))


### FIXED CODE ###

S = input()
S_list = list(S)
answers = []
acgt = 0
for s in S_list:
    if s == 'A' or s == 'C' or s == 'G' or s == 'T':
        acgt += 1
    else:
        answers.append(acgt)
        acgt = 0
answers.append(acgt)
if answers:
    print(max(answers))
else:
    print(acgt)
N, L = map(int, input().split())
Li = [input() for i in range(N)]

s = ""
for i in range(N):
  temp = min(Li)
  Li.remove(temp)
  s += temp
print(s)

### FIXED CODE ###

a, b, c = map(str, input().split())
s = a+b+c

if s.count("5") == 2 and s.count("7") == 1:
  print("YES")
else:
  print("NO")
import math
N,M=map(int,input().split())
n=math.fabs(N-2)
m=math.fabs(M-2)
ans=int(n*m)
print(ans)


### FIXED CODE ###

A=input()
B=input()
C=input()
a=A[:1]
b=B[1:2]
c=C[2:3]
print(a+b+c)
H, W = list(map(int, input().split()))
    M = [[-1]*(W+2)]
    ans = 0
    for _ in range(H):
        s = input()
        ans += s.count('.')
        M.append([-1]+[0 if c=='.' else -1 for c in s]+[-1])
    M += [[-1]*(W+2)]
     
    queue = [(1,1)]
    M[1][1] = 1
    dr = [(+1,0),(-1,0),(0,+1),(0,-1)]
    turn = 1
    while len(queue)>0:
        turn += 1
        queue_new = []
        for qx, qy in queue:
            for dx, dy in dr:
                x, y = qx+dx, qy+dy
                if M[y][x]==0:
                    M[y][x] = turn
                    queue_new.append((x,y))
        queue = queue_new
     
    print(ans-M[H][W] if M[H][W]>0 else -1)

### FIXED CODE ###

H, W = list(map(int, input().split()))
M = [[-1]*(W+2)]
ans = 0
for _ in range(H):
    s = input()
    ans += s.count('.')
    M.append([-1]+[0 if c=='.' else -1 for c in s]+[-1])
M += [[-1]*(W+2)]

queue = [(1,1)]
M[1][1] = 1
dr = [(+1,0),(-1,0),(0,+1),(0,-1)]
turn = 1
while len(queue)>0:
    turn += 1
    queue_new = []
    for qx, qy in queue:
        for dx, dy in dr:
            x, y = qx+dx, qy+dy
            if M[y][x]==0:
                M[y][x] = turn
                queue_new.append((x,y))
    queue = queue_new

print(ans-M[H][W] if M[H][W]>0 else -1)
S = input()
for i in range(len(S)):
  if S[i] == '9':
    S[i] = '1'
  elif S[i] == '1':
    S[i] = '9'
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)
a,b,c = map(int,input().split())
print(min[a+b,a+c,b+c])

### FIXED CODE ###

number = list(map(int,input().split()))

max = max(number)

number.remove(max)

print(number[0] + number[1])
n,m=map(int,input().split())
MOD = 10**9+7
ans=1
def inv_mod(a, p=MOD):
    def inv_mod_sub(a, p):
        if a == 1:
            return 1, 0
        else:
            d, r = p//a, p%a
            x, y = inv_mod_sub(r, a)
            return y-d*x, x
    if p < 0: p = -p
    a %= p
    return inv_mod_sub(a,p)[0] % p

def comb_mod(n, k):
    if k < 0 or k > n:
        return 0
    else:
        return f_mod[n]*f_mod_inverse[k]*f_mod_inverse[n-k] % MOD
f_mod=[1]*(m+1)
f_mod_inverse=[1]*(m+1)
for i in range(1,m+1):
  f_mod[i]=f_mod[i-1]*i%MOD
  f_mod_inverse[i]=f_mod_inverse[i-1]*inv_mod(i) % MOD  
pf={}
for i in range(2,int(m**0.5)+1):
    while m%i==0:
        pf[i]=pf.get(i,0)+1
        m//=i
if m>1:pf[m]=1
for i in pf.values():
  ans*=comb_mod(i+n-1,n-1)
print(ans%MOD,f_mod)


### FIXED CODE ###

import sys
n,m=map(int,input().split())
MOD = 10**9+7
ans=1
if m==1:
  print(1)
  sys.exit()
def inv_mod(a, p=MOD):
    def inv_mod_sub(a, p):
        if a == 1:
            return 1, 0
        else:
            d, r = p//a, p%a
            x, y = inv_mod_sub(r, a)
            return y-d*x, x
    if p < 0: p = -p
    a %= p
    return inv_mod_sub(a,p)[0] % p

def comb_mod(n, k):
    if k < 0 or k > n:
        return 0
    else:
        return f_mod[n]*f_mod_inverse[k]*f_mod_inverse[n-k] % MOD
pf={}
for i in range(2,int(m**0.5)+1):
    while m%i==0:
        pf[i]=pf.get(i,0)+1
        m//=i
if m>1:pf[m]=1
Max=max(list(pf.values()))
f_mod=[1]*(Max+n+1)
f_mod_inverse=[1]*(Max+n+1)
for i in range(1,Max+n+1):
  f_mod[i]=(f_mod[i-1]*i)%MOD
  f_mod_inverse[i]=(f_mod_inverse[i-1]*inv_mod(i)) % MOD  
for i in pf.values():
  ans*=comb_mod(i+n-1,n-1)
print(ans%MOD)
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

S = input()
print("Yes" if length(set(A))==3 else "No") 

### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

S = input()
print("Yes" if len(set(S))==3 else "No")
A, B, K = map(int, input().split())

yakusuu=[]
for i in range(1,A):
  if A% i == 0:
    yakusuu.append(i)
  
for j in range(1,B):
  if B%j == 0:
    yakusuu.append(j)
    
print(sorted(yakusuu)[K])

### FIXED CODE ###

A, B, K = map(int, input().split())

yakusuu=[]
yakusuuA = []
yakusuuB = []
for i in range(1,A+1):
  if A% i == 0:
    yakusuuA.append(i)
  
for j in range(1,B+1):
  if B%j == 0:
    yakusuuB.append(j)
    
yakusuu = list(set(yakusuuA) & set(yakusuuB))
yakusuu.append(1)     
print(sorted(yakusuu, reverse=True)[K-1])
mod = 10**9+7

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

if (X + Y) % 3 != 0:
    ans = 0
else:
    n = (X + Y) // 3
    r = X - n
    # nCr
    fact = [1, 1]
    for i in range(2, n+1):
        fact.append(fact[-1] * i % mod)
    ans = fact[n]*pow(fact[r], mod-2, mod)*pow(fact[n-r], mod-2, mod) % mod

print(ans)


### FIXED CODE ###

mod = 10**9+7
N = 10**6
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

for i in range(2, N + 1):
    g1.append((g1[-1] * i) % mod)
    inverse.append((-inverse[mod % i] * (mod//i)) % mod)
    g2.append((g2[-1] * inverse[-1]) % mod)


def cmb(n, r, mod):
    if (r < 0 or r > n):
        return 0
    return g1[n] * g2[r] * g2[n-r] % mod


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

if (X + Y) % 3 != 0:
    ans = 0
else:
    n = (X + Y) // 3
    r = min(X, Y) - n
    ans = cmb(n, r, mod)
print(ans)
N = int(input())

if N % 2 = 0:
    print([N])
else:
    print([N + 1])

### FIXED CODE ###

N = int(input())

if N % 2 == 0:
    print(N // 2)
else:
    print(N // 2 + 1)
print "Yes" if '7' in raw_input() else "No"

### FIXED CODE ###

print "Yes" if '7' in raw_input() else "No"
def main():
    i = 1
    while True:
        x = int(raw_input().strip())
        if x == 0:
            break
        print "Case %d: %d" % (i, x)
        i += 1

if __name__ == '__main__':
main()

### FIXED CODE ###

count = 1

while True:
    x = int(input())
    if x != 0:
        print("Case {0}: {1}".format(count, x))
        count += 1

    else:
        break
n , m = map(int,input().split())
s = input()
t = input()
l = n*m//fractions.gcd(n,m)
p = l//n
q = l//m

for i in range(10**9):
    if q*i >= n or p*i >= m:
        print(l)
        exit()
    if s[q*i] != t[p*i]:
        print(-1)
        exit()

### FIXED CODE ###

import fractions
n , m = map(int,input().split())
s = input()
t = input()
l = n*m//fractions.gcd(n,m)
p = l//n
q = l//m

for i in range(10**9):
    if q*i >= n or p*i >= m:
        print(l)
        exit()
    if s[q*i] != t[p*i]:
        print(-1)
        exit()
1 N, K = input().split()
  2 S = input()
  3 K = int(K)
  4 li = list(S)
  5 li[K-1] = chr(ord(S[K-1])+32)
  6 print(''.join(li))

### FIXED CODE ###

N, K = input().split()
S = input()
K = int(K)
li = list(S)
li[K-1] = chr(ord(S[K-1])+32)
print(''.join(li))
n = int(input())
x = list(input())

def popcount(nn):
    bin_n = bin(nn)[2:]
    count = 0
    for i in bin_n:
        count += int(i)
    return count

cnt = popcount(int(''.join(x), base=2))

dic = {}
for i in range(n):
    temp = x[:]
    if temp[i] == '0':
        temp[i] = '1'
        cnt_temp = cnt + 1
    else:
        temp[i] = '0'
        cnt_temp = cnt - 1
    temp = ''.join(temp)
    num = int(temp, base=2)
    num = num % cnt_temp
    lst = [num]
    ans = 1
    while num != 0:
        if num in dic:
            ans += dic[num]
            for i in range(len(lst)):
                dic[lst.pop()] = dic[num] + i
            break
        ans += 1
        popcnt = popcount(num)
        num %= popcnt
        lst.append(num)
    for i in range(len(lst)):
        dic[lst.pop()] = i
    print(ans)

### FIXED CODE ###

n = int(input())
x = list(input())

def popcount(n):
    bin_n = bin(n)[2:]
    count = 0
    for i in bin_n:
        count += int(i)
    return count

cnt = 0
for i in range(n):
    if x[i] == '1':
        cnt += 1

lst = [0 for i in range(n+1)]
for i in range(1, n+1):
    num = i%popcount(i)
    lst[i] = lst[num] + 1

plus = [0 for i in range(n)]
minus = [0 for i in range(n)]
plus[0] = 1
if cnt != 1:
    minus[0] = 1
for i in range(1, n):
    plus[i] = (plus[i-1]*2) % (cnt+1)
    if cnt != 1:
        minus[i] = (minus[i-1]*2) % (cnt-1)

origin = int(''.join(x), base=2)
amariplus = origin % (cnt+1)
if cnt != 1:
    amariminus = origin % (cnt-1)

for i in range(n):
    if x[i] == '0':
        amari = (amariplus + plus[n-i-1]) % (cnt+1)
        print(lst[amari] + 1)
    else:
        if cnt != 1:
            amari = (amariminus - minus[n-i-1]) % (cnt-1)
            print(lst[amari] + 1)
        else:
            print(0)
def gcd(a, b):
    if a < b:
        a, b = b, a
    while a % b != 0:
        a, b = b, a % b
    return b

def lmc(a, b):
    return a * b // gcd(a, b)

n, m = map(int, input().split())
s = str(input())
t = str(input())
l = lmc(n, m)
L = [0] * l
for i in range(n):
    L[i*(l//n)] = s[i]
for j in range(m):
    if L[j*(l//m)] == 0:
        L[j*(l//m)] = t[j]
    elif L[j*(l//m)] == t[j]:
        pass
    else:
        print(-1)
        break
else:
    print(l)


### FIXED CODE ###

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

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

n, m = map(int, input().split())
s = str(input())
t = str(input())
g = gcd(n, m)
l = lcm(n, m)
for i in range(g):
    if s[i*n//g] != t[i*m//g]:
        print(-1)
        break
else:
    print(l)
n, w = map(int, input().split())
s = [list(map(int, input().split())) for i in range(n)]
ws = [x[0] for x in s]
v = [x[1] for x in s]

dp = [[0]*(w+1) for _ in range(n+1)]
for i in range(n):
    for sum_w in range(w+1):
        if sum_w + ws[i] <= w:
            dp[i+1][sum_w + ws[i]] = max(dp[i+1][sum_w + ws[i]],
                                         dp[i][sum_w]+v[i])
        dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w])
print(dp[-1][-1])


### FIXED CODE ###

from pprint import pprint
n, w = map(int, input().split())
s = [list(map(int, input().split())) for i in range(n)]
ws = [x[0] for x in s]
vs = [x[1] for x in s]
max_v = sum(vs)
INF = float("inf")
dp = [[INF]*(max_v+1) for _ in range(n+1)]
dp[0][0] = 0
for i in range(1, n+1):
    for sum_v in range(max_v+1):
        if vs[i-1] <= sum_v:
            dp[i][sum_v] = min(dp[i-1][sum_v], dp[i-1][sum_v-vs[i-1]]+ws[i-1])
        else:
            dp[i][sum_v] = dp[i-1][sum_v]
ans = 0
for sum_v in range(max_v+1):
    if dp[n][sum_v] <= w:
        ans = sum_v
print(ans)
k,n=map(int,input().split())
a=map(int,input().split())
max = -1
for i in range(0,n-1):
  if max>abs(a[i]-a[i+1]):
    max=abs(a[i]-a[i+1])
if max>(k-a[n-1])+a[0]:
  max=(k-a[n-1])+a[0]
  
print(k-max)

### FIXED CODE ###

k,n=map(int,input().split())
a=list(map(int,input().split()))
max = -1
for i in range(0,n-1):
  d=abs(a[i+1]-a[i])
  if max<d:
    max=d
if max<k-a[n-1]+a[0]:
  max=k-a[n-1]+a[0]
  
print(k-max)
a,b = map(int,raw_input().split())
if a < b:
      print("a < b")
elif a > b:
      print("a > b")
else:
      print("a == b")

### FIXED CODE ###

a,b = map(int,input().split())
if a < b:
      print("a < b")
elif a > b:
      print("a > b")
else:
      print("a == b")
N, M = map(int, input().split())
L, R = 1, N

import math

def merge_list(target):
    L = target[-1][0]
    print(target)
    R = sorted(target, key=lambda x: x[1])[0][1]
    return (L, R)

data = []
for i in range(0, M):
    l, r = input().split()
    data.append((int(l), int(r)))
data = sorted(data, key=lambda x: x[0])

import numpy as np
def saiki(totyuu):
    D = 2 # ぶんかつすう
    if len(totyuu[0]) < 10:
        return merge_list(map(merge_list, totyuu))
    else:
        return saiki(np.array_split(totyuu, D))

data = saiki(data)

print(max(0, data[1]-data[0]+1))

### FIXED CODE ###

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

Ls = []
Rs = []
for i in range(0, M):
    l, r = input().split()
    Ls.append(int(l))
    Rs.append(int(r))

maxL = max(Ls)
minR = min(Rs)
result = max(0, minR-maxL+1)

print(result)
strings = raw_input.split(',')
new_strings = ""
for string in strings:
  if string.islower():
    new_strings.append(string.upper()+',')
  else:
    new_strings.append(string.lower())
print  new_strings

### FIXED CODE ###

print raw_input().swapcase()