Harryxun/stf_run huggingface dataset:
X = map(int,input().split())

K = 1
direct = X
while True:
  
  if direct % 360 = 0
  	break
  direct += X
  K += 1

print(K)

### FIXED CODE ###

X = int(input())

K = 1
dire = X
while True:
  if (dire % 360) == 0:
    break
  K+=1
  dire+=X

  
print(K)
import math

A,B=map(int,input().split())
g=math.gcd(A,B)

n=int(A*B/g)

print(n)


### FIXED CODE ###

A,B=map(int,input().split())
def gcd(A,B):
    while B!=0:
        A,B=B,A%B
    return A
print(int(A*B/gcd(A,B)))
N,K=map(int,input().split())
if N>=1 and 100>=K and N%K==0:
  print(0)
elif N>=1 and 100>=K and N%K == !0:
  print(N%K)

### FIXED CODE ###

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

if n%k==0:
  print(n%k)
else:
  print(1)
import re

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

X = []

for n in range(N-1):
    if H[n] >= H[n+1]:
        X.append('T')
    else:
        X.append('F')

XX = ''.join(X)

T = re.findall('T*T', XX)

Y=[]
for y in T:
    Y.append(len(y))

print(max(Y))

### FIXED CODE ###

import re

N = int(input())
H = list(map(int, input().split()))
X = []

if N == 1:
    print('0')
else:
    for n in range(N-1):
        if H[n] >= H[n+1]:
            X.append('T')
        else:
            X.append('F')

    XX = ''.join(X)

    if XX.find('T') == -1:
        print('0')
    else:
        T = re.findall('T*T', XX)

        Y=[]
        for y in T:
            Y.append(len(y))

        print(max(Y))
import numpy as np
from itertools import accumulate

N, M = map(int, input().split())
P = []
p = [0] * (N+1)
for i in range(M):
    p1, y1 = map(str, input().split())
    p[int(p1)] += 1
    P.append(int(p1+y1.rjust(10,"0")))
    
ans = np.argsort(P)
ans = np.argsort(ans)
p = list(accumulate(p))

for i in range(M):
    a = P[i] // 10 ** 6 
    print(str(a).rjust(6,"0") + str(ans[i] - p[a-1] + 1).rjust(6,"0"))

### FIXED CODE ###

import numpy as np
from itertools import accumulate

N, M = map(int, input().split())
P = []
p = [0] * (N+1)
for i in range(M):
    p1, y1 = map(str, input().split())
    p[int(p1)] += 1
    P.append(int(p1+y1.rjust(10,"0")))
    
ans = np.argsort(P)
ans = np.argsort(ans)
p = list(accumulate(p))

for i in range(M):
    a = P[i] // 10 ** 10 
    print(str(a).rjust(6,"0") + str(ans[i] - p[a-1] + 1).rjust(6,"0"))
n,m=list(map(int, input().split() ))
Firstlis=[]
Secondlis=[]
for i in range(m):
  s=list(map(int,inout().split()))
S1=s[0]
S2=s[1]
Firstlis.append(S1)
Secondlis.append(S2)
Min=max(Firstlis)
Max=min(Secondlis)
print(Max-Min)


  


### FIXED CODE ###

n,m=list(map(int, input().split() ))
Firstlis=[]
Secondlis=[]
for i in range(m):
  s=list(map(int,input().split()))
  S1=s[0]
  S2=s[1]
  Firstlis.append(S1)
  Secondlis.append(S2)
Min=max(Firstlis)
Max=min(Secondlis)
if Max>=Min:
    print(Max-Min+1)
else:
    print(0)
import numpy as np
N, A = map(int, input().split())
x = list(map(int, input().split()))

X = max(x)
if X < A:
    X = A

def check(j, k, s):
    if dp[j][k][s] != -1:
        return dp[j][k][s]
    if j == 0 and k == 0 and s == 0:
        dp[j][k][s] = 1
        return 1
    if j >= 1 and s < x[j-1]:
        a = check(j-1, k ,s)
        dp[j][k][s] = a
        return a
    if j >= 1 and k >= 1 and s >= x[j-1]:
        a = check(j-1, k, s) + check(j-1, k-1, s-x[j-1])
        dp[j][k][s] = a
        return a
    dp[j][k][s] = 0
    return 0
        
