Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

import itertools
#(縦, 横)
#bfs 徒歩→ワープ→徒歩→ワープ→…

h,w = map(int,input().split())
sy, sx = map(int,input().split())
start = (sy-1, sx-1)
gy, gx = (map(int,input().split()))
goal = (gy-1, gx-1)

chizu = [input() for _ in range(h)]
kabeset = set()

for i in range(h):
	for j in range(w):
		if chizu[i][j] == "#":
			kabeset.add((i, j))

settansaku = set()
stock = set()
setmada = {start}
kouho = 1
mode = 1
cost = 0

while kouho > 0:
	while kouho > 0:
		for i, j in list(setmada):
			settansaku.add((i, j))
			stock.add((i, j))
			setmada.remove((i, j))
			kouho -= 1
			for k in [(i+1, j), (i-1, j), (i, j-1), (i, j+1)]:
				if 0 <= k[0]:
					if 0 <= k[1]:
						if k[0] < h:
							if k[1] < w:
								if not k in kabeset:
									if not k in setmada:
										if not k in settansaku:
											setmada.add(k)
											kouho += 1
											if k == goal:
												mode = 0
								
	if mode == 0:
		break
	
	cost += 1
	newkouho = len(stock)
	while newkouho > 0:
		for i, j in list(stock):
			stock.remove((i, j))
			newkouho -= 1
			for k in itertools.product(range(i-2, i+3), range(j-2, j+3)):
				if 0 <= k[0]:
					if 0 <= k[1]:
						if k[0] < h:
							if k[1] < w:
								if not k in kabeset:
									if not k in settansaku:
										setmada.add(k)
										kouho += 1
										if k == goal:
											mode = 0
								
	if mode == 0:
		break
	
	kouho = len(setmada)

if mode == 0:
	print(cost)
else:
	print(-1)

### FIXED CODE ###

h,w = map(int,input().split())
sy, sx = map(int,input().split())
start = (sy-1, sx-1)
gy, gx = (map(int,input().split()))
goal = (gy-1, gx-1)

yukaset = set()

for i in range(h):
	chizu = input()
	for j in range(w):
		if chizu[j] == ".":
			yukaset.add((i, j))

settansaku = {start}
stock = []
listmada = [start]
mode = 1
cost = 0

while len(listmada) > 0:
	for i, j in listmada:
		stock.append((i, j))
		for k in [(i+1, j), (i-1, j), (i, j-1), (i, j+1)]:
			if k in yukaset:
				if k not in settansaku:
					listmada.append(k)
					settansaku.add(k)

	if goal in settansaku:
		mode = 0
		break
	
	listmada = []
	cost += 1
	for i, j in stock:
		for k in [(i-2, j-2), (i-1, j-2), (i, j-2), (i+1, j-2), (i+2, j-2), (i-2, j-1), (i-1, j-1), (i, j-1), (i+1, j-1), (i+2, j-1), (i-2, j), (i-1, j), (i+1, j), (i+2, j), (i-2, j+1), (i-1, j+1), (i, j+1), (i+1, j+1), (i+2, j+1), (i-2, j+2), (i-1, j+2), (i, j+2), (i+1, j+2), (i+2, j+2)]:
			if k in yukaset:
				if k not in settansaku:
					listmada.append(k)
					settansaku.add(k)
	
	stock = []

if mode == 0:
	print(cost)
else:
	print(-1)
### BUGGY CODE ###

N, W = list(map(int, input().split()))
wvList = [list(map(int, input().split())) for _ in range(N)]

ans = 0
dp = [[0] * (W + 1) for _ in range(2)]
for i, wv in enumerate(wvList):
    for j in range(1, W + 1):
        numi = 0
        if i % 2 == 0:
            numi = 1
        if j - wv[0] >= 0:
            dp[numi][j] = max(dp[numi-1][j-wv[0]] + wv[1], dp[numi-1][j])
        else:
            dp[numi][j] = dp[numi-1][j]
        ans = max(dp[numi][j], ans)

