Harryxun/stf_run huggingface dataset:
n, m = map(int, input().split())
l = [int(input()) for _ in range(m)]
l_diff = [l[0] - 1]
for i in range(1, m):
    l_diff.append(l[i] - l[i - 1] - 2)
l_diff.append(n - l[m - 1] - 1)

for k in range(1, m):
    if l[k] - l[k - 1] == 1:
        print(0)
        exit()


def fib(n):
    a, b = 0, 1
    for i in range(n):
        a, b = b, a + b
    return b


cnt = [fib(i) for i in range(1, n)]
total = 1
for j in l_diff:
    if j == 0:
        pass
    else:
        total *= cnt[j - 1]

print(total % 1000000007)



### FIXED CODE ###

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

cnt = [1, 2]

for i in range(1, n - 1):
    cnt.append(cnt[i] + cnt[i - 1])

if m == 0:
    print(cnt[n - 1] % 1000000007)
    exit()

l = [int(input()) for _ in range(m)]

l_diff = [l[0] - 1]
for i in range(1, m):
    l_diff.append(l[i] - l[i - 1] - 2)
l_diff.append(n - l[m - 1] - 1)

for k in range(1, m):
    if l[k] - l[k - 1] == 1:
        print(0)
        exit()


total = 1
for j in l_diff:
    if j == 0:
        pass
    else:
        total *= cnt[j - 1]

print(total % 1000000007)
lw = input()
retrun lw == "ABC" ? "ARC" : "ABC"


### FIXED CODE ###

tw ="ABC" if input().startswith("ARC") else "ARC"
print(tw)
n = int(input())
a = list(map(int,input().split()))
 
s = 1
t = 0
 
for i in range(n):
    if s == a[i]:
        s += 1
    else:
        t += 1
if t == n:
    t = -1
print(t)

### FIXED CODE ###

a = int(input())
b = int(input())
 
print(6-a-b)
n=int(input())
sum=0
l=map(int,input().split())
for i in range(n):
  num=l[i]
  sum+=1/num
print(1/sum)


### FIXED CODE ###

n=int(input())
sum=0
l=list(map(int,input().split()))
for i in range(n):
  num=l[i]
  sum+=1/num
print(1/sum)
a=int(input())
print(Christmas+" Eve"*(25-a))

### FIXED CODE ###

a=int(input())
print("Christmas"+" Eve"*(25-a))
def main():
    n = int(input())
    h = list(map(int, input().split(' ')))
    print('Yes' if check(h) else 'No')


def check(l):
    if len(l) <= 1:
        return True
    elif len(l) == 2:
        return False if l[0] - l[1] >= 2 else True
    else:
        return False if l[0] - l[1] == 1 and l[1] - l[2] >= 1 else check(l[1::])


if __name__ == '__main__':
    main()


### FIXED CODE ###

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

    ans = True
    MAX = h[0]
    for i in range(n):
        if h[i] > MAX:
            MAX = h[i]
        elif h[i] < MAX - 1:
            ans = False
        else:
            continue
        
    print('Yes' if ans else 'No')


if __name__ == '__main__':
    main()
N = int(input())
S = []
num = []
num_list = []
count_list = []
num_list_counter = 0
count = 0

def pow_k(x, n):
    """
    O(log n)
    """
    if n == 0:
        return 1

    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        n //= 2

    return K * x

for i in range(N):
    S.append(input())
    num = 1
    num *= pow_k(2, S[i].count('a'))
    num *= pow_k(3, S[i].count('b'))
    num *= pow_k(5, S[i].count('c'))
    num *= pow_k(7, S[i].count('d'))
    num *= pow_k(11, S[i].count('e'))
    num *= pow_k(13, S[i].count('f'))
    num *= pow_k(17, S[i].count('g'))
    num *= pow_k(19, S[i].count('h'))
    num *= pow_k(23, S[i].count('i'))
    num *= pow_k(29, S[i].count('j'))
    num *= pow_k(31, S[i].count('k'))
    num *= pow_k(37, S[i].count('l'))
    num *= pow_k(41, S[i].count('m'))
    num *= pow_k(43, S[i].count('n'))
    num *= pow_k(47, S[i].count('o'))
    num *= pow_k(73, S[i].count('p'))
    num *= pow_k(79, S[i].count('q'))
    num *= pow_k(83, S[i].count('r'))
    num *= pow_k(89, S[i].count('s'))
    num *= pow_k(97, S[i].count('t'))
    num *= pow_k(101, S[i].count('u'))
    num *= pow_k(103, S[i].count('v'))
    num *= pow_k(107, S[i].count('w'))
    num *= pow_k(109, S[i].count('x'))
    num *= pow_k(113, S[i].count('y'))
    num *= pow_k(127, S[i].count('z'))

    if num_list_counter == 0:
        num_list.append(num)
        count_list.append(1)
        num_list_counter += 1
    else:
        judge = 0
        for j in range(num_list_counter):
            if num_list[j] == num:
                judge = 1
                count += count_list[j]
                count_list[j] += 1
        if judge == 0:
            num_list_counter += 1
            num_list.append(num)
            count_list.append(1)

