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

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

def main():        
    h,w=map(int,input().split())
    s=[[]*w for _ in range(h)]
    for i in range(h):
        s[i]=list(input())
    chk=deque()
    d=[[0,1],[0,-1],[1,0],[-1,0]]

    def bfs(x,y):
        ans,dist=0,0
        a=[[-1]*w for _ in range(h)]
        chk.append([x,y,0])
        a[x][y]=0
        while chk:
            x,y,dist=chk.popleft()
            bx,by=x,y
            a[x][y]=dist
            for dx,dy in d:
                x=dx+bx
                y=dy+by
                if x>=0 and y>=0 and x<=h-1 and y<=w-1:
                    if s[x][y]=='.' and a[x][y]==-1:
                        chk.append([x,y,dist+1])
        ans=0
        for i in range(h):
                ans=max(ans,max(a[i]))
        return ans
    
    ans=0
    for i in range(h):
        for j in range(w):
            if s[i][j]=='#':
                continue
            ans=max(ans,bfs(i,j))
    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

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

def main():        
    h,w=map(int,input().split())
    s=[input() for _ in range(h)]

    def bfs(x,y):
        dist=[[-1]*w  for _ in range(h)]
        seen=[[False]*w for _ in range(h)]
        stk=[(x,y,0)]
        while stk:
            px,py,dst=stk.pop(0)
            if seen[px][py]:
                continue
            seen[px][py]=True
            
            if s[px][py]=='#':
                dist[px][py]=0
                continue
            
            for x,y in [(-1,0),(1,0),(0,-1),(0,1)]:
                if px+x<0 or px+x>=h or py+y<0 or py+y>=w:
                    continue
                else:
                    stk.append((px+x,py+y,dst+1))
            dist[px][py]=dst
        ans=0
    
        for i in range(h):
            ans=max(max(dist[i]),ans)
        return ans
    
    ans=0
    for i in range(h):
        for j in range(w):
            if s[i][j]=='#':
                continue
            ans=max(ans,bfs(i,j))
    print(ans)

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

# -*- condig:utf-8 -*-

import sys
sys.setrecursionlimit(10000000)

n, q = map(int, input().split())
g = []
o = []
counter = []
for i in range(n+1):
  counter.append(0)
  o.append(0)
  g.append([])

for i in range(n-1):
  a,b= map(int, input().split())
  g[a].append(b)
  g[b].append(a)

for i in range(q):
  p,x= map(int, input().split())
  o[p] += x


queue = [1]
parents = []
while queue:
  p = queue.pop(0)
  parents.append(p)
  count = o[p]
  flag = False
  for i in g[p]:
    if not i in parents:
      queue.append(i)
    else:
      count += counter[i]
  counter[p] += count
 
for i in range(1, n+1):
  print(counter[i], end=' ')

 
  


### FIXED CODE ###


n, q = map(int, input().split())

ct = [0] * (n+1)
o = [0] * (n+1)
g = [[] for _ in range(n+1)]

for i in range(n-1):
  a,b= map(int, input().split())
  g[a].append(b)
  g[b].append(a)

for i in range(q):
  p,x= map(int, input().split())
  o[p] += x

todo = [1]
seen = [False] * (n+1)
while todo:
  p = todo.pop(-1)
  ct[p] += o[p]
  seen[p] = True
  for i in g[p]:
    if seen[i]:
      ct[p] += ct[i]
    else:
      todo.append(i)

print(*ct[1:])
### BUGGY CODE ###

import sys
import numpy as np

N = int(sys.stdin.readline())
A = np.array(list(map(int, sys.stdin.readline().split())), dtype=np.uint32)
Q = int(sys.stdin.readline())
replace_map = [list(map(int, sys.stdin.readline().split())) for i in range(Q)]

for search, replace in replace_map:
    A[A == search] = replace
    print(np.sum(A))


### FIXED CODE ###

import sys
import numpy as np

