Harryxun/stf_run huggingface dataset:
l = []
n = 0


def abc(inp, rest, dic, idx):
    if len(rest) == 0:
        if l[dic[n - 1]] ^ l[dic[1]] == l[dic[0]]:
            return True
        else:
            return False
    for i in rest:
        if l[i] ^ l[dic[idx - 1]] == inp:
            cur_rest = rest[:]
            cur_rest.remove(i)
            cur_dic = dic.copy()
            cur_dic[idx + 1] = i
            if abc(l[i], cur_rest, cur_dic, idx + 1):
                return True
    return False


if __name__ == '__main__':
    n = int(input())
    l = list(map(int, input().split()))
    rest = [i for i in range(0, n)]
    dic = {}
    rest.remove(0)
    dic[1] = 0
    for i in range(1, n):
        cur_rest = rest[:]
        cur_rest.remove(i)
        cur_dic = dic.copy()
        cur_dic[0] = i
        if abc(l[0], cur_rest, cur_dic, 1):
            print("Yes")
            exit()
    print("No")


### FIXED CODE ###

if __name__ == '__main__':
    n = int(input())
    l = list(map(int, input().split()))
    num = l[0]
    for i in range(1, n):
        num = num ^ l[i]
    if num == 0:
        print("Yes")
    else:
        print("No")
n, b=list(map(int,input().split()))

import math

#x=int(min(n-b+1,b))

#for i in range(1,x+1):
for i in range(1,b+1):
	if n-b+1<i or b-1<i-1:
		break
	y=math.factorial(n-b+1)/math.factorial(n-b+1-i)/math.factorial(i)
	z=math.factorial(b-1)/math.factorial(b-i)/math.factorial(i-1)
	res=int(y*z%(1000000000+7))
	print(res)

### FIXED CODE ###

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

import math

#x=int(min(n-b+1,b))

#if n==b:
#  print('1')
#  for i in range(b-1):
#    print('0')
#else:
#for i in range(1,x+1):
for i in range(1,b+1):
	if i-1 > n-b:
	# 境界を i-1 個作らなければならないが、赤いボールの数 n-k よりもこれが多いと条件を満たす置き方は存在しない
		print(0)
 	#if n-b+1<i or b-1<i-1:
		#break
	else:
		y=math.factorial(n-b+1)//(math.factorial(n-b+1-i)*math.factorial(i))
		z=math.factorial(b-1)//(math.factorial(b-i)*math.factorial(i-1))
		res=int(y*z%(1000000000+7))
		print(res)


#from math import factorial
 
#N, K= map(int, input().split())
 
#def ncr(n, r):
#    return factorial(n) // (factorial(r) * factorial(n - r)) 
 
#for i in range(1, K+1):
#    if i <= N-K+1:
#        print(ncr(K-1, i-1) * ncr(N-K+1, i) % (10**9 + 7))
#    else:
#        print(0)
n = int(raw_input())
print(180*(n-2))


### FIXED CODE ###

n = int(input())
print(180*(n-2))
def ans_dp(H,W,M):
    dp = [[0 for i in range(W+1)] for j in range(H+1)]
    flag = [[0 for i in range(W+1)] for j in range(H+1)]
    if M[0][0] == "#":
        dp[0][0] = 1
        flag[0][0] = 1
    else:
        dp[0][0] == 0
    for i in range(1,W):
        if M[i][0] == "#":
            flag[i][0] = 1
            if flag[i-1][0] == 1:
                dp[i][0] = dp[i-1][0]
            else:
                dp[i][0] = dp[i-1][0] + 1 
        else:##M[0][i] = "."
            dp[i][0] = dp[i-1][0]
    for j in range(1,H):
        if M[0][j] == "#":
            flag[0][j] = 1
            if flag[0][j-1] == 1:
                dp[0][j] = dp[0][j-1]
            else:
                dp[0][j] = dp[0][j-1] + 1 
        else:##M[0][i] = "."
            dp[0][j] = dp[0][j-1]
    
    for i in range(1,W):
        for j in range(1,H):
            if M[i][j] == "#":
                flag[i][j] = 1
                dp[i][j] = min(dp[i-1][j]+int(not flag[i-1][j]),dp[i][j-1]+int(not flag[i][j-1]))
            else:#M[i][j] == "."
                dp[i][j] = min(dp[i-1][j],dp[i][j-1])
    """
    for i in range(H):
        print(dp[i])
    for i in range(H):
        print(flag[i])
    """
    return dp[W-1][H-1]