dp = [[[-1] * (N*X+1) for _ in range(N+1)] for _ in range(N + 1)]
# dp = np.array(dp)
# print (dp)
# for j in range(N+1):
#     for k in range(N+1):
#         for s in range(N*X + 1):
#             print (j, k, s)
#             dp[j][k][s] = check(j, k, s)

ans = 0
for k in range(1, N+1):
    ans += check(N, k, k * A)
    # ans += dp[N][k][k * A]

print (ans)

### FIXED CODE ###

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

X = max(x)
if X < A:
    X = A

def check(j, k, s):
    if dp[j][k][s] != -1:
        return dp[j][k][s]
    if j == 0 and k == 0 and s == 0:
        dp[j][k][s] = 1
        return 1
    if j >= 1 and s < x[j-1]:
        a = check(j-1, k ,s)
        dp[j][k][s] = a
        return a
    if j >= 1 and k >= 1 and s >= x[j-1]:
        a = check(j-1, k, s) + check(j-1, k-1, s-x[j-1])
        dp[j][k][s] = a
        return a
    dp[j][k][s] = 0
    return 0
        
dp = [[[-1] * (N*X+1) for _ in range(N+1)] for _ in range(N + 1)]
# dp = np.array(dp)
# print (dp)
# for j in range(N+1):
#     for k in range(N+1):
#         for s in range(N*X + 1):
#             print (j, k, s)
#             dp[j][k][s] = check(j, k, s)

ans = 0
for k in range(1, N+1):
    ans += check(N, k, k * A)
    # ans += dp[N][k][k * A]

print (ans)
l = [int(input())for i in range(5)]
num = l.index(min(l))
sum = 0
for i in range(5):
    if i != num:
        ans += -(-l[i] // 10)
print(ans*10)

### FIXED CODE ###

l = [int(input())for i in range(5)]
l1 = ['']*5
ans = 0
for i in range(5):
    l1[i] = l[i]%10
    if l1[i] == 0:
        l1[i] = 10
for i in range(5):
    ans += -(-l[i]//10)
print(ans*10 - 10 + min(l1))
import math
n, m = map(int, input().split())

list1 = list(map(int,input().split()))
list1.sort()
list1.reverse()

i=0
s = math.floor(list1[0]/2)

if n==1:
    print(math.floor(list[1]/(2**m)))
    # 処理終了
    exit() 

while True:
    while True:
        if i+1 > n:
            break
        if list1[i] < s or m == 0:
            break
        list1[i] = math.floor(list1[i]/2)
        m -= 1
        i += 1
    if m==0:
        break
    list1.sort()
    list1.reverse()
    s = math.floor(list1[0]/2)
    i = 0
print(sum(list1))


### FIXED CODE ###

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

list1 = list(map(int,input().split()))
list1.sort()
list1.reverse()
i = 0
s = math.floor(list1[0]/2)
 
if n == 1:
    print(math.floor(list1[0]/(2**m)))
    exit()
 
while True:
    while True:
        if i+1 > n:
            break
        if list1[i] < s or m == 0:
            break
        list1[i] = math.floor(list1[i]/2)
        m -= 1
        i += 1
    if m == 0:
        break
    list1.sort()
    list1.reverse()
    s = math.floor(list1[0]/2)
    i = 0
print(sum(list1))
import math
N,M = list(map(int,input().split()))

def combination(n,r):
    return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))

ans = combination(N,2) + combination(M,2)

print(ans)

### FIXED CODE ###