print(ans)

### FIXED CODE ###

import sys

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

ans = 0
DP = [0] * (W + 1)
for i in range(N):
    dp = []
    w, v = map(int, sys.stdin.readline().split())
    for j, element in enumerate(DP):
        if j >= w:
            dp.append(DP[j - w] + v if element < DP[j - w] + v else element)
        else:
            dp.append(element)
    DP = dp

print(max(DP))
### BUGGY CODE ###

'''
包除原理
すべての条件を満たしている
2^{N-1}から「どれかの条件を満たしていない」を引けば良い
i番目の条件を満たしていない確率はかんたんに計算できる
Sに属していいないやつが全て条件を満たしていない確率については
Sに対応する辺が全て白となる確率を考えれば良い
'''
from collections import deque
N=int(input())
G=[[] for i in range(N)]
for i in range(N-1):
    a,b=map(int,input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
M=int(input())
u=[0 for i in range(M)]
v=[0 for i in range(M)]
for i in range(M):
    u[i],v[i]=map(int,input().split())
    u[i]-=1;v[i]-=1
root=[set() for i in range(M)]
for i in range(M):
    q=deque([u[i]])
    parents=[-1 for i in range(N)]
    reached=[0 for i in range(N)]
    while(len(q)>0):
        r=q.popleft()
        reached[r]=1
        for p in G[r]:
            if reached[p]==1:
                continue
            parents[p]=r
            q.append(p)
    x=v[i]
    while(1):
        if parents[x]==-1:
            break
        s=min(x,parents[x])
        t=max(x,parents[x])
        root[i].add((s,t))
        x=parents[x]
#print(root)
ans=0
def cnt(x):
    ans=0
    for i in range(M):
        if x|(2**i)==x:
            ans+=1
    return ans
L=sorted(list(range(2**M)),key=lambda x:cnt(x))
S=[set() for i in range(2**M)]
for i in L:
    for j in range(M):
        if i&(2**j)==0:
            S[i|(2**j)]=S[i]|{k for k in root[j]}
    ans+=(-1)**(cnt(i))*2**(N-len(S[i])-1)
print(ans)



### FIXED CODE ###

'''
包除原理
すべての条件を満たしている
2^{N-1}から「どれかの条件を満たしていない」を引けば良い
i番目の条件を満たしていない確率はかんたんに計算できる
Sに属していいないやつが全て条件を満たしていない確率については
Sに対応する辺が全て白となる確率を考えれば良い
'''
from collections import deque
N=int(input())
G=[[] for i in range(N)]
a=[0 for i in range(N-1)]
b=[0 for i in range(N-1)]
edges=dict()
for i in range(N-1):
    a[i],b[i]=map(int,input().split())
    a[i]-=1;b[i]-=1
    G[a[i]].append(b[i])
    G[b[i]].append(a[i])
    edges[(min(a[i],b[i]),max(a[i],b[i]))]=i
M=int(input())
u=[0 for i in range(M)]
v=[0 for i in range(M)]
for i in range(M):
    u[i],v[i]=map(int,input().split())
    u[i]-=1;v[i]-=1
root=[0 for i in range(M)]
for i in range(M):
    q=deque([u[i]])
    parents=[-1 for i in range(N)]
    reached=[0 for i in range(N)]
    while(len(q)>0):
        r=q.popleft()
        reached[r]=1
        for p in G[r]:
            if reached[p]==1:
                continue
            parents[p]=r
            q.append(p)
    x=v[i]
    while(1):
        if parents[x]==-1:
            break
        s=min(x,parents[x])
        t=max(x,parents[x])
        root[i]+=2**edges[(s,t)]
        x=parents[x]
ans=0
def cnt(x):
    ans=0
    for i in range(M):
        if x|(2**i)==x:
            ans+=1
    return ans
q=deque([])
q.append(0)
S=[0 for i in range(2**M)]
reached=[0 for i in range(2**M)]
while(len(q)>0):
    i=q.popleft()
    for j in range(M):
        if i&(2**j)==0:
            S[i|(2**j)]=S[i]|root[j]
            if reached[i|(2**j)]==0:
                q.append(i|(2**j))
                reached[i|(2**j)]=1
    ans+=(-1)**(cnt(i))*2**(N-bin(S[i]).count("1")-1)
print(ans)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, m = map(int, input().split())

    if m % n == 0:
        print(m // n)
    else:
        ma = m // n
        res = 0
        for g in range(1, ma + 1):
            t = m - g * (n - 1)
            if t % g == 0:
                GCD = g
                res = max(res, GCD)
        print(res)


if __name__ == '__main__':
    resolve()


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def make_divisors(n):
    divisors = []
    for i in range(1, int(pow(n, 0.5)) + 1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n // i)
    divisors.sort()
    return divisors


def resolve():
    n, m = map(int, input().split())

    ma = m // n
    div = make_divisors(m)
    res = 1
    for d in div:
        if d <= ma:
            res = d
        else:
            break

    print(res)


if __name__ == '__main__':
    resolve()
### BUGGY CODE ###

N, M = [int(x) for x in input().split()]
lst = [[int(x) for x in reversed(input().split())] for i in range(M)]
lst.sort()
bridge = [True] * N

def connected(a, b):
    for i in range(a, b):
        if bridge[i] == False:
            return False
    return True

def solve():
    res = 0
    for l in lst:
        a, b = l
        if connected(b, a):
            bridge[a - 1] = False
            res += 1
    return res

if __name__ == '__main__':
    print(solve())


### FIXED CODE ###

bridge = set()
def connected(a, b):
    for i in bridge:
        if a <= i and i < b:
            return False
    return True
def solve():
    N, M = [int(x) for x in input().split()]
    lst = [[int(x) for x in reversed(input().split())] for i in range(M)]
    lst.sort()
    res = 0
    for l in lst:
        a, b = l
        if connected(b, a):
            bridge.add(a - 1)
    return len(bridge)

if __name__ == '__main__':
    print(solve())
### BUGGY CODE ###


from collections import defaultdict
from bisect import bisect
n, k = list(map(int, input().split()))
al = [0] * n
for i in range(n):
    al[i] = int(input())

d = defaultdict(lambda: 0)
d[al[0]] = 1
for a in al[1:]:
    m = 0
    for i in range(max(0, a-k), a+k+1):
        m = max(m, d[i])
    d[a] = m+1
print(max(d.values()))


### FIXED CODE ###


from collections import defaultdict
from bisect import bisect

n, k = list(map(int, input().split()))
al = [0] * n
for i in range(n):
    al[i] = int(input())
max_al = max(al)
min_al = min(al)

# N: 処理する区間の長さ
N = max(al)+1
N0 = 2**(N-1).bit_length()
INF = 2**31-1
data = [INF]*(2*N0)
# a_k の値を x に更新


def update(k, x):
    k += N0-1
    data[k] = x
    while k >= 0:
        k = (k - 1) // 2
        data[k] = min(data[2*k+1], data[2*k+2])
# 区間[l, r)の最小値


def query(l, r):
    L = l + N0
    R = r + N0
    s = INF
    while L < R:
        if R & 1:
            R -= 1
            s = min(s, data[R-1])

        if L & 1:
            s = min(s, data[L-1])
            L += 1
        L >>= 1
        R >>= 1
    return s


for i in range(n):
    update(al[i], n)

for a in al:
    v = query(max(min_al, a-k), min(a+k, max_al)+1)
    update(a, n-((n-v)+1))
v = query(min_al, max_al+1)
print(n-v)
### BUGGY CODE ###

n,k=map(int,input().split())
a=[int(i) for i in input().split()]
d=[0 for i in range(n)]
c=1
k=min(k,40)

while c<=k:
    b=list(d)
    for i in range(n):
        l=max(0,i-a[i])
        r=min(n-1,i+a[i])
        b[l]+=1
        if r+1<n:
            b[r+1]-=1
    for i in range(1,n):
        b[i]+=b[i-1]
    c+=1
    a=b

print(" ".join(map(str,a)))

### FIXED CODE ###

n,k=map(int,input().split())
a=[int(i) for i in input().split()]
k=min(k,41)

for j in range(k):
    b=[0 for i in range(n)]
    for i in range(n):
        l=max(0,i-a[i])
        r=min(n-1,i+a[i])
        b[l]+=1
        if r+1<n:
            b[r+1]-=1
    for i in range(1,n):
      b[i]+=b[i-1]
    a=b
print(" ".join(map(str,a)))
### BUGGY CODE ###

#!/usr/bin/env python3
import sys, os

def main():
    inp = [int(x) for x in os.read(0, os.fstat(0).st_size).split()]
    n, m = inp[0],inp[1]

    wi, vi = inp[2], inp[3]


    dp = [0] * (m + 1)
    for j in range(wi, m + 1):
        dp[j] = vi

    for i in range(n - 1):
        wi = inp[2*i + 4]
        vi = inp[2*i + 5]
        j = m
        while j >= wi:
            if dp[j] < vi + dp[j - wi]:
                dp[j] = vi + dp[j - wi]
            j -= 1

    print(dp[-1])
main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys, os
range = xrange

def main():
    inp = [int(x) for x in os.read(0, os.fstat(0).st_size).split()]
    n, m = inp[0],inp[1]

    w, v = inp[2::2], inp[3::2]

    dp = [0] * (m + 1)
    for j in range(w[0], m + 1):
        dp[j] = v[0]

    for i in range(n - 1):
        vi = v[i + 1]
        wi = w[i + 1]
        for j in reversed(range(wi, m + 1)):
            dp[j] = max(vi + dp[j - wi], dp[j])

    print(dp[-1])
main()
### BUGGY CODE ###

#K-th Substring

#入力
s = input()
k = int(input())
 
 #計算
subs = set()
for i in range(len(s)):
  for j in range(i+1, len(s)+1):
    subs.add(s[i:j])

subs = list(subs) 
subs.sort()

#出力
print(subs[k-1])


### FIXED CODE ###

#K-th Substring

#入力
s = input()
k = int(input())
 
 #計算
sub = set()

for i in range(len(s)):
	for j in range(i+1, min(i+6,len(s)+1)):
		sub.add(s[i:j])

sub = list(sub) 
sub.sort()

#出力
print(sub[k-1])
### BUGGY CODE ###

def main(N,A):
    B=[0]
    count = 0
    for i in range(N):
        T = A[i] + B[i]
        for m in range(len(B)):
            if T - B[m] == 0:
                # print(i, m)
                # print(B[i],B[i-m])
                # print(T)
                # print("kore",B[i],B[i-m])
                count += 1
        B.append(T)

    #print(count)
    #print(B)
    return print(count)

if __name__ == "__main__":
    N=int(input())
    A=list(map(int,input().split()))

    main(N,A)

### FIXED CODE ###

import collections

def main(N,A):
    B=[0]
    count = 0
    for i in range(N):
        T = A[i] + B[i]

        B.append(T)
    c = collections.Counter(B)

    for i in range(len(c)):
        k, v = c.popitem()
        for z in range(v):
            count += z

    return print(count)

if __name__ == "__main__":
    N=int(input())
    A=list(map(int,input().split()))

    main(N,A)
### BUGGY CODE ###

import itertools

N, K = map(int, input().split())
p = list(map(int, input().split()))
ans = 10e6

for i in itertools.combinations(p, K):
    tmp = sum(list(i))
    if tmp < ans:
        ans = tmp

print(ans)


### FIXED CODE ###

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

ans = sum(sorted(p)[:K])
print(ans)
### BUGGY CODE ###

from collections import deque
import sys
input = sys.stdin.readline
h,w=map(int, input().split(' '))
a = [input() for i in range(h)]
nl = [[] for i in range(h)]
q = deque()
for i in range(h):
    for j in range(w):
        if a[i][j] == "#":
            nl[i].append(0)
            q.append([i,j,0])
        else:
            nl[i].append(-1)
while q:
    [s,t,cnt] = q.popleft()
    if s>0 and nl[s-1][t] == -1:
        q.append([s-1,t,cnt+1])
        nl[s-1][t] = cnt+1
    if s<h-1 and nl[s+1][t] == -1:
        q.append([s+1,t,cnt+1])
        nl[s+1][t] = cnt+1
    if t>0 and nl[s][t-1] == -1:
        q.append([s,t-1,cnt+1])
        nl[s][t-1] = cnt+1
    if t<w-1 and nl[s][t+1] == -1:
        q.append([s,t+1,cnt+1])
        nl[s][t+1] = cnt+1
ans = 0
for i in range(h):
    ans = max(ans,max(nl[i]))
print(ans)

### FIXED CODE ###

from collections import deque
import sys
input = sys.stdin.readline
h,w=map(int, input().split(' '))
a = [input() for i in range(h)]
nl = [[] for i in range(h)]
q = deque()
for i in range(h):
    for j in range(w):
        if a[i][j] == "#":
            nl[i].append(0)
            q.append([i,j,0])
        else:
            nl[i].append(-1)
while q:
    [s,t,cnt] = q.popleft()
    if s>0 and nl[s-1][t] == -1:
        q.append([s-1,t,cnt+1])
        nl[s-1][t] = cnt+1
    if s<h-1 and nl[s+1][t] == -1:
        q.append([s+1,t,cnt+1])
        nl[s+1][t] = cnt+1
    if t>0 and nl[s][t-1] == -1:
        q.append([s,t-1,cnt+1])
        nl[s][t-1] = cnt+1
    if t<w-1 and nl[s][t+1] == -1:
        q.append([s,t+1,cnt+1])
        nl[s][t+1] = cnt+1
ans = 0
for i in range(h):
    ans = max(ans,max(nl[i]))
print(ans)
### BUGGY CODE ###

from collections import Counter
N = int(input())
L = [input() for _ in range(N)]
#for n in range(N):
    #S = input()
    #L.append(S)
Dic = Counter(L)

max_k_list = [i for i, j in Dic.items() if j == max(Dic.values())]
max_k_list = sorted(max_k_list)
for t in max_k_list:
    print(t)

### FIXED CODE ###

from collections import Counter
N = int(input())
L = [input() for _ in range(N)]
#for n in range(N):
    #S = input()
    #L.append(S)
Dic = Counter(L)
max_value = max(Dic.values())
max_k_list = [i for i, j in Dic.items() if j == max_value]
max_k_list = sorted(max_k_list)
for t in max_k_list:
    print(t)
### BUGGY CODE ###

from collections import Counter
# union find
class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]

    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x

    def is_same(self, x, y):
        return self.find(x) == self.find(y)

N, M = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(M)]

AB = AB[::-1]
ret = []
tmp = 0
uf = UnionFind(N)
for a,b in AB:
    if uf.is_same(a-1, b-1):
        ret.append(0)
    else:
        c = Counter(uf.par)
        ret.append(c[uf.find(a-1)] * c[uf.find(b-1)])
        uf.union(a-1,b-1)
        for i in range(N):
            uf.find(i)

ans = 0
for i in range(M-1, -1, -1):
    ans += ret[i]
    print(ans)

### FIXED CODE ###

from collections import Counter
# union find
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)

    def find_root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            self.root[x] = self.find_root(self.root[x])
            return self.root[x]

    def unite(self, x, y):
        x = self.find_root(x)
        y = self.find_root(y)
        if(x == y):
            return 
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1

    def is_same_group(self, x, y):
        return self.find_root(x) == self.find_root(y)

    def count(self, x):
        return -self.root[self.find_root(x)]