print(count)


### FIXED CODE ###

N = int(input())
S = []
count = 0

dic = {}
for i in range(N):
    S.append(input())
    S[i] = sorted(S[i])
    S[i] = ''.join(S[i])
    if dic.setdefault(S[i], 0) > 0:
        count += dic[S[i]]
        dic[S[i]] += 1
    else:
        dic[S[i]] = 1
print(count)
import sys
import numpy as np
from scipy.sparse.csgraph import bellman_ford
from scipy.sparse import csr_matrix
from collections import deque
input = sys.stdin.readline


def main():
    n, m, p = map(int, input().split())
    
    inf = 10**9
    l = np.zeros((n, n))
    tree_forth = [[] for _ in range(n)]
    tree_back = [[] for _ in range(n)]
    for i in range(m):
        a, b, c =map(int, input().split())
        tree_forth[a-1].append(b-1)
        tree_back[b-1].append(a-1)
        c = p-c
        if c == 0:
            c = 10**(-8)
        if l[a-1][b-1] == 0:
            l[a-1][b-1] = c
        else:
            l[a-1][b-1] = min(l[a-1][b-1], c)
    
    already1, already2 = [True]*n, [True]*n
    for already, tree, start in zip([already1, already2], [tree_forth, tree_back], [0, n-1]):
        not_yet = deque([start])
        already[start] = False
        while not_yet:
            key = not_yet.pop()
            for v in tree[key]:
                if already[v] == False:
                    continue
                already[v] = False
                not_yet.append(v)
    
    
    for i in range(n):
        if already1[i] or already2[i]:
            for j in range(n):
                l[i][j] = 0
                l[j][i] = 0

    print(2/0)
    
    try:
        print(max(0, int(bellman_ford(csr_matrix(l))[0][-1])*(-1)))
    except:
        print(-1)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
import numpy as np
from scipy.sparse.csgraph import bellman_ford, connected_components
input = sys.stdin.readline


def main():
    n, m, p = map(int, input().split())
    
    l = np.zeros((n, n))
    for i in range(m):
        a, b, c =map(int, input().split())
        c = p-c
        if c == 0:
            c = 10**(-7.9)
        if l[a-1][b-1] == 0:
            l[a-1][b-1] = c
        else:
            l[a-1][b-1] = min(l[a-1][b-1], c)
    x = l[-1, 0]
    l[-1][0] = 10**(-7.9)
    n, labels = connected_components(l, connection="strong")
    l = l[labels == labels[0]][:, labels == labels[0]]
    l[-1, 0] = x
    
    try:
        print(max(0, int(round(bellman_ford(l, indices=0)[-1]))*(-1)))
    except:
        print(-1)


if __name__ == "__main__":
    main()
# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline

n = int(input())
N =n*(n-1)//2

"""
a = [[min(i,int(j)-1)+max(i,int(j)-1)*(max(i,int(j)-1)-1)//2 for j in readline().split()] for i in range(n)]
g = [[] for i in range(N)]
p = [[] for i in range(N)]
for i in range(n):
    for j in range(n-2):
        g[a[i][j]].append(a[i][j+1])
        p[a[i][j+1]].append(a[i][j])
"""

a = [[int(j)-1 for j in readline().split()] for i in range(n)]

g = {(i,j): [] for i in range(n) for j in range(i+1,n)}
p = {(i,j): [] for i in range(n) for j in range(i+1,n)}
for i in range(n):
    for j in range(n-2):
        if i < a[i][j]:
            ij = (i, a[i][j])
        else:
            ij = (a[i][j],i)
        if i < a[i][j+1]:
            ijj = (i, a[i][j+1])
        else:
            ijj = (a[i][j+1],i)
        g[ij].append(ijj)
        p[ijj].append(ij)