N,M = list(map(int,input().split()))
ans = (N*(N-1)//2) + (M*(M-1)//2)
print(ans)
a,b = map(int, input().split())

c = a * b
d = (a + b) *2

print(c d)

### FIXED CODE ###

a,b = map(int, input().split())

c,d = a * b,(a + b) *2

print(str(c) + " " + str(d))
A = sorted(input())
B = sorted(input(), reversed=True)
if A < B:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

A = "".join((sorted(input())))
B = "".join(sorted(input(), reverse=True))
print("Yes" if A < B else "No")
import numpy as np


def div(n, d):
    cnt = 0
    while n % d == 0 and cnt < 18:
        n //= d
        cnt += 1
    return cnt


n = int(input())
arr = np.array([float(input()) for _ in range(n)], np.float64)
arr = np.rint(arr * 10**9).astype(np.int64)

f = np.vectorize(div)
arr2 = (f(arr, 2) + np.zeros([arr.shape[0],　arr.shape[0]], np.int64)).astype(np.int32)
arr5 = (f(arr, 5) + np.zeros([arr.shape[0],　arr.shape[0]], np.int64)).astype(np.int32)

arr2 = np.tril(arr2 + arr2.T)
arr2 -= arr2.T
arr5 = np.tril(arr5 + arr5.T)
arr5 -= arr5.T

result = (arr2 >= 18).astype(np.int32) + (arr5 >= 18).astype(np.int32)

print(np.sum(result >= 2))

### FIXED CODE ###

def div(n, d):
    cnt = 0
    while n % d == 0 and cnt < 18:
        n //= d
        cnt += 1
    return cnt


n = int(input())
dp = [[0]*19 for _ in range(19)]

ans = 0
for _ in range(n):
    x = round(float(input()) * pow(10, 9))
    two = div(x, 2)
    five = div(x, 5)
    ans += dp[18 - two][18 - five]
    for i in range(two + 1):
        for j in range(five + 1):
            dp[i][j] += 1

print(ans)
N,M = map(int,input().split())
A = list(map(int,input().split()))

R = [A[0]%M]


for i in range(1,N):
  R.append((R[-1]+A[i])%M)


k = set(R)
dic = {i:0 for i in k}
for item in R:
  dic[item]+=1

ans = (dic[0]*(dic[0]+1))//2

k_l = list(k)
for i in k_l:
  if i !=0 :
    ans += (dic[i]*(dic[i]-1))//2

print(ans)


### FIXED CODE ###

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

R = [A[0]%M]


for i in range(1,N):
  R.append((R[-1]+A[i])%M)



import collections
c = collections.Counter(R)


ans = 0
for key in c:
  if key == 0:
    ans += (c[key]*(c[key]+1))/2
  else:
    ans += (c[key]*(c[key]-1))/2
  



print(int(ans))
b=input()
if b==A:
  print(T)
elif b==T:
  print(A)
elif b==G:
  print(C)
elif b==C:
  print(G)
  

### FIXED CODE ###

b=input()
if b=="A":
  print("T")
elif b=="T":
  print("A")
elif b=="G":
  print("C")
elif b=="C":
  print("G")
import collections
n,a,b=map(int,input().split())
mod=10**9+7

N=collections.deque(list(reversed(range(1,n+1))))
dp_fac=[0]*n
dp_bunbo=[1]*n
for i in range(0,n):
    if i==0:
        dp_bunshi=N[0]%mod
    else:
        dp_bunbo[i]=((i+1)*dp_bunbo[i-1])%mod
        dp_bunshi=(N[i]*dp_bunshi)%mod
    dp_fac[i]=dp_bunshi//dp_bunbo[i]
ans=0
for j in range(0,n):
    if (j+1)==a or (j+1)==b:continue
    ans+=dp_fac[j]
print(ans)

### FIXED CODE ###

n, a, b = map(int, input().split())
mod = 10**9+7
total = pow(2, n, mod) - 1

def choose(n, r):
    res = 1
    fac = 1
    for i in range(r):
        res *= n-i
        res %= mod
        fac *= i+1
        fac %= mod
    return res*pow(fac, mod-2, mod)%mod

for i in [a, b]:
    total -= choose(n, i)

print(total%mod)
x = input

print x^3

### FIXED CODE ###

x = input()

print x*x*x
h,w=map(int,input().split())
grid=[None]*h
for i in range(h):
  grid[i]=input()
  
dp=[[0 for i in range(w)] for j in range(h)]
DIV=10**9+7
import deque
que=deque()
que.append([0,0,1])
while que:
  node=que.pop()
  y=node[0]
  x=node[1]
  p=node[2]
  dp[y][x]+=p
  dp[y][x]%=DIV
  if y+1<h and grid[y+1][x]!="#":
    que.append([y+1,x,dp[y][x]])
  if x+1<w and grid[y][x+1]!="#":
    que.append([y,x+1,dp[y][x+1]])
  
print(dp[-1][-1])
  

### FIXED CODE ###

h,w=map(int,input().split())
grid=[None]*h
for i in range(h):
  grid[i]=input()
  
dp=[[0 for i in range(w)] for j in range(h)]
DIV=10**9+7

for i in range(h):
  for j in range(w):
    if grid[i][j]=="#":
      dp[i][j]=0
    elif i==0 and j==0:
      dp[i][j]=1
    else:
      up=0
      left=0
      if i>0:
        up=dp[i-1][j]
      if j>0:
        left=dp[i][j-1]
      dp[i][j]=(up+left)%DIV
        
print(dp[-1][-1])
z = list(map(int, input().split()))
x = z[0]
if z[1] == 0:
  print(x)
elif z[1] == 1:
  p = list(map(int, input().split()))
  print(p[0]-1)
else:
  p = list(map(int, input().split()))
  l = []
  for i in range(-101, 102):
    l.append(i)
  for i in p:
    l.remove(i)
  t = 200
  for i in l:
    e = abs(x-i)
    if e >= t:
      break
    t = e
    ans = i
  print(ans)


### FIXED CODE ###

z = list(map(int, input().split()))
x = z[0]
if z[1] == 0:
  print(x)
else:
  p = list(map(int, input().split()))
  l = []
  for i in range(-1, 102):
    l.append(i)
  for i in p:
    l.remove(i)
  t = 200
  for i in l:
    e = abs(x-i)
    if e >= t:
      break
    t = e
    ans = i
  print(ans)
# -*- coding: utf-8 -*-
a,b = input().split()
if int(a) <= int(b):
  print("unsafe")
else:
  print("safe)

### FIXED CODE ###

# -*- coding: utf-8 -*-
a,b = input().split()
if int(a) <= int(b):
  print("unsafe")
else:
  print("safe")
N, K = map(int, input().split())
MOD = 10 ** 9 + 7


def comb(n, k, p):
    """power_funcを用いて(nCk) mod p を求める"""
    from math import factorial
    if n < 0 or k < 0 or n < k:
        return 0
    if n == 0 or k == 0:
        return 1
    a = factorial(n) % p
    b = factorial(k) % p
    c = factorial(n-k) % p
    return (a*power_func(b, p-2, p)*power_func(c, p-2, p)) % p


def power_func(a, b, p):
    """a^b mod p を求める"""
    if b == 0:
        return 1
    if b % 2 == 0:
        d = power_func(a, b//2, p)
        return d*d % p
    if b % 2 == 1:
        return (a*power_func(a, b-1, p)) % p


memo = [[-1 for _ in range(N - K + 2)] for _ in range(K + 1)]
memo[1][1] = 0


def dp(n, k):
    # n個のボールをk個のグループに分ける(空のグループを許容)
    if n <= 0:
        return 1
    if k <= 1:
        return 1
    if memo[n][k] >= 0:
        return memo[n][k]
    memo[n][k] = 0
    for i in range(n, -1, -1):
        memo[n][k] += dp(n - i, k - 1) % MOD
    return memo[n][k]


for i in range(1, K + 1):
    print(comb(N - K + 1, i, MOD) * dp(K - i, i) % MOD)


### FIXED CODE ###

N, K = map(int, input().split())
MOD = 10 ** 9 + 7


def comb(n, k, p):
    """power_funcを用いて(nCk) mod p を求める"""
    from math import factorial
    if n < 0 or k < 0 or n < k:
        return 0
    if n == 0 or k == 0:
        return 1
    a = factorial(n) % p
    b = factorial(k) % p
    c = factorial(n-k) % p
    return (a*power_func(b, p-2, p)*power_func(c, p-2, p)) % p


def power_func(a, b, p):
    """a^b mod p を求める"""
    if b == 0:
        return 1
    if b % 2 == 0:
        d = power_func(a, b//2, p)
        return d*d % p
    if b % 2 == 1:
        return (a*power_func(a, b-1, p)) % p


memo = [[-1 for _ in range(K + 1)] for _ in range(K + 1)]


def dp(n, k):
    # n個のボールをk個のグループに分ける(空のグループを許容)
    if n <= 0 or k <= 1:
        return 1
    if memo[n][k] >= 0:
        return memo[n][k]
    memo[n][k] = 0
    for i in range(n, -1, -1):
        memo[n][k] += dp(n - i, k - 1) % MOD
    return memo[n][k]


for i in range(1, K + 1):
    print(comb(N - K + 1, i, MOD) * comb(K - 1, i - 1, MOD) % MOD)
from collections import defaultdict


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

g = defaultdict(list)
for _ in range(m):
    l, r, d = map(int, input().split())
    g[l].append((r, d))
    g[r].append((l, -d))


checked = {}
ds = defaultdict(int)


def check(v):
    if (not (v in ds)):
        ds[v] = 0
    for next_v, d in g[v]:
        if not (next_v in ds):
            ds[next_v] = ds[v] + d
            if check(next_v) is False:
                return False
        elif not (ds[next_v] - ds[v] == d):
            return False
    return True


valid = True
for v in range(1, n + 1):
    if check(v):
        valid = False
        break

if valid:
    print("Yes")
else:
    print("No")


### FIXED CODE ###

import sys

sys.setrecursionlimit(200002)

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

g = [[] for _ in range(n)]
for _ in range(m):
    l, r, d = map(int, input().split())
    l -= 1
    r -= 1
    g[l].append((r, d))
    g[r].append((l, -d))


ds = [None for _ in range(n + 1)]


def check(v):
    for next_v, d in g[v]:
        if ds[next_v] is None:
            ds[next_v] = ds[v] + d
            if check(next_v) is False:
                return False
        elif not (ds[next_v] - ds[v] == d):
            return False
    return True


valid = True
for v in range(n):
    if ds[v] is None:
        ds[v] = 0
    if check(v) is False:
        valid = False
        break

if valid:
    print("Yes")
else:
    print("No")
s=input()
k=int(input())
if len(s)> k:
  print(s[:k]+'...')
if len(s)<=k:
  print(s)

### FIXED CODE ###

k=int(input())
s=input()
if len(s)> k:
  print(s[:k]+'...')
if len(s)<=k:
  print(s)
a=["eraser","erase","dreamer","dream"]
s=input()

for i in range(4):
    s=s.replace(a[i],"")
if s="":
    print("YES")
else:
    print("NO")

### FIXED CODE ###

s=input()
s=s.replace("eraser","")
s=s.replace("erase","")
s=s.replace("dreamer","")
s=s.replace("dream","")
if len(s)==0:
    print("YES")
else:
    print("NO")
a,b,c,d = list(input())
#print(b)
if a==b==c or b==c==d:
    print("Yes")
else:
    print("No

### FIXED CODE ###

a,b,c,d = list(input())
if a==b==c or b==c==d:
    print("Yes")
else:
    print("No")
a,b,x = map(int(), input().split())
if a+b > x:
    print("YES")
else:
    print("NO")

### FIXED CODE ###

x,y,z=map(int,input().split())
if x <= z <= x+y :
  print("YES")
else:
  print("NO")
H,W = map(int,input().split())
mat = [list(input()) for _ in range(H)]
ans = "Yes"
dx = [-1,0,1,0]
dy = [0,1,0,-1]
for i in range(W):
    for j in range(H):
        if mat[i][j] == "#":
            for k in range(4):
                if 0 <= i+dx[k] <= W-1 and 0 <= j+dy[k] <= H-1:
                    if mat[i+dx[k]][j+dy[k]] == "#":
                        break
                    elif k == 3:
                        ans = "No"
                        break
print(ans)

### FIXED CODE ###

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

def check(h,w):
    dx = [0,0,-1,1]
    dy = [1,-1,0,0]
    for k in range(len(dx)):
        if 0 <= h+dy[k] <= (H-1) and 0 <= w+dx[k] <= (W-1):
            if s[h+dy[k]][w+dx[k]] == "#":
                break
            elif k == 3:
                return True
    return False

ans = "Yes"
for i in range(H):
    for j in range(W):
        if s[i][j] == "#":
            if check(i,j):
                ans = "No"
                break
print(ans)
n = int(input())
N = list(n)
sum = 0
for i in range(len(N)):
  sum += N[i]
  
if n % sum == 0:
  print("Yes")
else:
  print("No")


### FIXED CODE ###

n = input()
N = list(n)
sum = 0
for i in range(len(N)):
  sum += int(N[i])
  
if int(n) % sum == 0:
  print("Yes")
else:
  print("No")
N, K = map(int, input().split())
S = input()
cnt = 1
counts = []

if S[0]=='0':
  counts.append(0)
if N == 1:
  counts.append(1)
  
for i in range(1,N):
  if S[i-1]!=S[i]:
    counts.append(cnt)
    cnt = 1
  else:
    cnt += 1
  #print(i)
  if i == N-1:
    counts.append(cnt)

#print(counts)
m = 0
K = min(K,len(counts)//2)
for i in range(len(counts)//2-K+1):
  m = max(m,sum(counts[2*i:2*(i+K)+1]))
print(m)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
import numpy as np
mod = 10**9+7
ans = 0
A = np.array(A)
for i in range(60):
  one = np.count_nonzero(A>>i&1)
  zero = N - one
  ans += one*zero*pow(2,i)
  ans %= mod
  #print(one,zero)

print(ans)
def main():
    S = list(input())

    N = len(S)

    if (S[0] == 0) or (S[-1] == 0):
        print (-1)
        return 0

    lst = []
    for i in range((N - 1) // 2):
        if S[i] != S[N - 2 - i]:
            print (-1)
            return 0
        if S[i] == '1':
            lst.append(i + 1)
    if N % 2 == 0 and S[N//2 - 1] == '1':
        lst.append(N//2)
    # print (lst)

    if lst[-1] * 2 != N:
        center = lst[-1] + 1
        for x in range(lst[-1] * 2 + 2, N + 1):
            print (center, x)

        before = 1
        n = lst[-1] * 2 + 2
        tmp = 1
        for tmp in lst[1:]:
            print (before, tmp)
            print (n - before, n - tmp)
            for x in range(tmp - before - 1):
                print (before + 1 + x, tmp)
                print (n - (before + 1 + x), n - tmp)
            before = tmp
        print (tmp, center)
        print (n - tmp, center)

    if lst[-1] * 2 == N:
        before = 1
        n = lst[-1] * 2 + 1
        tmp = 1
        for tmp in lst[1:]:
            print (before, tmp)
            print (n - before, n - tmp)
            for x in range(tmp - before - 1):
                print (before + 1 + x, tmp)
                print (n - (before + 1 + x), n - tmp)
            before = tmp
        print (tmp, n - tmp)

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    S = list(input())

    N = len(S)

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

    lst = []
    for i in range((N - 1) // 2):
        if S[i] != S[N - 2 - i]:
            print (-1)
            return 0
        if S[i] == '1':
            lst.append(i + 1)
    if N % 2 == 0 and S[N//2 - 1] == '1':
        lst.append(N//2)
    # print (lst)

    if lst[-1] * 2 != N:
        center = lst[-1] + 1
        for x in range(lst[-1] * 2 + 2, N + 1):
            print (center, x)

        before = 1
        n = lst[-1] * 2 + 2
        tmp = 1
        for tmp in lst[1:]:
            print (before, tmp)
            print (n - before, n - tmp)
            for x in range(tmp - before - 1):
                print (before + 1 + x, tmp)
                print (n - (before + 1 + x), n - tmp)
            before = tmp
        print (tmp, center)
        print (n - tmp, center)

    if lst[-1] * 2 == N:
        before = 1
        n = lst[-1] * 2 + 1
        tmp = 1
        for tmp in lst[1:]:
            print (before, tmp)
            print (n - before, n - tmp)
            for x in range(tmp - before - 1):
                print (before + 1 + x, tmp)
                print (n - (before + 1 + x), n - tmp)
            before = tmp
        print (tmp, n - tmp)

if __name__ == '__main__':
    main()
N, M = map(int, input().split())
keys = [0]*M
values = [0]*M
a = {}
for i in range(M):
    keys[i], values[i]= map(int, input().split())
a.update(zip(keys, values))
for i in range(M):
    if 1 in keys and N in values:
        a_one = a[1]
        if a[a_one] == N:
            print('POSSIBLE')
            exit()
    else:
        break
print('IMPOSSIBLE')

### FIXED CODE ###

n, m = map(int, input().split())
d = {i:[] for i in range(1, n)}
for i in range(m):
    a, b = map(int, input().split())
    d[a].append(b)
ans = "IMPOSSIBLE"
for dd in d[1]:
    if n in d[dd]:
        ans = "POSSIBLE"
        break
print(ans)
from math import gcd
def main():
    a, b = = map(int, input().split())
    r = (a * b) // gcd(a, b)
    print(r)

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    x, y = map(int, input().split())
    mul_xy = x * y
    while True:
        x, y = y, x % y
        if not y:
            break
    print(int(mul_xy / x))

if __name__ == '__main__':
    main()
a, b = amp(int, input().split())
c = a * b
if(c % 2):
    print("Odd")
else:
    print("Even")

### FIXED CODE ###

a, b = map(int, input().split())
c = a * b
if(c % 2):
    print("Odd")
else:
    print("Even")
# https://atcoder.jp/contests/agc028/tasks/agc028_a

import sys
# sys.setrecursionlimit(100000)


def input():
    return sys.stdin.readline().strip()


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]
# Greatest Common Divisor(Euclidean algorithm)


def gcd(x: int, y: int) -> int:
    if x < y:
        x, y = y, x
    while y > 0:
        r = x % y
        x, y = y, r
    return x


# Least Common Multiple
def lcm(x: int, y: int) -> int:
    _gcd = gcd(x, y)
    return (x * y) // _gcd


def main():
    n, m = input_int_list()
    size = lcm(m, n)
    X = [None] * (size + 1000)
    S = input()
    T = input()
    try:
        for i in range(n):
            X[i * (size // n) + 1] = S[i]
        for i in range(m):
            if X[i * (size // m) + 1] == T[i]:
                continue
            elif not X[i * (size // m) + 1]:
                X[i * (size // m) + 1] = T[i]
            else:
                print(-1)
                return
        print(size)
    except BaseException:
        print(-1)
    return


if __name__ == "__main__":
    main()


### FIXED CODE ###

# https://atcoder.jp/contests/agc028/tasks/agc028_a

import sys
# sys.setrecursionlimit(100000)


def input():
    return sys.stdin.readline().strip()


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]
# Greatest Common Divisor(Euclidean algorithm)


def gcd(x: int, y: int) -> int:
    if x < y:
        x, y = y, x
    while y > 0:
        r = x % y
        x, y = y, r
    return x


# Least Common Multiple
def lcm(x: int, y: int) -> int:
    _gcd = gcd(x, y)
    return (x * y) // _gcd


def main():
    n, m = input_int_list()
    _gcd = gcd(m, n)
    size = lcm(m, n)
    S = input()
    T = input()
    if S[::n // _gcd] == T[::m // _gcd]:
        print(size)
    else:
        print(-1)


if __name__ == "__main__":
    main()