N, M = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(M)]

AB = AB[::-1]
ret = []
tmp = 0
uf = UnionFind(N)
for a,b in AB:
    if uf.is_same_group(a-1, b-1):
        ret.append(0)
    else:

        ret.append(uf.count(a-1) * uf.count(b-1))
        uf.unite(a-1,b-1)

ans = 0
for i in range(M-1, -1, -1):
    ans += ret[i]
    print(ans)
### BUGGY CODE ###

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

for i in range(n):
    p[i]=(p[i]+1)/2#p[i]を期待値に変更
    
max_sum=0    
for i in range(n-k+2):
    max_sum=max(max_sum,sum(p[i:i+k]))
print(max_sum)


### FIXED CODE ###

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

for i in range(n):
    p[i]=(p[i]+1)/2#p[i]を期待値に変更
    
p_sum=[0]*n
ans=0
for i in range(n):
    if i==0:
        p_sum[i]=p[i]
        ans=p_sum[i]
    elif i<k:
        p_sum[i]=p_sum[i-1]+p[i]
        if p_sum[i]>ans:
            ans=p_sum[i]
    else:
        p_sum[i]=p_sum[i-1]+p[i]-p[i-k]
        if p_sum[i]>ans:
            ans=p_sum[i]
print(ans)
### BUGGY CODE ###