_ = sys.stdin.readline()
A = list(map(int, sys.stdin.readline().split()))
Q = int(sys.stdin.readline())
replace_map = [list(map(int, sys.stdin.readline().split())) for _ in range(Q)]

nums = {}
for a in A:
    nums[a] = nums[a] + 1 if a in nums else 1

previous_sum = 0
for search, replace in replace_map:
    replaced_count = 0
    if search in nums:
        replaced_count = nums[search]
        nums[replace] = nums[replace] + replaced_count if replace in nums else replaced_count
        del nums[search]
    if previous_sum == 0:
        previous_sum = np.dot(list(nums.keys()), list(nums.values()))
    else:
        previous_sum += replaced_count * (replace - search)
    print(previous_sum)
### BUGGY CODE ###

# input
N, M = map(int, input().split())
W = []
V = []
for _ in range(N):
    w, v = map(int, input().split())
    W.append(w)
    V.append(v)

dp = [[None for __ in range(M+1)] for _ in range(N+1)]
dp[0] = [0 for _ in range(M+1)]
for i in range(1, N+1):
    for w in range(M+1):
        if W[i-1] <= w:
            dp[i][w] = max(dp[i-1][w], dp[i-1][w-W[i-1]] + V[i-1])
        else:
            dp[i][w] = dp[i-1][w]


print(max(dp[-1]))


### FIXED CODE ###

# input
N, M = map(int, input().split())
W = []
V = []
for _ in range(N):
    w, v = map(int, input().split())
    W.append(w)
    V.append(v)

dp = [[None for __ in range(M+1)] for _ in range(N+1)]
dp[0] = [0 for _ in range(M+1)]
for i in range(1, N+1):
    for w in range(M+1):
        if W[i-1] <= w:
            dp[i][w] = max(dp[i-1][w], dp[i-1][w-W[i-1]] + V[i-1])
        else:
            dp[i][w] = dp[i-1][w]


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

N, Y = map(int, input().split())
count = 0

for i in range(N+1):# 10000円札
  for j in range(N+1):# 5000円札
    if count == 0:
      X1 = Y - 10000*i - 5000*j
      X = X1//1000
      if (X1 % 1000 == 0) & (X == N-i-j) & (X>=0):
        print(i, j, X)
        count += 1
        break

if count == 0:
  print('-1 -1 -1')


### FIXED CODE ###

N, Y = map(int, input().split())
count = 0
Y = Y//1000

for i in range(N+1):# 10000円札
  for j in range(N+1):# 5000円札
    if count == 0:
      X = Y - 10*i - 5*j
      if (X == N-i-j) & (X>=0):
        print(i, j, X)
        count += 1
    else:
      break

if count == 0:
  print('-1 -1 -1')
### BUGGY CODE ###

import collections
n,m = list(map(int,input().split()))

di = collections.defaultdict(list)
for i in range(m):
    a,b = list(map(int,input().split()))
    di[a-1].append(b-1)
    di[b-1].append(a-1)

ans=[-1]*n
que = [0]
serched = []
#print(di)

while 1:
    tmp = []
    for i in que:
        for j in di[i]:
            if j in serched:
                continue
            ans[j]=i+1
            serched.append(j)
            tmp.append(j)
    if len(tmp)==0:
        break
    que = tmp[:]
print("Yes")
for i in ans[1:]:
    print(i)

### FIXED CODE ###

import collections
n,m = list(map(int,input().split()))
ans = [0]*n
graph = [[] for _ in range(n)]
for i in range(m):
    a,b = list(map(int,input().split()))
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
D = collections.deque([0])
visited = [False]*n
visited[0]=True

while D:
    v = D.popleft()
    for i in graph[v]:
        if visited[i]:continue
        visited[i]=True
        ans[i]=v
        D.append(i)
print("Yes")
for i in ans[1:]:
    print(i+1)
### BUGGY CODE ###