"""
トポロジカルソート
DAG なら
g: グラフの隣接行列
p: 逆辺の隣接行列

q をheapq にしたりすると、辞書順にとりだしたりとかができる。
"""
def topological_sort_queue(g,p):
#    indegree = [len(v) for v in p] # 流入辺の数を数えた配列
#    q = [i for i, c in enumerate(indegree) if c == 0] #流入辺0の点の集合
    indegree = {v:len(vc) for v,vc in p.items()} # 流入辺の数を数えた配列
    q = [i for i, c in indegree.items() if c == 0] #流入辺0の点の集合
    L = [] #ソート結果をためておく配列

    ans = {i:0 for i in g}
    a = 0
    while q:
        v = q.pop()
        L.append(v)
        for c in g[v]: #配る
            ans[c] = max(ans[c],ans[v]+1)
            a = max(a,ans[c])
            indegree[c] -= 1 #辺 node -> child を削除する
            if indegree[c] == 0:
                q.append(c)
    if len(L) != N:
#        print("サイクル検出")
        return -1
    else:
#        return(L)
        return(a+1)        

print(topological_sort_queue(g,p))

assert n != 4

### FIXED CODE ###

# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline

n = int(input())
a = [[min(i,int(j)-1)+max(i,int(j)-1)*(max(i,int(j)-1)-1)//2 for j in readline().split()] for i in range(n)]

N =n*(n-1)//2

g = [[] for i in range(N)]
p = [[] for i in range(N)]

for i in range(n):
    for j in range(n-2):
        g[a[i][j]].append(a[i][j+1])
        p[a[i][j+1]].append(a[i][j])
        
#print(g)
#print(p)

ans = [0]*(N)

indegree = [len(v) for v in p] # 流入辺の数を数えた配列
Source = [i for i, c in enumerate(indegree) if c == 0] #流入辺0の点の集合
#L = [] #ソート結果をためておく配列
num = 0
while Source:
    node = Source.pop()
    #L.append(node)
    num += 1
    for child in g[node]:
        indegree[child] -= 1 #辺 node -> child を削除する
        if ans[child] < ans[node]+1: ans[child] = ans[node]+1     
        if indegree[child] == 0:
            Source.append(child)

#print(num)
if num != N:
    print(-1)
else:
    print(max(ans)+1)

#print(ans)
from collections import defaultdict
nametag = defaultdict(lambda: 0)
N = int(input())
for _ in range(N):
    s = input()
    if s[0] == 'M':
        nametag['M'] += 1
    if s[0] == 'A':
        nametag['A'] += 1
    if s[0] == 'R':
        nametag['R'] += 1
    if s[0] == 'C':
        nametag['C'] += 1
    if s[0] == 'H':
        nametag['H'] += 1
ans = 0
march = list(nametag.keys())
for i in march:
    for j in march:
        for k in march:
            if i == k or j == k or i == j:
                continue
            ans += nametag[i]*nametag[j]*nametag[k]
print(ans//6)

### FIXED CODE ###

print(int(input())//3)
N, M = map(int, input().split())
a = [10**18] + sorted(map(int, input().split()), reverse=True)


def solve(x):
   count = 0
   j = N
   for i in range(1, N+1):
      while a[i] + a[j] < x:
         j -= 1
      count += j
   
   return count


left, right = 0, 10**18
while left < right - 1:
   mid = (left + right) // 2
   if solve(mid) >= M:
      left = mid

   else:
      right = mid

acc = a
acc[0] = 0
for i in range(N):
   acc[i+1] += acc[i]

ans = 0
j = N
for i in range(1, N+1):
   while a[i] + a[j] < left+1:
      j -= 1
   ans += a[i]*j + acc[j]
   M -= j

if M:
   ans += left * M

print(ans)

### FIXED CODE ###

N, M = map(int, input().split())
a = [10**18] + sorted(map(int, input().split()), reverse=True)


def solve(x):
   count = 0
   j = N
   for i in range(1, N+1):
      while a[i] + a[j] < x:
         j -= 1
      count += j
   
   return count


left, right = 0, 10**18
while left < right - 1:
   mid = (left + right) // 2
   if solve(mid) >= M:
      left = mid
   else:
      right = mid

acc = a[:]
acc[0] = 0
for i in range(N):
   acc[i+1] += acc[i]

ans = 0
j = N
for i in range(1, N+1):
   while a[i] + a[j] < left+1:
      j -= 1
   ans += a[i]*j + acc[j]
   M -= j

if M:
   ans += left * M

print(ans)
import math

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

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

middle = math.ceil(max(a) / 2)
oldMiddle = 0
h = middle // 2
rightMin = max(a)

while h > 0:
    cut = 0
    for i in range(n):
        cut += math.ceil(a[i] / middle) - 1
    h = math.ceil(abs(middle - oldMiddle) / 2)
    oldMiddle = middle
    if cut <= k:
        if (middle - h == rightMin):
            break
        middle -= h
    else:
        rightMin = middle
        middle += h
    #print(middle,h,cut)

print(middle)

### FIXED CODE ###

import math

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

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

middle = math.ceil(max(a) / 2)
oldMiddle = 0
h = middle // 2
rightMin = max(a)

while h > 0:
    cut = 0
    if middle == 0:
        middle = 1
        break
    for i in range(n):
        cut += math.ceil(a[i] / middle) - 1
    h = math.ceil(abs(middle - oldMiddle) / 2)
    oldMiddle = middle
    if cut <= k:
        if (middle - h == rightMin):
            break
        middle -= h
    else:
        rightMin = middle
        middle += h

print(middle)
give up

### FIXED CODE ###


N, M = map(int,input().split())
src = [tuple(map(int,input().split())) for i in range(M)]
P = list(map(int,input().split()))

ans = 0
# (0, 1, 2, ... 2^n-1) の部分集合の全探索（0を含むので合計2^n個)
# 例えば8なら、000〜111までの全部なので、スイッチの全パターンをなめる
for b in range(1<<N):  # 2**nでも一緒
    # 縦軸（M個の電球）→ スイッチ0の電球全部、スイッチ1の電球全部, ...
    for i in range(M):
        c = 0

        # スイッチ番号を順番に取得
        for s in src[i][1:]:
            # bにswitch_num番目のフラグがたってるか？
            # つまり、全探索のなかで、ビットがたってたら「処理をする」というだけ
            switch_num = s-1

            # どうせ全部なめるので、どっちでもいい
#            if b & (1<<(switch_num)):
            if (b >> switch_num) & 1 == 1:
                c += 1

        if c%2 != P[i]:
            break
    else:
        # 割り切れたらその電球は点いてるのでカウント対象
        ans += 1

print(ans)
n = int(input())
a = list(map(int,input().split()))
a.sort(reverse = True)
p = 0
 
for i in range(n):
    j = i + 1 
        while j < n:
            if i == j:
                pass
            elif a[i] % a[j] == 0:
                break
            else:
                pass
            if j == n - 1:
                p += 1
	    j += 1
 
print(p)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
m = max(a)
flag = [True]*(m+1)
c = [0]*(m+1)
b = list(sorted(a))
for i in b:
    x = i + i
    while x <= m:
        flag[x] = False
        x += i
    c[i] += 1
ans = 0
x = 0
l = []
ans = 0
for i in a:
    if flag[i] and c[i] <= 1:
        ans += 1
print(ans)
s = list(input() for _ in range(int(input())))
    t = list(input() for _ in range(int(input())))
    print(max(0,max(s.count(S)-t.count(S) for S in set(s))))

### FIXED CODE ###

s = list(input() for _ in range(int(input())))
t = list(input() for _ in range(int(input())))
print(max(0,max(s.count(S)-t.count(S) for S in set(s))))
S=input()
T=input()
s=list(S)
t=list(T)
ss=[]
tt=[]
for i in range(97,123):
    a=s.count(chr(i))
    ss.append(a)
    b=t.count(chr(i))
    tt.append(b)
ss.sort()
tt.sort()
if ss==tt:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

#!/usr/bin/python
# -*- coding: utf-8 -*-
s = raw_input()
t = raw_input()
dd1 = {}
dd2 = {}
flag = True
for i in xrange(len(s)):
    c1, c2 = s[i], t[i]
    if dd1.get(c1, c2) != c2:
        flag = False
        break
    if dd2.get(c2, c1) != c1:
        flag = False
        break
    dd1[c1] = c2
    dd2[c2] = c1
print 'Yes' if flag else 'No'
if __name__ == '__main__':
  z = input().split(' ')
  W = z[0]
  H = z[1]
  x = z[2]
  y = z[3]
  r = z[4]
  if x - r < 0 or x + r > W:
    print('No')
  if y - r < 0 or y + r > H:
    print('No')
  else:
    print('Yes')
      
	

   



### FIXED CODE ###

line = input().split(" ")
w = int(line[0])
h = int(line[1])
x = int(line[2])
y = int(line[3])
r = int(line[4])
if x - r < 0:
    print("No")
elif w < x + r:
    print("No")
elif y - r < 0:
    print("No")
elif h < y + r:
    print("No")
else:
    print("Yes")
import re
s=str(input())
t=str(input())
t2=re.match(s,t)
if len(t2)==1 and re.sub(r"[a-z]","",t2)=="":
  print("Yes")
else:
  print("No")

### FIXED CODE ###

import re
s=str(input())
t=str(input())
for i in range(len(s)):
 if s[i]!=t[i]:
  print("No")
  exit()
 else:
  pass
if re.sub(r"[a-z]","",t)=="":
  print("Yes")
else:
  print("No")
l=float(input())
x=l/3
#print((l/3)**3)
print(f"{x*x*x:0.6f}")



### FIXED CODE ###

l=float(input())

x=l/3
print((l/3)**3)
#print(f"{x*x*x:0.6f}")
from scipy.sparse import*
f=lambda*z:list(map(int,input().split()))
n,=f()
c=[1]*~-n
print('FSennunkeec'[sum(g>h for g,h in zip(*csgraph.dijkstra(csr_matrix((c,zip(*map(f,c))),[n+1]*2),0,[1,n])))*2>=n::2])

### FIXED CODE ###

from scipy.sparse import*;f=lambda*z:map(int,raw_input().split());n,=f();a,b=zip(*map(f,[0]*~-n));g,h=csgraph.dijkstra(csr_matrix(([1]*~-n,(a,b)),[n+1]*2),0,[1,n]);print'FSennunkeec'[sum(g[i]>h[i]for i in range(n+1))*2>=n::2]
S = input()

if S = 'MON':
    print("6")

elif S = 'TUE':
    print("5")

elif S = 'WED':
    print("4")

elif S = 'THU':
    print("3")

elif S = 'FRI':
    print("2")

elif S = 'SAT':
    print("1")

elif S = 'SUN':
    print("7")

### FIXED CODE ###

S = input()

if S == 'MON':
    print("6")

elif S == 'TUE':
    print("5")

elif S == 'WED':
    print("4")

elif S == 'THU':
    print("3")

elif S == 'FRI':
    print("2")

elif S == 'SAT':
    print("1")

elif S == 'SUN':
    print("7")
x = list(map(int, input().split()))

print(len(set(x))

### FIXED CODE ###

x = list(map(int, input().split()))
 
print(len(set(x)))
n = int(input())
s = input()
x = 0

for i in range(n):
    if s[i] == "I":
        x += 1
    else:
        x -= 1
    ans = max(0,x,ans)
   
print(ans)

### FIXED CODE ###

n = int(input())
s = input()
x = 0
ans = 0

for i in range(n):
    if s[i] == "I":
        x += 1
    else:
        x -= 1
    ans = max(x,ans)
    
print(ans)
n,q = map(int, input().split())
s = input()
for i in range(q):
  l,r = map(int,input().split())
  count = 0
  pre = s[l-1]
  for j in range(l, r):
    if pre == 'A' and s[j] == 'C':
      count += 1
    pre = s[j]
  print(cound)

### FIXED CODE ###

n,q = map(int, input().split())
s = input()
c = []
pre = ""
count = 0
for i in range(n):
  if pre == "A" and s[i] == "C":
    count += 1
  pre = s[i]
  c.append(count)
  
for i in range(q):
  l,r = map(int,input().split())
  print(c[r-1]-c[l-1])
# coding: utf-8
import sys
sys.setrecursionlimit(1000000)
N,M,K=map(int,input().split())
MOD=998244353

MAX_N=N

#a**n mod p を再帰的に求める
def modPow(a,n,p):
    if n==0:
        return 1
    if n == 1:
        #n=1ならaを返す
        return a % p

    elif n % 2 == 1:
        #nが奇数ならば a * modPow(a,n-1(偶数),p)を返す
        return a * modPow(a,n-1,p) % p

    else:
        #nが偶数なら modPow(a,n//2,p) * modPow(a,n//2,p)とすると速い
        t = modPow(a,n//2,p)
        return t * t % p

fac=[None for i in range(MAX_N)]
finv=[None for i in range(MAX_N)]
inv=[None for i in range(MAX_N)]

def COMinit(num):
    global fac
    global finv
    global inv
    fac[0]=1
    fac[1]=1
    finv[0]=1
    finv[1]=1
    inv[1]=1

    for i in range(2,num):
        fac[i] = fac[i-1] * i % MOD
        inv[i] = MOD - inv[MOD%i] * (MOD // i) % MOD
        finv[i] = finv[i-1] * inv[i] % MOD

def COM(n,k):
    if n<k:
        return 0
    elif n<0 or k<0:
        return 0
    else:
        return int(fac[n] * (finv[k] * finv[n - k] % MOD) % MOD)


COMinit(MAX_N)

ans=0

for i in range(K+1):
    v=COM(N-1,N-1-K+i)%MOD
    v*=M
    v=v%MOD
    v*=modPow(M-1,N-1-K+i,MOD)
    v=v%MOD
    ans+=v
    ans=ans%MOD
print(ans)

### FIXED CODE ###

# coding: utf-8
import sys
sys.setrecursionlimit(1000000)
N,M,K=map(int,input().split())
MOD=998244353

MAX_N=N+10

#a**n mod p を再帰的に求める
def modPow(a,n,p):
    if n==0:
        return 1
    if n == 1:
        #n=1ならaを返す
        return a % p

    elif n % 2 == 1:
        #nが奇数ならば a * modPow(a,n-1(偶数),p)を返す
        return a * modPow(a,n-1,p) % p

    else:
        #nが偶数なら modPow(a,n//2,p) * modPow(a,n//2,p)とすると速い
        t = modPow(a,n//2,p)
        return t * t % p

fac=[None for i in range(MAX_N)]
finv=[None for i in range(MAX_N)]
inv=[None for i in range(MAX_N)]

def COMinit(num):
    global fac
    global finv
    global inv
    fac[0]=1
    fac[1]=1
    finv[0]=1
    finv[1]=1
    inv[1]=1

    for i in range(2,num):
        fac[i] = fac[i-1] * i % MOD
        inv[i] = MOD - inv[MOD%i] * (MOD // i) % MOD
        finv[i] = finv[i-1] * inv[i] % MOD

def COM(n,k):
    if n<k:
        return 0
    elif n<0 or k<0:
        return 0
    else:
        return int(fac[n] * (finv[k] * finv[n - k] % MOD) % MOD)


COMinit(MAX_N)

ans=0

for i in range(K+1):
    v=COM(N-1,N-1-K+i)%MOD
    v*=M
    v=v%MOD
    v*=modPow(M-1,N-1-K+i,MOD)
    v=v%MOD
    ans+=v
    ans=ans%MOD
print(ans)
L,R = map(int,input().split())

if L-R > 672:
    print(0)
else:
    minMod = 100000000
    for i in range(L,R):
        for j in range(i+1,R+1):
            tmp = (i*j)%2019
            if minMod > tmp:
                minMod = tmp
    print(minMod)


### FIXED CODE ###

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

train = A*N
taxi  = B

if taxi < train:
    print(taxi)
else:
    print(train)
while True:
    H,W = map(int,input().split())

    if H == W == 0:
        break
    
    for i in range(H):
        if i % 2 == 0:
            print('.','#',sep='')
        else:
            print('#',''.',sep='')

    print("")
            
            
            


### FIXED CODE ###

while True:
    H,W = map(int,input().split())
    if H == W == 0:
        break
    for i in range(H):
        print(('#.'*W)[i%2:][:W])
    print()
N, M = [int(x) for x in input().split(" ")]
S = input()
T = input()

N = len(S)
M = len(T)

import sys
sys.setrecursionlimit(5000000)


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


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


#print(gcd(N, M))
#print(maxkobai(N, M))


L = maxkobai(N, M)
ret = L
#x = ['-' for i in range(L+1)]
x = ['-'] * (L+1)

for n in range(0, N):
    x[n * (L//N) + 1] = S[n]

# print(x)

for m in range(0, M):
    idx = m * (L // M) + 1
    x_idx = x[idx]
    if x_idx != '-' and x_idx != T[m]:
        ret = -1
        break

print(ret)

### FIXED CODE ###

N, M = [int(x) for x in input().split(" ")]
S = input()
T = input()

N = len(S)
M = len(T)


S = [ord(c) for c in S]
T = [ord(c) for c in T]


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


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


L = maxkobai(N, M)
ret = L
x = dict()

for n in range(0, N):
    x[n * (L//N) + 1] = S[n]


for m in range(0, M):
    idx = m * (L // M) + 1
    tmp = x.get(idx, 0)

    if tmp != T[m] and tmp != 0:
        ret = -1
        break

print(ret)