n = int(input())
ans = 1

nums = list(map(lambda x : int(x),input().split()))

for i in range(n):
    ans *= nums[i]
    
if ans > 10**18:
  ans = -1

print(ans)

### FIXED CODE ###

n = int(input())
ans = 1

nums = list(map(lambda x : int(x),input().split()))

for i in range(n):
    if nums[i] == 0:
        ans = 0
        break
        
for k in range(n):
    ans *= nums[k]
    if ans > 10**18:
        ans = -1
        break

print(ans)
### BUGGY CODE ###

n, k = map(int, input().split())
A = [*map(int, input().split())]

pre = 1
for i in range(k):
    pre *= A[i]

for i in range(k,n):
    now = pre//A[i-k] *A[i]
    if pre < now:
        print('Yes')
    else:
        print('No')
    pre = now


### FIXED CODE ###

n, k = map(int, input().split())
A = [*map(int, input().split())]
for i in range(k, n):
    if A[i-k] < A[i]: print('Yes')
    else: print('No')
### BUGGY CODE ###

import sys

h, n = list(map(int, input().split()))
INF = 10 ** 18
dp = [INF] * (h + 10001)
dp[0] = 0
for line in sys.stdin:
    a, b = map(int, line.split())
    for i in range(h):
        if dp[i] == INF:
            continue
        dp[i + a] = min(dp[i + a], dp[i] + b)