N,K=list(map(int,input().split()))
a_list=list(map(int,input().split()))
a_mul = [1]
for i,a in enumerate(a_list):
  a_mul.append(a_mul[i] * a)

for i in range(K+1,N+1):
  iscore = a_mul[i]//a_mul[i-K]
  i_score = a_mul[i-1]//a_mul[i-1-K]
  print('Yes' if iscore > i_score else 'No')

### FIXED CODE ###

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

for i in range(K,N):
  iscore = a_list[i]
  i_score = a_list[i-K]
  print('Yes' if iscore > i_score else 'No')
### BUGGY CODE ###

from time import time
from random import randint

from numba import njit
from numpy import int64

@njit('i8(i8[:],i8[:])')
def func(s,x):
    last=[0]*26
    score=0
    for i,v in enumerate(x,1):
        last[v]=i
        c=0
        for j in range(26):
            c+=s[j]*(last[j]-i)
        score=score+s[i*26+v]-c
    return score

def main():
    start=time()
    d,*s=map(int,open(0).read().split())
    s=int64(s)
    x=int64(([*range(26)]*15)[:d])
    M=func(s,x)
    while time()-start<1.7:
        y=x.copy()
        y[randint(0,d-1)]=randint(0,25)
        t=func(s,y)
        if t>M:
            M=t
            x=y
    print(*x,sep='\n')

main()

### FIXED CODE ###

from time import time
from random import randint

from numba import njit
from numpy import int64

@njit('i8(i8[:],i8[:])')
def func(s,x):
    last=[0]*26
    score=0
    for i,v in enumerate(x,1):
        last[v]=i
        c=0
        for j in range(26):
            c+=s[j]*(last[j]-i)
        score=score+s[i*26+v]-c
    return score

def main():
    start=time()
    d,*s=map(int,open(0).read().split())
    s=int64(s)
    x=int64(([*range(26)]*15)[:d])
    M=func(s,x)
    while time()-start<1:
        y=x.copy()
        y[randint(0,d-1)]=randint(0,25)
        t=func(s,y)
        if t>M:
            M=t
            x=y
    print(*x+1,sep='\n')

main()
### BUGGY CODE ###

s=[i for i in input()]
leng=len(s)
flg=True
while flg:
    flg=False
    for i in range(len(s)-1):
        if s[i]!=s[i+1]:
            s.pop(i+1)
            s.pop(i)
            flg=True
            break
print(leng - len(s))     
    

### FIXED CODE ###

s=input()
print(min(s.count("0") , s.count("1")) * 2)
### BUGGY CODE ###

A,B=map(int,input().split())
b=A
for x in range(A+1,B+1):
    b = x^b

print(b)

### FIXED CODE ###

import math
A,B=map(int,input().split())
x=0
if A%2==0:#偶数スタート
    if(B%2==0):#偶数エンド
        if((B-A)/2 %2 == 0 ):#1が偶数個ならば？
            print(B)
        else:
            print(1^B)
    else:#奇数エンド
        if(((B+1) - A)/2 %2 == 0):#1が偶数個ならば？
            print(0)
        else:
            print(1)
else:#奇数スタート
    if(B%2==0):#偶数エンド
        if((B-(A+1))/2 %2 ==0):
            print(A^B)
        else:
            print(A^B^1)
    else:#奇数エンド
        if((B-A)/2 %2 == 0):
            print(A)
        else:
            print(A^1)
### BUGGY CODE ###

n,m = map(int, input().split())
cn = [i for i in range(1,n+1)]
for i in range(m):
    l,r = map(int, input().split())
    lr = [i for i in range(l,r+1)]
    cn = set(cn)&set(lr)
print(len(cn))

### FIXED CODE ###

n,m = map(int, input().split())
fn = 1
ln = n
for i in range(m):
    l,r = map(int, input().split())
    fn = max(fn,l)
    ln = min(ln,r)    