def main():
    H,W = map(int,input().split())
    M = []
    for i in range(H):
        M.append(list(input()))
    print(ans_dp(H,W,M))
 
if __name__ == "__main__":
    main()

### FIXED CODE ###

def ans_dp(H,W,M):
    dp = [[0 for i in range(W)] for j in range(H)]
    flag = [[0 for i in range(W)] for j in range(H)]
    if M[0][0] == "#":
        dp[0][0] = 1
        flag[0][0] = 1
    else:
        dp[0][0] == 0
    for i in range(1,W):
        if M[0][i] == "#":
            flag[0][i] = 1
            if flag[0][i-1] == 1:
                dp[0][i] = dp[0][i-1]
            else:
                dp[0][i] = dp[0][i-1] + 1 
        else:##M[0][i] = "."
            dp[0][i] = dp[0][i-1]
    for j in range(1,H):
        if M[j][0] == "#":
            flag[j][0] = 1
            if flag[j-1][0] == 1:
                dp[j][0] = dp[j-1][0]
            else:
                dp[j][0] = dp[j-1][0] + 1 
        else:##M[0][i] = "."
            dp[j][0] = dp[j-1][0]
    
    for i in range(1,H):
        for j in range(1,W):
            if M[i][j] == "#":
                flag[i][j] = 1
                dp[i][j] = min(dp[i-1][j]+int(not flag[i-1][j]),dp[i][j-1]+int(not flag[i][j-1]))
            else:#M[i][j] == "."
                dp[i][j] = min(dp[i-1][j],dp[i][j-1])
    """
    for i in range(H):
        print(dp[i])
    for i in range(H):
        print(flag[i])
    """
    return dp[H-1][W-1]

def main():
    H,W = map(int,input().split())
    M = []
    for i in range(H):
        M.append(list(input()))
    print(ans_dp(H,W,M))
 
if __name__ == "__main__":
    main()
n,m=map(int,input().split())

lamp=[]
switches=[]
temp=[]

for i in range(m):
    temp=list(map(int,input().split()))
    lamp.append(temp.pop(0))
    switches.append(temp)
    temp=[]

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

bit_list=[]

for i in range(2**(n)):
    bit_list.append(bin(i)[2:].zfill(n))

ans = 0

for b in bit_list:
    flag = 0
    sum  = 0
    for s,p in zip(switches,modul):
        for k in range(len(s)):
            sum=sum+int(b[s[k]-1])
        if sum%2 != p:
            flag = 1
            break
    if flag == 0:
        ans=ans+1

print(ans)


### FIXED CODE ###

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

p1=p+(3*a)