print(min(dp[h:]))


### FIXED CODE ###

import sys

h, n = list(map(int, input().split()))
INF = 10 ** 18
dp = [INF] * (20201)
dp[0] = 0
for line in sys.stdin:
    a, b = map(int, line.split())
    for i in range(10000):
        if dp[i] == INF:
            continue
        dp[i + a] = min(dp[i + a], dp[i] + b)
print(min(dp[h:]))
### BUGGY CODE ###

def main():
    n = int(input())
    inlis = list(map(int, input().split()))
    anstup = tuple()
    for i in range(n):
        junban = inlis.index(i+1) + 1
        tup = junban,
        anstup += tup
    print(*anstup)
    
if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    n = int(input())
    inlis = list(map(int, input().split()))
    anslis = [0] * n
    for i in range(n):
        num = inlis[i]
        anslis[num-1] = i+1
    print(*anslis)
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

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

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

_lcm=lcm(N,M)
n=_lcm//N
m=_lcm//M
for i in range(_lcm):
    if i%n==0 and i%m==0:
        if S[i//n]!=T[i//m]:
            print(-1)
            exit()
print(_lcm)


### FIXED CODE ###

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

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

_lcm=lcm(N,M)
n=_lcm//N
m=_lcm//M
for i in range(0,_lcm,n*m):
    if S[i//n]!=T[i//m]:
        print(-1)
        exit()    
print(_lcm)
### BUGGY CODE ###

s = input()
K = int(input())
alphabet = "abcdefghijklmnopqrstuvwxyz"
for alp in alphabet:
    sub = set()
    for i,S in enumerate(s):
        if S == alp:
            for j in range(i,len(s)):
                sub.add(s[i:j+1])
    if len(sub) < K:
        K -= len(sub)
    else:
        l_sub = list(sub)
        l_sub.sort()
        print(l_sub[K-1])
        exit()


### FIXED CODE ###

s = input()
K = int(input())
alphabet = "abcdefghijklmnopqrstuvwxyz"
for alp in alphabet:
    if alp not in s:
        continue
    sub = set()
    for i,S in enumerate(s):
        if S == alp:
            for j in range(i,min(i+5,len(s))):
                sub.add(s[i:j+1])
    if len(sub) < K:
        K -= len(sub)
    else:
        l_sub = list(sub)
        l_sub.sort()
        print(l_sub[K-1])
        exit()
### BUGGY CODE ###


import sys


def solv(n):
    r = 0
    if n % 2 == 1:
        if (n-2) in primes:
            return 1
    else:
        for p in primes:
            if n/2 < p:
                break
            q = n - p
            if q in primes:
                r += 1
    return r


def prime_list(n):
    limit = int(n ** 0.5) + 1
    lis = range(1, n + 1, 2)
    lis[0] = 2
    while True:
        if len(lis) == 0:
            break
        p = lis.pop(0)
        yield p
        if p <= limit:
            lis = [x for x in lis if x % p != 0]


primes = []
for p in prime_list(50000):
    primes.append(p)

while True:
    n = int(sys.stdin.readline())
    if n == 0:
        exit()
    print solv(n)

### FIXED CODE ###


import sys
import itertools


def prime_list(n):
    limit = int(n ** 0.5) + 1
    lis = range(1, n + 1, 2)
    lis[0] = 2
    while True:
        if len(lis) == 0:
            break
        p = lis.pop(0)
        yield p
        if p <= limit:
            lis = [x for x in lis if x % p != 0]


primes = []
for p in prime_list(50000):
    primes.append(p)
c = [0] * 50001 * 2
for i, j in itertools.combinations(primes, 2):
    c[i+j] += 1
for i in primes:
    c[i+i] += 1
while True:
    n = int(sys.stdin.readline())
    if n == 0:
        exit()
    print c[n]
### BUGGY CODE ###

k = int(input())
s = input()
len_s = len(s)
MOD = 1000000007

pow26 = [1] * (k + 1)
pow25_i = 1
comb_i = 1

for i in range(k):
  pow26[i+1] = (pow26[i] * 26) % MOD

a = 0
for i in range(k + 1):  
  a += (((comb_i  * pow26[k-i]) % MOD) * pow25_i ) % MOD
  a %= MOD

  pow25_i = (pow25_i * 25) % MOD
  comb_i = ((((comb_i * (len_s + i)) % MOD)) * pow(i + 1, -1, MOD)) % MOD


print(a)

### FIXED CODE ###

k = int(input())
s = input()
len_s = len(s)
MOD = 1000000007

x_i = pow(26, k, MOD)
r = (25 * pow(26, -1, MOD)) % MOD
comb_i = 1

a = 0
for i in range(k + 1):  
  a += (comb_i  * x_i  ) % MOD
  a %= MOD
  
  x_i  = (x_i  * r) % MOD
  comb_i = (comb_i * (len_s + i) * pow(i + 1, -1, MOD)) % MOD


print(a)