print(ln-fn+1 if ln-fn>=0 else 0)
### BUGGY CODE ###

n, m = map(int, input().split())
A = [list(map(str, input().split())) for _ in range(m)]

ans = 0
pen = 0

def get_dup(seq):
    seen = []
    return [x for x in seq
            if not seen.append(x) and seen.count(x) == 0
            or not seen.append(x) and seen.count(x) == 2]

A=get_dup(A)

for a in A:
    if a[1]=='AC':
        ans += 1
    if a[1] == 'WA':
        pen += 1

print(ans, pen)

### FIXED CODE ###

n, m = map(int, input().split())

ac = [0]*n
wa = [0]*n

for _ in range(m):
    p, s = map(str, input().split())
    p = int(p)

    if ac[p-1]:
        continue
    else:
        if s == 'AC':
            ac[p-1] = 1
        else:
            wa[p-1] += 1

AC = 0
WA = 0
for i in range(n):
    AC += ac[i]
    if ac[i]:
        WA += wa[i]

print(AC, WA)
### BUGGY CODE ###

import sys,time
sys.setrecursionlimit(10**7)

start_time = time.time()
N,M = map(int,input().split())
S = input()
src = [tuple(map(lambda x:int(x)-1,input().split())) for i in range(M)]

outdeg = [set() for i in range(2*N)]
for x,y in src:
    if S[x] == S[y]:
        #A0->A1, B0->B1
        outdeg[x].add(y+N)
        outdeg[y].add(x+N)
    else:
        #A1->B0, B1->A0
        outdeg[x+N].add(y)
        outdeg[y+N].add(x)

mem = [0] * (2*N)
def visit(v):
    if mem[v] == 1:
        print('Yes')
        exit()
    if mem[v] == 0:
        mem[v] = 1
        for to in outdeg[v]:
            visit(to)
        mem[v] = 2

for i in range(2*N):
    visit(i)
    # gori~~~
    if time.time() - start_time > 1.9:
        break
print('No')

### FIXED CODE ###

import sys,time
sys.setrecursionlimit(10**7)

start_time = time.time()
N,M = map(int,input().split())
S = input()
src = [tuple(map(lambda x:int(x)-1,sys.stdin.readline().split())) for i in range(M)]

outdeg = [set() for i in range(2*N)]
for x,y in src:
    if S[x] == S[y]:
        #A0->A1, B0->B1
        outdeg[x].add(y+N)
        outdeg[y].add(x+N)
    else:
        #A1->B0, B1->A0
        outdeg[x+N].add(y)
        outdeg[y+N].add(x)

mem = [0] * (2*N)
def visit(v):
    if time.time() - start_time > 1.8:
        # gori~~~
        print('No')
        exit()
    if mem[v] == 1:
        print('Yes')
        exit()
    if mem[v] == 0:
        mem[v] = 1
        for to in outdeg[v]:
            visit(to)
        mem[v] = 2

for i in range(2*N):
    visit(i)

print('No')
### BUGGY CODE ###

from itertools import*
n,k=map(int,input().split())
a=10**20
for z in combinations(sorted(list(map(int,input().split()))for _ in range(n)),k):
    y=[j for _,j in z]
    a=min(a,(z[-1][0]-z[0][0])*(max(y)-min(y)))
print(a)

### FIXED CODE ###

n,k=map(int,input().split())
z=[list(map(int,input().split()))for _ in range(n)]
z.sort()
a=10**20
for i in range(n):
    for j in range(i+1,n):
        x=z[j][0]-z[i][0]
        l=sorted(t[1]for t in z[i:j+1])
        for u,v in zip(l,l[k-1:]):
            a=min(a,x*(v-u))
print(a)
### BUGGY CODE ###

import sys
import numpy as np


def read():
    return sys.stdin.buffer.readline().rstrip()