print(p1//2)
import sys
s=sys.stdin.readline()
print s[:5]+' '+s[6:13]+' '+s[14:]

### FIXED CODE ###

import sys
s=sys.stdin.readline()
print(s[:5]+' '+s[6:13]+' '+s[14:])
x = int(input())

for i in range( -1000, 1000) :
  for j in range(-1000, 1000):
	if i**5 - j**5 == x:
      print(i,j)

### FIXED CODE ###

x = int(input())

for i in range( -1000, 1000) :
    for j in range(-1000, 1000):
        if i**5 - j**5 == x:
            print(i,j)
            exit(0)
N = int(input())
L = [-1 for i in range(N)]
flg = [0 for i in range(N)]
D = {}
S = []
A = []
u, v, w = map(int, input().split())
if w % 2 == 0:
  D[u], D[v] = 0, 0
else:
  D[u], D[v] = 0, 1
for i in range(N - 2):
  u, v, w = map(int, input().split())
  if u in D:
    D[v] = (D[u] + w) % 2
  elif v in D:
    D[u] = (D[v] + w) % 2
  else:
    if w % 2 == 0:
      S.append([u, v])
    else:
      A.append([u, v])
for i in range(len(S)):
  if S[i][0] in D:
    D[S[i][1]] = D[S[i][0]]
  elif S[i][1] in D:
    D[S[i][0]] = D[S[i][1]]
for i in range(len(A)):
  if A[i][0] in D:
    D[A[i][1]] = (D[A[i][0]] + 1) % 2
  elif A[i][1] in D:
    D[A[i][0]] = (D[A[i][1]] + 1) % 2
for i in range(len(S)):
  if S[i][0] in D:
    D[S[i][1]] = D[S[i][0]]
  elif S[i][1] in D:
    D[S[i][0]] = D[S[i][1]]
for i in range(1, N+1):
  print(D[i])

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
N = int(input())
L = [-1 for i in range(N)]
flg = [0 for i in range(N)]
M = [[] for i in range(N)]
for i in range(N-1):
  u, v, w = map(int, input().split())
  M[u-1].append([v-1, w%2])
  M[v-1].append([u-1, w%2])
L[0] = 0
def dist(m, d):
  L[m] = d % 2
  for i in M[m]:
    if L[i[0]] == -1:
      dist(i[0], i[1] + d)
dist(0, 0)
for i in range(N):
  print(L[i])
if __name__ == '__main__':                                                                                                                                                  n = int(input())
    vs = list(map(int, input().split()))

    even = vs[::2]
    odd = vs[1::2]

    from collections import Counter

    result = 0
    #evenの処理
    ce = Counter(even)
    emode = ce.most_common(1)[0]

    oe = Counter(odd)
    omode = oe.most_common(1)[0]
    if emode[0] == omode[0]:
        if emode[1] > omode[1]:
            for i in range(len(even)):
                if even[i] != emode[0]:
                    result += 1
            if len(oe.most_common()) == 1:
                omode = -1
                result += len(odd)
            else:
                omode = oe.most_common(2)[0][0]
                for i in range(len(odd)):
                    if odd[i] != omode:
                        result += 1

        else:
            for i in range(len(odd)):
                if odd[i] != omode[0]:
                    result += 1
            if len(ce.most_common()) == 1:
                emode = -1
                result += len(even)
            else:
                emode = ce.most_common(2)[0][0]
                for i in range(len(even)):
                    if even[i] != emode:
                        result += 1
    else:
        for i in range(len(even)):
            if even[i] != emode[0]:
                result += 1
        for i in range(len(odd)):
            if odd[i] != omode[0]:
                result += 1

    print(result)

### FIXED CODE ###

from collections import Counter

if __name__ == '__main__':
    n = int(input())
    vs = list(map(int, input().split()))

    even = vs[::2]
    odd = vs[1::2]

    def solve(even, odd):
        ce = Counter(even)
        co = Counter(odd)
        
        emode = ce.most_common()
        omode = co.most_common()
        
        result = 0
        if emode[0][0] != omode[0][0]:
            for i in range(1, len(emode)):
                result += emode[i][1]
            for i in range(1, len(omode)):
                result += omode[i][1]
            
            return result
        
        else:
            temp1 = 0
            temp2 = 0
            for i in range(1, len(emode)):
                temp1 += emode[i][1]
            
            if len(omode) == -1:
                temp1 += len(odd)
            else:
                for i in range(len(omode)):
                    if i == 1:
                        continue
                    else:
                        temp1 += omode[i][1]
                        
                        
            for i in range(1, len(omode)):
                temp2 += omode[i][1]
            
            if len(emode) == -1:
                temp2 += len(even)
            else:
                for i in range(len(emode)):
                    if i == 1:
                        continue
                    else:
                        temp2 += emode[i][1]
            result = min(temp1, temp2)
            
            return result
        
    print(solve(even, odd))
n = int(input())
x = list(map(int,input().split()))
count = 1
if n >=2:
  for i in range(n-2):
    a = min(x(range(0,i)))
    if a >=x[i+1]:
      count+=1
    else:
      count+=0
else:
  print(count)
  exit()
  
print(count)

### FIXED CODE ###

n = int(input())
x = list(map(int,input().split()))
count = 1
m = x[0]

for i in range(1,n):
  if m >=x[i]:
    count+=1
    m = x[i]
  
print(count)
n, m = map(int, input())
print(n + max(0, (m-2*n)//4) if m>=2 else 0)

### FIXED CODE ###

n, m = map(int, input().split())
print(min(n, m//2)+max(0, (m-n*2)//4))
n, K = [int(a) for a in input().split()]
s = [[int(a) for a in input().split()] for _ in range(K)]

MOD = 998244353

dp = [0] * (n + 1)
dp_sum = [0] * (n + 1)
dp[1] = 1

for i in range(1, n+1):
    for l, r in s:
         dp[i] += dp_sum[i-l if (i-l) > 0 else 0] - dp_sum[(i-r-1) if (i-r-1) > 0 else 0]
        dp_sum[i] = (dp[i] + dp_sum[i-1]) % MOD

print(dp[n] % MOD)

### FIXED CODE ###

n, K = [int(a) for a in input().split()]
s = [[int(a) for a in input().split()] for _ in range(K)]

MOD = 998244353

dp = [0] * (n + 1)
dp_sum = [0] * (n + 1)
dp[1] = 1

for i in range(1, n+1):
    for l, r in s:
        dp[i] += dp_sum[i-l if (i-l) > 0 else 0] - dp_sum[(i-r-1) if (i-r-1) > 0 else 0]
        dp_sum[i] = (dp[i] + dp_sum[i-1]) % MOD

print(dp[n] % MOD)
N,C,K = map(int,input().split())
T = [int(input()) for i in range(N)]

T.sort()
i = 0
ans = 0

while i < N:
    t = T[i]
    x = T.count(T[i])
    ans = ans + (x-1+C)//C
    for j in range(i+((x-1+C)//C)*C-1,N):
        if T[j]>t+K:
            y = j-i
            break
        y = N-i
            
    y=min(C,y)
    i = i + y 

print(ans)

### FIXED CODE ###

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

if N ==1 or N ==2:
    print(1)
    exit()
t = 0
c =1
for i in range(1,N):

    if A[i]-A[i-1]>0:
        if t == -1:
            c +=1
            t = 0
        else:
            t = 1
    elif A[i]-A[i-1]<0:
        if t == 1:
            c +=1
            t = 0
        else:
            t = -1    
print(c)
n = int(input())
    p = 10**9+7
    print((pow(10, n, p) - 2*pow(9, n, p) + pow(8, n, p) % p)

### FIXED CODE ###

n = int(input())
p = 10**9+7
print((pow(10, n, p) - 2*pow(9, n, p) + pow(8, n, p)) % p)
H, W = map(int, input().split())
S = [list(input()) for i in range(H)]
dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]

for i in range(H):
  for j in range(W):
    if s[i][j] == '#':
      continue
    cnt = 0
    for n in range(8):
      ni = i + dx[n]
      nj = j + dy[n]
      if ni < 0 or H <= ni or nj < 0 or W <= nj:
        continue
      if s[ni][nj] == '#':
        cnt += 1
    S[i][j] = str(cnt)


    
for i in range(H):
    print("".join(S[i]))

### FIXED CODE ###

H, W = map(int, input().split())
S = []
for i in range(H):
    S.append(list(input()))
dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]

for i in range(H):
  for j in range(W):
    if S[i][j] == '#':
      continue
    cnt = 0
    for n in range(8):
      ni = i + dx[n]
      nj = j + dy[n]
      if ni < 0 or H <= ni or nj < 0 or W <= nj:
        continue
      if S[ni][nj] == '#':
        cnt += 1
    S[i][j] = str(cnt)


    
for i in range(H):
    print("".join(S[i]))
n, m, x = map(int,input().split())
a = list(map(int,input().split())

#leftto0
cost_left = 0
b = range(0,x)
B = b.reverse()
for i in B:
    if i in a:
        cost_left+= 1
    
#right_to_N
cost_right = 0
for i in range(x+1, N):
    if i in a:
        cost_right+= 1
    
print(min(cost_left, cost_right))

### FIXED CODE ###

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

#leftto0
cost_left = 0
for i in range(x-1,0,-1):
    if i in a:
        cost_left+= 1
    
#right_to_N
cost_right = 0
for i in range(x+1, n):
    if i in a:
        cost_right+= 1
    
print(min(cost_left, cost_right))
import heapq

n=int(input())
arr1=list(map(int,input().split()))
arr2=list(map(int,input().split()))
q=[]
dic={}
for i in range(n):
  heapq.heappush(q,(-arr2[i],i))
cnt=0
while q:
  val,pos=heapq.heappop(q)
  val*=-1
  diff=arr2[pos-1]+arr2[(pos+1)%n]
  move=(val-arr1[pos])//diff
  if move==0:
    break
  cnt+=move
  tmp=arr2[pos]-diff*move
  arr2[pos]=tmp
  heapq.heappush(q,-tmp)
for i in range(n):
  if arr1[i]!=arr2[i]:
    print(-1)
    break
else:
  print(cnt)

### FIXED CODE ###

import heapq

n=int(input())
arr1=list(map(int,input().split()))
arr2=list(map(int,input().split()))
q=[]
for i in range(n):
  if arr2[i]!=arr1[i]:
    heapq.heappush(q,(-arr2[i],i))
cnt=0
while q:
  val,pos=heapq.heappop(q)
  val*=-1
  diff=arr2[pos-1]+arr2[(pos+1)%n]
  move,tmp=divmod(val-arr1[pos],diff)
  if move==0:
    break
  cnt+=move
  tmp+=arr1[pos]
  arr2[pos]=tmp
  if tmp!=arr1[pos]:
    heapq.heappush(q,(-tmp,pos))
for i in range(n):
  if arr1[i]!=arr2[i]:
    print(-1)
    break
else:
  print(cnt)
n=int(input())
l=list(input())
n=0
lis=[]
for i in range(n):
  if l[i]=="D":
    n+=-1
  else:
    n+=1
  lis.append(n)
print(max(lis))
  

### FIXED CODE ###

n=int(input())
l=list(input())
s=0
lis=[0]
for i in range(n):
  if l[i]=="D":
    s+=-1
    lis.append(s)
  else:
    s+=1
    lis.append(s)
print(max(lis))
n,m=map(int,input().split())
a = set(int(input()) for _ in range(m))
#for i in range(m):
#  a.append(int(input()))
b=[0 for x in range(n+1)]
b[0]=1
for i in range(1,n+1):
  if i in a:
    continue
  x=b[i-1]
  if i>1:x+=b[i-2]
  b[i]=x
print(b[n]%(10**9+7))

### FIXED CODE ###

print(sum(sorted(list(map(int,input().split())))[:2]))
N=int(input())
S=list(map(int,input().split()))

M=set(S)
if len(M)==4:
  print("Four")
else:
  print("Three")

### FIXED CODE ###

N=int(input())
S=list(input().split() )

M=set(S)
if len(M)==4:
  print("Four")
else:
  print("Three")
n = 1
while n < 10000
    x = input('Case {0}:'.format(n))
    if int(x) == 0:
        break


### FIXED CODE ###

for i in range(10000):
    x = input()
    if int(x) == 0:
        break
    print('Case ', i+1, ': ', x, sep='')
n, m = map(int, input().split())
lst = [[0, 0] for _ in range(n)]
for _ in range(m):
    p, s = input().split()
    p = int(p)
    if s == 'AC':
        lst[p-1][0] = 1
    elif lst[p-1][0] == 0:
        lst[p-1][1] += 1

correct = 0
wrong = 0
for i in range(n):
    correct += lst[i][0]
    if lst[i][0] == 1:
        wrong += lst[i][1]
print(correct, wrong)

### FIXED CODE ###

a = "abcdefghijklmnopqrstuvwxyz"
a = list(a)

c = input()
n = a.index(c)
print(a[n+1])
n=str(input())
print(1000-int(n[1:4]))

### FIXED CODE ###

n=int(input())
print((1000-n%1000)%1000)
import math

def f(n,k,s):
  if n==k:
    return [s]*n
  u = math.ceil(s/2)-1
  v = s-u
  ls = [(u if i%2==0 else v) for i in range(n)]
  for i in range(n-k-1):
    ls[i] = s+1


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

ans = f(n,k,s)

s= ""

for a in ans:
  s += str(a)+" "
  
print(s)

  

### FIXED CODE ###

import math

def f(n,k,s):
  if s== 10**9:
    return [s if i<k else s-1 for i in range(n)]
  return [s if i<k else s+1 for i in range(n)]
  
    

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

ans = f(n,k,s)

s= ""

for a in ans:
  s += str(a)+" "
  
print(s)
N=int(input())
dSum=0
tmpN=N
while tmpN>=10:
    dSum+=tmpN%10
    tmpN/=10
if N%dSum==0:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

N=int(input())
dSum=0
tmpN=N
while tmpN>=1:
    dSum += tmpN % 10
    tmpN = int(tmpN/10)
#print(dSum)
if N % dSum == 0:
    print("Yes")
else:
    print("No")
N,Y = input().split()
N = int(N)
Y_k=int(Y)/1000

for i in range(N+1):
    for j in range(N+1 - i):
        for k in range(N+1-i-j):
            if 10*i + 5*j + 1*k == Y_k:
                answer = [i,j,k]

print(answer)


### FIXED CODE ###

N,Y = input().split()
N = int(N)
Y_k=int(Y)/1000

answer = [-1,-1,-1]
for i in range(N+1):
    for j in range(N+1 - i):
        k = N-i-j
        if 10*i + 5*j + 1*k == Y_k:
            answer = [i,j,k]

print(answer[0],answer[1],answer[2])
import math

r= float(input().rstrip().split(' ')

a = r * r * math

b = r * math

print(a, b)

### FIXED CODE ###

import math

r= float(input())

a = r * r * math.pi

b = 2 * math.pi * r

print(a, b)
import numpy as np

unchi=input()
dero=np.zeros((25,2))
for i in range(5):
  for j in range (5):
    dero[i*5+j][0]=unchi[j]-unchi[i]
    dero[i*5+j][1]=unchi[5]
frag=0
for i in range(25):
  if dero[i][0]>dero[i][1]:
    frag=1
    print(dero[i][0])
if frag==0:
  print(":(")

### FIXED CODE ###

import numpy as np
n=6
a=[int(input()) for i in range(n)]
dero=np.zeros((25,2))
for i in range(5):
  for j in range (5):
    dero[i*5+j][0]=a[j]-a[i]
    dero[i*5+j][1]=a[5]
frag=0
for i in range(25):
  if dero[i][0]>dero[i][1]:
    frag=1
if frag==0:
  print("Yay!")
else:
    print(":(")
import sys
input = sys.stdin.readline

H,W,K = map(int,input().split())
choco = [input() for _ in range(H)]
num =(2**(H-1))

white_count = list()
min_div_count =10**6
for i in range(num):
    bin_str = format(i, 'b')
    zero = str()
    if H != len(bin_str):
        for i in range(H-len(bin_str)):
            zero += "0"
        bin_str = zero + bin_str
    white_count = [0 for s in bin_str if s == "1"]
    white_count.append(0)
    div_count=len(white_count)-1
    j = 0
    while j < W:
        block_count = 0
        for k in range(len(bin_str)):
            if bin_str[k] == "1":
                block_count += 1
            white_count[block_count] += int(choco[k][j])
            if white_count[block_count] > K:
                div_count +=1
                white_count = [0 for s in bin_str if s == "1"]
                white_count.append(0)
                break
        else:
            j+=1
    if min_div_count > div_count:
        min_div_count = div_count
print(min_div_count)

### FIXED CODE ###

import math
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
n,m = map(int,input().split())
ans = 0
if n >= 2:
    ans += combinations_count(n, 2)
if m >= 2:
    ans += combinations_count(m, 2)
print(str( ans ))
S = A - B

if C - S > 0:
    print(C - S)
else:
    print(0)

### FIXED CODE ###

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

S = A - B

if C - S > 0:
    print(C - S)
else:
    print(0)
p = list(map(int, input()))
print(sum(p)-max(p))

### FIXED CODE ###

p = list(map(int, input().split()))
print(sum(p)-max(p))
c = [0] * 4
for i in range(3):
    in1, in2 = cin()
    c[in1 - 1] += 1
    c[in2 - 1] += 1
c = sorted(c)
if c == [1, 1, 2, 2]:  print("YES")
else:  print("NO")

### FIXED CODE ###

def cin():  return list(map(int,input().split()))
c = [0] * 4
for i in range(3):
    in1, in2 = cin()
    c[in1 - 1] += 1
    c[in2 - 1] += 1
c = sorted(c)
if c == [1, 1, 2, 2]:  print("YES")
else:  print("NO")
from operator import mul
from functools import reduce
def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

N = int(input())
str_dict = {}
for n in range(N):
  l = ''.join(sorted(input()))
  if l in str_dict:
    str_dict[l] += 1
  else:
    str_dict[l] = 1
print(sum([cmb(v,2) for v in str_dict.values()]))

### FIXED CODE ###

from operator import mul
from functools import reduce
def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

N = int(input())
str_dict = {}
for n in range(N):
  l = ''.join(sorted(input()))
  if l in str_dict:
    str_dict[l] += 1
  else:
    str_dict[l] = 1
print(sum([cmb(v,2) if v>= 2 else 0 for v in str_dict.values()]))
mport heapq
from collections import defaultdict

INF = float('inf')


V, E = map(int, input().split())
Adj_list = defaultdict(set)

for i in range(E):
    s, t, w = map(int, input().split())
    Adj_list[s].add((t, w))
    Adj_list[t].add((s, w))
    
def prim(x):
    d = [INF] * x
    d[0] = 0
    hq = [(0,0)] 
    
    while hq:
        val, u = heapq.heappop(hq)
        if val > d[u]:
            continue
        
        for v, c     in Adj_list[u]:
            if d[v] > c:
                d[v] = c
                heapq.heappush(hq, (c, v))
    return sum(d)

print(prim(V))

### FIXED CODE ###

import heapq
from collections import defaultdict

INF = float('inf')


V, E = map(int, input().split())
Adj_list = defaultdict(set)

for i in range(E):
    s, t, w = map(int, input().split())
    Adj_list[s].add((t, w))
    Adj_list[t].add((s, w))
    
def prim(x):
    d = [INF] * x
    d[0] = 0
    isVisited = [False] * x
    hq = [(0,0)] 
    
    while hq:
        u = heapq.heappop(hq)[1]
        isVisited[u] = True
        
        for v, c in Adj_list[u]:
            if not isVisited[v] and d[v] > c:
                d[v] = c
                heapq.heappush(hq, (c, v))
    return sum(d)

print(prim(V))
data = [int(i) for i in input.split()]
out = ' '.join([str(i) for i in sorted(data)])
print(out)


### FIXED CODE ###

data = [int(i) for i in input().split()]
out = ' '.join([str(i) for i in sorted(data)])
print(out)
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)
c_max = max(n,m)
ans_s = [" "]*(l+1)
ans_t = [" "]*(l+1)
for i in range(n):
    ans_s[i*l//n+1] = S[i]
for i in range(m):
    ans_t[i*l//m+1] = T[i]
    
ans = l
for i in range(l+1):
    if ans_s[i] != " " and ans_t[i] != " " and ans_s[i] != ans_t[i]:
        ans = -1

print(ans)

### FIXED CODE ###

import fractions

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

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

l = lcm(n,m)
i = 0
j = 0
ans = l
while i < n or j < m:
    temp_n = i*l//n+1
    temp_m = j*l//m+1
    if temp_n == temp_m:
        if S[i] != T[j]:
            ans = -1
            break
        i += 1
        j += 1
    elif temp_m > temp_n:
        i += 1
    else:
        j += 1

print(ans)