def main():
    n, q = map(int, read().split())
    a = np.array([int(i) for i in read().split()])
    for _ in range(q):
        query = [int(i) for i in read().split()]
        if query[0] == 0:
            a[query[1]] += query[2]
        else:
            print(a[query[1]:query[2]].sum())


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys


def read():
    return sys.stdin.buffer.readline().rstrip()


class FenwickTree:
    def __init__(self, n):
        self._n = n
        self._a = [0] * n

    def add(self, i, x):
        i += 1
        while i <= self._n:
            self._a[i - 1] += x
            i += i & -i

    def sum(self, l, r):
        return self._sum(r) - self._sum(l)

    def _sum(self, r):
        s = 0
        while r > 0:
            s += self._a[r - 1]
            r -= r & -r
        return s


def main():
    n, q = map(int, read().split())
    fw = FenwickTree(n)
    for i, ai in enumerate(map(int, read().split())):
        fw.add(i, ai)
    for _ in range(q):
        query = [int(i) for i in read().split()]
        if query[0] == 0:
            fw.add(query[1], query[2])
        else:
            print(fw.sum(query[1], query[2]))


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

N = int(input())
A = [int(input()) for _ in range(N)]

print(max(A[1:]))
for i in range(1, N-1):
    print(max(max(A[:i]), max(A[i+1:])))
print(max(A[:-1]))


### FIXED CODE ###

n=int(input())
a = [int(input()) for i in range(n)]
b = sorted(a)
for i in a:
    print(b[-2] if i==b[-1] else b[-1])
### BUGGY CODE ###

from sys import stdin

class DList:
    class Cell:
        def __init__(self, k):
            self.key  = k
            self.prev = None
            self.next = None

    def __init__(self):
        self.head = DList.Cell(None)
        self.last = DList.Cell(None)
        self.head.next = self.last
        self.last.prev = self.head

    def insert(self, x):
        c = DList.Cell(x)
        c.prev = self.head
        c.next = self.head.next
        c.next.prev = c
        self.head.next = c

    def delete(self, x):
        c = self.__find(x)
        if c != None:
            self.__delete(c)

    def __delete(self, c):
        c.prev.next = c.next
        c.next.prev = c.prev

    def __find(self, x):
        c = self.head.next
        while c != None and c.key != x:
            c = c.next
        return c

    def deleteFirst(self):
        self.__delete(self.head.next)
    def deleteLast(self):
        self.__delete(self.last.prev)

    def __iter__(self):
        self.it = self.head.next
        return self
    def __next__(self):
        if self.it == self.last:
            raise StopIteration
        k = self.it.key
        self.it = self.it.next
        return k

dlist = DList()

n = int(stdin.readline())
for i in range(n):
    cmd = tuple(stdin.readline().split())
    if   cmd[0] == 'insert':
        dlist.insert(int(cmd[1]))
    elif cmd[0] == 'delete':
        dlist.delete(int(cmd[1]))
    elif cmd[0] == 'deleteFirst':
        dlist.deleteFirst()
    elif cmd[0] == 'deleteLast':
        dlist.deleteLast()

print(' '.join(map(str, dlist)))


### FIXED CODE ###

from sys import stdin

class DList:
    class Cell:
        def __init__(self, k):
            self.key  = k
            self.prev = None
            self.next = None

    def __init__(self):
        self.head = DList.Cell(None)
        self.last = DList.Cell(None)
        self.head.next = self.last
        self.last.prev = self.head

    def insert(self, x):
        c = DList.Cell(x)
        c.prev = self.head
        c.next = self.head.next
        c.next.prev = c
        self.head.next = c

    def delete(self, x):
        c = self.__find(x)
        if c != None:
            self.__delete(c)

    def __delete(self, c):
        c.prev.next = c.next
        c.next.prev = c.prev

    def __find(self, x):
        c = self.head.next
        while c != None and c.key != x:
            c = c.next
        return c

    def deleteFirst(self):
        self.__delete(self.head.next)
    def deleteLast(self):
        self.__delete(self.last.prev)

    def __iter__(self):
        self.it = self.head.next
        return self
    def __next__(self):
        if self.it == self.last:
            raise StopIteration
        k = self.it.key
        self.it = self.it.next
        return k

dlist = DList()

n = int(stdin.readline())
for i in range(n):
    cmd = stdin.readline()
    if   cmd.startswith('insert'):
        dlist.insert(cmd[7:-1])
    elif cmd.startswith('deleteFirst'):
        dlist.deleteFirst()
    elif cmd.startswith('deleteLast'):
        dlist.deleteLast()
    elif cmd.startswith('delete'):
        dlist.delete(cmd[7:-1])

print(' '.join(dlist))
### BUGGY CODE ###

N = int(input())
L = [int(input()) for i in range(N)]
A = []
for i in range(len(L)):
  if (L[i] not in A):
    A.append(L[i])
k = 0
for j in range(len(A)):
  s = L.count(A[j])
  if (s%2 != 0):
    k += 1
print(k)

### FIXED CODE ###

N = int(input())
A = [int(input()) for i in range(N)]
A.sort()
j = 1
J = 1
ans = 0
for j in range(1,len(A)):
  if (A[j-1] == A[j]):
    J += 1
  else:
    if (J%2 != 0):
      ans += 1
      J = 1
    else:
      J = 1
if (J%2 != 0):
  ans += 1
print(ans)
### BUGGY CODE ###

N, M, K = map(int, input().split())
P = 10**9+7
fact = [1]
for i in range(N*M):
    fact.append(fact[-1]*(i+1))
def inv(n):
    return pow(n, P-2, P)
def C(a, b):
    return fact[a]*inv(fact[a-b]*fact[b])%P
print((M**2*(N**3-N)+N**2*(M**3-M))//6*C(M*N-2, K-2)%P)

### FIXED CODE ###

N, M, K = map(int, input().split())
P = 10**9+7
fact = [1]
for i in range(N*M):
    fact.append(fact[-1]*(i+1)%P)
def inv(n):
    return pow(n, P-2, P)
def C(a, b):
    return fact[a]*inv(fact[a-b]*fact[b])%P
print((M**2*(N**3-N)+N**2*(M**3-M))//6*C(M*N-2, K-2)%P)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10000000)


def ans(chance, a, start, end):
    if start > end:
        return 0
    temp = -1 if chance else 1
    val1 = a[start]*temp + ans((chance+1) % 2, a, start+1, end)
    val2 = a[end]*temp + ans((chance+1) % 2, a, start, end-1)
    return min(val1, val2) if chance else max(val1, val2)


def main():
    n = int(input())
    a = list(map(int, input().split()))
    print(ans(0, a, 0, n-1))


if __name__ == "__main__":
    main()


### FIXED CODE ###


def main():
    n = int(input())
    a = list(map(int, input().split()))

    dp = [[0 for i in range(n+2)]for i in range(n+2)]
    # dp [start][end] is the diffence between X and Y
    # such for range start to end
    for start in range(n, 0, -1):
        for end in range(start, n+1):
            if start == end:
                dp[start][end] = a[start-1]
            else:
                dp[start][end] = max(a[start-1]-dp[start+1]
                                     [end], a[end-1]-dp[start][end-1])
    print(dp[1][n])


if __name__ == "__main__":
    main()
### BUGGY CODE ###

n, m = map(int, input().split(' '))
l = [set(map(int, input().split(' '))) for _ in range(m)]
max_useless = n*(n-1)//2
ll = [[l[-1]]]

for i in range(2, m):
  x = ll[-1]
  ind = []
  se = l[-i]
  for j in range(len(x)):
    if x[j] & se:
      ind.append(j)
  if not ind:
    ll.append(ll[-1] + [se])
  else:
    for j in ind:
      se = se | x[j]
    ll.append([x[j] for j in range(len(x)) if j not in ind] + [se])

def func(lis):
  count = 0
  for x in lis:
    y = len(x)
    count += y*(y-1)//2
  return max_useless - count

for i in range(1, m):
  print(func(ll[-i]))
print(max_useless)

### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline
n,m=map(int,input().split())
z=n*(n-1)//2
l=[-1]*n
a=[1]*n
b=[input().split() for _ in range(m)]
c=[0]*m+[z]
def r(s):
  t=l[s]
  if t<0:
    return s
  else:
    l[s]=r(t)
    return l[s]
def f(s):
  return r(int(s)-1)
for i in range(m-1,-1,-1):
  x,y=map(f,b[i])
  if x!=y:
    l[x]=y
    z-=a[x]*a[y]
    a[y]+=a[x]
  c[i]=z
for x in c[1:]:
  print(x)
### BUGGY CODE ###

n,k,q = (int(x) for x in input().split())
p = [k]*n
for x in range(q):
  for y in range(len(p)):
    p[y] -= 1
  s = int(input())
  p[s-1] += 1
for z in range(len(p)):
  if p[z] > 0:
    print("Yes")
  else:
    print("No")

### FIXED CODE ###

n,k,q = (int(x) for x in input().split())
p = [k-q]*n
for x in range(q):
  s = int(input())
  p[s-1] += 1
for z in range(len(p)):
  if p[z] > 0:
    print("Yes")
  else:
    print("No")
### BUGGY CODE ###

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


N, M = map(int, input().split())
S = input()
T = input()
L = lcm(N, M)
d = {}
s = list()
# s = set()
for i in range(N):
    d[str(i * (L // N))] = S[i]
    s.append(str(i * (L // N)))
    # s.add(str(i * (L // N)))

for i in range(M):
    key = str(i * (L // M))
    if key in s:
        if d[key] != T[i]:
            print(-1)
            exit()
print(L)

### FIXED CODE ###

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


N, M = map(int, input().split())
S = input()
T = input()
L = lcm(N, M)
d = {}
s = set()
for i in range(N):
    d[str(i * (L // N))] = S[i]
    s.add(str(i * (L // N)))

for i in range(M):
    key = str(i * (L // M))
    if key in s:
        if d[key] != T[i]:
            print(-1)
            exit()
print(L)
### BUGGY CODE ###

# gcdより長いのは存在しなさそう（勘）なので存在するとしたらgcd
# 実際に試していく
n, m = map(int, input().split())
s, t = input(), input()


def lcm(a, b):
    if a > b:
        return lcm(b, a)
    while 0 != a:
        a, b = b % a, a
    return b


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


u = gcd(n, m)
v = [None for _ in range(u)]
x1 = 0
while x1 < n:
    p = x1 * (u // n) + 1
    # print("p = {}".format(p))
    # if v[p - 1] == None:
    #     v[p - 1] = s[x1]
    # else:
    #     print("すでに入ってるのでおしまい")
    v[p - 1] = s[x1]
    x1 += 1
x2 = 0
while x2 < m:
    p = x2 * (u // m) + 1
    if v[p - 1] == None:
        if x2 > 0:
            v[p - 1] = t[x2]
        else:
            if s[0] == t[0]:
                continue
            else:
                print(-1)
                exit()
    else:
        if v[p - 1] != t[x2]:
            print(-1)
            exit()
    x2 += 1
print(u)


### FIXED CODE ###

# たぶん最小の値は最小公倍数になりそう
# 内包表記 -> TLE
# [0]*l -> RE

n, m = map(int, input().split())
s, t = input(), input()


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


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


l = lcm(n, m)
arr = {}

for i in range(n):
    x = i * (l // n)
    arr[x] = s[i]

for i in range(m):
    x = i * (l // m)
    if x in arr and arr[x] != t[i]:
        print(-1)
        exit()
print(l)