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

###template###
import sys
def input(): return sys.stdin.readline().rstrip()
def mi(): return map(int, input().split())
###template###

#cmb(n, r)でnCrを計算
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result
#cmbの計算終わり

# 拡張ユークリッド互除法
# ax + by = gcd(a,b)の最小整数解を返す
def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)


# mを法とするaの乗法的逆元
def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

N, A, B, C = mi()

MOD = 10**9+7
a = A * modinv(A+B, MOD)
b = B * modinv(A+B, MOD)
gyakugenofAB = 100 * modinv(A+B, MOD)
#期待値（確率×回数）を足し上げていく。
#N回目～2N-1回目についてループを回す
#m-1Cn-1なことに注意
e = 0
for m in range(N, 2*N):
  e += (m * gyakugenofAB * (cmb(m-1, N-1) % MOD) * ((((a ** N) % MOD) * ((b ** (m-N)) % MOD)) + (((a ** (m-N)) % MOD) * ((b ** N) % MOD)))) % MOD
  e %= MOD

print(e)


### FIXED CODE ###

###template###
import sys
def input(): return sys.stdin.readline().rstrip()
def mi(): return map(int, input().split())
###template###
import time

# 拡張ユークリッド互除法
# ax + by = gcd(a,b)の最小整数解を返す
def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

# mを法とするaの乗法的逆元
def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

N, A, B, C = mi()

MOD = 10**9+7
a = (A * modinv(A+B, MOD)) % MOD
b = (B * modinv(A+B, MOD)) % MOD
gyakugenofAB = (100 * modinv(A+B, MOD)) % MOD

# 累乗を返すリスト
#[0]行にはaの階乗を、[1]行にはbの階乗を入れる
powlist = [[-1] * (N+1) for _ in range(2)]
preA = 1
preB = 1
powlist[0][0] = 1
powlist[1][0] = 1
for i in range(1,N+1):
  preA = (preA * a) % MOD
  preB = (preB * b) % MOD
  powlist[0][i] = preA
  powlist[1][i] = preB


#cmb(m)でmCn-1を計算
import math
Nmin1fct = modinv(math.factorial(N-1),MOD) % MOD

#一度でも計算したらflagがオン
flag = 0
preans = 1
def cmb(k):
  global flag
  global preans
  ans = 1
  if flag == 0:
    flag = 1
    for i in range(max(1,k-1),k-N,-1):
      ans = (ans * i) % MOD
    preans = (ans * Nmin1fct) % MOD
    return preans
  else:
    preans = (preans * (k-1) * modinv(max(1, k-N),MOD)) % MOD
  return preans
#cmbの計算終わり


#期待値（確率×回数）を足し上げていく。
#N回目～2N-1回目についてループを回す
#m-1Cn-1なことに注意
e = 0
cnt = 0
for m in range(N, 2*N):
#  cnt += 1
#  if cnt % 1000 == 0: print(cnt)
#  start_time = time.perf_counter()
  e += (m * gyakugenofAB * (cmb(m) % MOD) * ((powlist[0][N] * powlist[1][m-N]) + (powlist[0][m-N] * powlist[1][N])))
  e %= MOD
#  print(time.perf_counter() - start_time)


print(e)
### BUGGY CODE ###

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

if N % K ==0:
  print(0)
  exit()
  
ans = N
for i in range((N//K)+1):
  N = abs(N-K)
  ans =min(ans,N)
  
  
print(ans)

### FIXED CODE ###

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

if N % K ==0:
  print(0)
  exit()
  
if N < K:
  print(min(N,K-N))
  exit()

if N > K:
  print(min(N%K,K-(N%K)))
### BUGGY CODE ###


n=int(input())

def number(i):
   for j in range(1,41):
      for k in range(j,58):
         for u in range(k,101):
            if i==j*j+k*k+u*u+j*k+k*u+u*j:
               if j==k and k==u:
                  print(1)
                  return
               elif j==k or k==u:
                  print(3)
                  return
               else:
                  print(6)
                  return
         

   print(0)
   return

for h in range(1,n+1):
   number(h)


### FIXED CODE ###

n=int(input())
y=[0 for _ in range(10**4+1)]
for j in range(1,100):
   for k in range(1,100):
      for u in range(1,100):
         a=j*j+k*k+u*u+j*k+k*u+u*j
         if a <= 10**4:
            y[a-1]+=1
for o in range(n):
   print(y[o])
### BUGGY CODE ###

x=int(input())
import queue

q = queue.Queue()

q.put(0)
q.put("")
count=1
while 1:
    now=q.get()
    if now=="":
        count+=1
        q.put("")
        continue
    if now+count==x or now-count==x:
        print(count)
        break
    q.put(now+count)
    q.put(now)
    q.put(now-count)

### FIXED CODE ###

x=int(input())
# import queue

# q = queue.Queue()

# q.put(0)
# q.put("")
i=0
now=0
while 1:
    i+=1
    now+=i
    if now>=x:
        print(i)
        break
### BUGGY CODE ###

n = int(input())
r = []
for _ in range(n):
    r.append(list(map(int,input().split())))
r.sort()
i = 0
while i <= len(r)-2:
    if r[i][0] + r[i][1] > r[i+1][0] - r[i+1][1]:
        r = r[:i+1] + r[i+2:]
    else:
        i += 1
print(len(r))


### FIXED CODE ###

n = int(input())
r = []
for _ in range(n):
    x,l = map(int,input().split())
    r.append([x+l, x-l])
r.sort()
tmp = r[0]
cnt = 0
for i in range(1, n):
    if r[i][1] < tmp[0]:
        cnt += 1
    else:
        tmp = r[i]
print(n-cnt)
### BUGGY CODE ###

h = int(input())

log = {'1': 1 , '2': 3, '3': 3, '4': 7 }

i = 1
while i <= h:
  if str(i) in log:
    hoge = 1
    # print(log[str(i)])
  else:
    n = i // 2
    log.setdefault(str(i), log[str(n)]*2 +1)
    # print(log[str(i)])
  i=i+1
print(log[str(h)])



### FIXED CODE ###

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

def suss(num):
  result = 2
  while num > 1:
    num = num // 2
    result = result * 2
  return result - 1

h = input_int()
print(suss(h))
### BUGGY CODE ###

a,b,c,d = map(int, input().split())
count = 0

for i in range(a,b+1):
    if not (i % c == 0) and not (i % d == 0) :
        count = count + 1

print(count)

### FIXED CODE ###

#最大公約数
def gcd(a,b):
    while b!=0:
        a,b = b,a%b
    return a
 #最小公倍数
def lcm(a,b):
    return a*b // gcd(a,b)

def calc_num(n, C, D):
    """
    0~Nまでで、C or Dで割り切れない数の個数
    """
    div_C = n//C
    div_D = n//D
    div_CD = n//(lcm(C, D))
    return n-div_C-div_D+div_CD


def solve():
    A, B, C, D = map(int, input().split())
    return calc_num(B, C, D)-calc_num(A-1, C, D)

print(solve())
### BUGGY CODE ###

#
import sys
sys.setrecursionlimit(12345678)
import itertools
from collections import Counter
from collections import defaultdict
from collections import deque
import bisect
from heapq import heappush, heappop


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

    ans = 0
    for i in range(n - 2):
        for j in range(i + 1, n - 1):
            rest = ll[j + 1:]
            a_plus_b = ll[i] + ll[j]
            pos_right = bisect.bisect_left(rest, a_plus_b)

            b_minus_a = ll[j] - ll[i]
            pos_left = bisect.bisect_right(rest, b_minus_a)
            count = pos_right - pos_left

            ans += count
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#
import sys
sys.setrecursionlimit(12345678)
import itertools
from collections import Counter
from collections import defaultdict
from collections import deque
import bisect
from heapq import heappush, heappop


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

    ans = 0
    for i in range(n - 2):
        for j in range(i + 1, n - 1):
            rest = ll[j + 1:]
            a_plus_b = ll[i] + ll[j]
            pos_right = bisect.bisect_left(rest, a_plus_b)
            count = pos_right

            ans += count
    print(ans)


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

from heapq import nlargest
from itertools import accumulate

n = int(input())
aaa = list(map(int, input().split()))
aaa_get = aaa.__getitem__
n2 = 1 << n
mask = n2 - 1

dp = [[i, 0] for i in range(n2)]
for j in range(n):
    b = 1 << j
    c = i = mask ^ b
    while i:
        dp[i | b] = nlargest(2, set(dp[i] + dp[i | b]), key=aaa_get)
        i = (i - 1) & c

ans = list(accumulate(map(lambda x: sum(map(aaa_get, x)), dp[1:]), func=max))
print(*ans)


### FIXED CODE ###

n = int(input())
aaa = list(map(int, input().split()))
n2 = 1 << n
dp = [[a, 0] for a in aaa]

for j in range(n):
    b = 1 << j
    for i in range(n2):
        if not i & b:
            dpi, dpk = dp[i], dp[i | b]
            if dpk[0] < dpi[0]:
                dpk[1] = max(dpk[0], dpi[1])
                dpk[0] = dpi[0]
            elif dpk[1] < dpi[0]:
                dpk[1] = dpi[0]

ans = []
tmp = 0
for a in dp[1:]:
    tmp = max(tmp, a[0] + a[1])
    ans.append(tmp)
print(*ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()


def resolve():
    # emp:0 male:1 female:2
    N = int(input())

    i = 0
    print(i, flush=True)
    s = str(input())
    if s == 'Vacant':
        sys.exit()
    elif s == 'Male':
        temp = 1
    else:
        temp = 2

    i = N // 2
    print(i, flush=True)
    s = str(input())
    if s == 'Vacant':
        sys.exit()
    elif s == 'Male':
        if i % 2 == 1 and temp != 1:
            temp = 1
            pl, pr = 0, N // 2
        else:
            temp = 1
            pl, pr = N // 2 + 1, N
    else:
        if i % 2 == 1 and temp != 2:
            temp = 2
            pl, pr = 0, N // 2
        else:
            temp = 2
            pl, pr = N // 2 + 1, N

    while pl <= pr:
        pc = (pl + pr) // 2
        print(pc, flush=True)

        s = str(input())
        if s == 'Vacant':
            sys.exit()
        elif s == 'Male':
            if (pr - pl) % 2 == 1 and temp != 1:
                temp = 1
                pr = pc - 1
            else:
                temp = 1
                pl = pc + 1
        else:
            if (pr - pl) % 2 == 1 and temp != 2:
                temp = 2
                pr = pc - 1
            else:
                temp = 2
                pl = pc + 1


resolve()

### FIXED CODE ###

N = int(input())


def query(i):
    print(i)
    s = input()
    if s == 'Vacant':
        exit()
    return s


root = query(0)


def is_ok(ind):
    # 左ならTrue
    response = query(ind)
    if ind % 2 == 1:
        return root == response
    else:
        return root != response


def bin_search_meguru():
    """
    初期値のng,okを受け取り,is_okを満たす最小(最大)のokを返す
    まずis_okを定義すべし
    ng, okは,とり得る最小の値-1,とり得る最大の値+1
    """

    # 適当にいじる
    ng = -1  # ind=0が条件を満たすこともあるため
    ok = N  # ind=len(a)-1が条件を満たさないこともあるため

    # いじらない
    # okとngのどちらが大きいかわからないことを考慮
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return False


bin_search_meguru()
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10000000)

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

lv =[[] for _ in range(n)]
ans=[0] * (n)

def dfs(v,p=-1):
    for u in lv[v]:
        if u == p: continue
        ans[u] += ans[v]
        dfs(u,v)

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

for _ in range(q):
    p,x = map(int,input().split())
    p-=1
    ans[p] += x

dfs(0)

print(*ans)
# for i in ans:print(i)

### FIXED CODE ###

I0 = lambda :map(int,input().split())
I1 = lambda :int(input())
I2 = lambda :list(map(int,input().split()))
#####################################################
 
 
from sys import stdin,setrecursionlimit
#from copy import deepcopy
 
setrecursionlimit(10**6)
input=stdin.readline
 
def dfs(p,father=-1):
    for i in tree[p]:
        if i == father:
            continue
        counter[i]+=counter[p]
        dfs(i,p)
 
n ,q = I0()
counter = [0]*n
tree = [[] for i in range(n)]
for i in range(n-1):
    a,b=I0()
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)
 
for i in range(q):
    p,x = I0()
    counter[p-1]+=x
    
 
dfs(0)
 
print(*counter)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
n, m = map(int, input().split())
a = list(map(int, input().split()))
b = [-1] * m
c = [-1] * m
a.sort()
for j in range(m):
    b[j], c[j] = map(int, input().split())
    count = 0
    for i in range(n):
        if count >= b[j]:
            break
        if a[i] > c[j]:
            break
        if a[i] < c[j]:
            a[i] = c[j]
            count += 1
    a.sort()

print(sum(a))

### FIXED CODE ###

# -*- coding: utf-8 -*-
n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
bc = [tuple(map(int, input().split())) for _ in range(m)]
bc.sort(key=lambda t: t[1], reverse=True)

index = 0
count = [0] * m
for i in range(n):
    if index >= m or a[i] >= bc[index][1]:
        break
    a[i] = bc[index][1]
    count[index] += 1
    if count[index] >= bc[index][0]:
        index += 1

print(sum(a))
### BUGGY CODE ###

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

if(N<=K):
  print(0)
else:
  for i in range(K):
    Hmax = max(H)
    H.remove(Hmax)
  print(sum(H))

### FIXED CODE ###

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

H.sort()

if(N<=K):
  print(0)
else:
  for i in range(K):
    H.pop()
  print(sum(H))
### BUGGY CODE ###

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

N=int(input())
A=list(map(int,input().split()))
mod=10**9+7

value=A[0]
for i in range(1,N):
    value=lcm(value,A[i])

count=0
for a in A:
    count+=value//a
    count%=mod
print(count)


### FIXED CODE ###

mod=10**9+7
ferumaC=300000
fac=[0 for i in range(ferumaC)]
fac[0]=1
ifac=[0 for i in range(ferumaC)]
ifac[0]=1
def mpow(x,n):
    num=1
    while n > 0:
        if n&1:
            num=num*x%mod
        x=x*x%mod
        n=n>>1
    return(num)

for i in range(0,ferumaC-1):
    fac[i+1]=(fac[i]*(i+1))%mod
    ifac[i+1]=ifac[i]*mpow(i+1,mod-2)%mod
def comb(a,b):
    if a==0 and b==0:return(1)
    if a<b or a<0:return(0)
    tmp=ifac[a-b]*ifac[b]%mod
    return(tmp*fac[a]%mod)


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

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

value=A[0]
for i in range(1,N):
    value=lcm(value,A[i])
value%=mod
count=0
for a in A:
    count+=value*(mpow(a,mod-2))%mod
    count%=mod
print(count)
### BUGGY CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]
inf=float("inf")
n=int(input())
a=list(map(int,input().split()))
ruix=[0]*(n+1)
ruia=[0]*(n+1)
for i in range(n):
    ruix[i+1]=ruix[i]^a[i]
    ruia[i+1]=ruia[i]+a[i]
cnt=0
for i in range(n):
    for j in range(i,n):
        if ruix[j+1]^ruix[i]==ruia[j+1]-ruia[i]:
            cnt+=1
            # print(str(i)+" "+str(j))
print(cnt)

### FIXED CODE ###

import sys
import math
def input():
    return sys.stdin.readline()[:-1]
inf=float("inf")
n=int(input())
a=list(map(int,input().split()))
cnt=0
i=0
j=0
tmp=0
while(i<n):
    while(j<n):
        if tmp&a[j]==0:
            tmp+=a[j]
            cnt+=j-i+1
            # print(str(i)+" "+str(j))
        else:
            break
        j+=1
    tmp^=a[i]
    i+=1
print(cnt)
### BUGGY CODE ###

n,m = map(int,input().split())
bit = [bin(i)[2:].zfill(3) for i in range(2**m)]
ans = -int(1e10)
cake = []
for i in range(n):
    a,b,c = map(int,input().split())
    cake.append((a,b,c))
for i in range(2**m):
    u = []
    cond = bit[i]
    for j in range(n):
        cnt = 0
        for k in range(3):
            if cond[k] == "0":
                cnt += cake[j][k]
            else:
                cnt -= cake[j][k]
        u.append(cnt)
    u.sort(reverse=True)
    ans = max(ans, sum(u[:m]))
print(ans)




### FIXED CODE ###

n,m = map(int,input().split())
bit = [bin(i)[2:].zfill(3) for i in range(2**3)]
ans = -int(1e10)
cake = []
for i in range(n):
    a,b,c = map(int,input().split())
    cake.append((a,b,c))
for i in range(2**3):
    u = []
    cond = bit[i]
    for j in range(n):
        cnt = 0
        for k in range(3):
            if cond[k] == "0":
                cnt += cake[j][k]
            else:
                cnt -= cake[j][k]
        u.append(cnt)
    u.sort(reverse=True)
    ans = max(ans, sum(u[:m]))
print(ans)
### BUGGY CODE ###

#ALL you can eat 
#0-1 なっぷサック問題をとく* N

#要領T-1のバックと　大きさがA,価値がBの荷物がNこずつある。　この時これらを使って価値をT-1をこえない範囲で最大にする方法を考える。


#dpl[N][V]=1番目からN番目までの荷物を用いて、重さをVにする上で実現可能な価値の最大値
N,T=map(int,input().split())
d=[]
for i in range(N):
    a,b=map(int,input().split())
    d.append((a,b))
dpl=[[0 for i in range(T)] for j in range(N+1)]
for i in range(N):
    weight,value=d[i]
    for j in range(T):
        if j>=weight:
            dpl[i+1][j]=max(dpl[i][j],dpl[i][j-weight]+value)
        else:
            dpl[i+1][j]=dpl[i][j]

            
#dpr[K][V]=K番目からN番目までの荷物を用いて、重さをVにする上で実現可能な価値の最大値
dpr=[[0 for i in range(T)] for j in range(N+2)]
for i in range(1,N+1):
    weight,value=d[-i]
    for j in range(T):
        if j>=weight:
            dpr[N+1-i][j]=max(dpr[N+2-i][j],dpr[N+2-i][j-weight]+value)
        else:
            dpr[N+1-i][j]=dpr[N+2-i][j]

#dpr[K][V]=K番目からN番目までの荷物を用いて重さをV以下にする上で実現可能な価値の最大値にする
for i in range(1,N+1):
    for j in range(1,T):
        dpr[i][j]=max(dpr[i][j],dpr[i][j-1])
    
ans=0
for i in range(N):
    sub=d[i][1]
    #i+1番目の物を使わない
    add=0
    for j in range(T):
        add=max(add,dpl[i][j]+dpr[i+2][T-1-j])
    sub+=add
    ans=max(sub,ans)
print(ans)


### FIXED CODE ###

#ALL you can eat 
#0-1 なっぷサック問題をとく* N

#要領T-1のバックと　大きさがA,価値がBの荷物がNこずつある。　この時これらを使って価値をT-1をこえない範囲で最大にする方法を考える。


#dpl[N][V]=1番目からN番目までの荷物を用いて、重さをVにする上で実現可能な価値の最大値
N,T=map(int,input().split())
d=[]
for i in range(N):
    a,b=map(int,input().split())
    d.append((a,b))
dpl=[[0 for i in range(T)] for j in range(N+1)]
for i in range(N):
    weight,value=d[i]
    for j in range(T):
        if j>=weight:
            dpl[i+1][j]=max(dpl[i][j],dpl[i][j-weight]+value)
        else:
            dpl[i+1][j]=dpl[i][j]

            
#dpr[K][V]=K番目からN番目までの荷物を用いて、重さをVにする上で実現可能な価値の最大値
dpr=[[0 for i in range(T)] for j in range(N+2)]
for i in range(1,N+1):
    weight,value=d[-i]
    for j in range(T):
        if j>=weight:
            dpr[N+1-i][j]=max(dpr[N+2-i][j],dpr[N+2-i][j-weight]+value)
        else:
            dpr[N+1-i][j]=dpr[N+2-i][j]

#dpr[K][V]=K番目からN番目までの荷物を用いて重さをV以下にする上で実現可能な価値の最大値にする
for i in range(1,N+1):
    for j in range(1,T):
        dpr[i][j]=max(dpr[i][j],dpr[i][j-1])
    
ans=0
for i in range(N):
    sub=d[i][1]
    #i+1番目の物を使わない
    add=0
    for j in range(T):
        add=max(add,dpl[i][j]+dpr[i+2][T-1-j])
    sub+=add
    ans=max(sub,ans)
print(ans)
### BUGGY CODE ###

n,m = map(int,input().split())
tree=[[] for _ in range(n+1)]
ans=[0]*n 
for _ in range(m):
    a,b=map(int,input().split())
    tree[a].append(b)
    tree[b].append(a)
    
checked=[False]*(n+1)
checked[1]=True
stack=[1]
while stack:
    p=stack.pop()
    for i in tree[p]:
        if checked[i]:
            continue
        ans[i-1]=p
        checked[i]=True
        stack=[i]+stack

print('Yes')
for i in ans[1:]:
    print(i)

### FIXED CODE ###

from collections import deque
n,m = map(int,input().split())
tree=[[] for _ in range(n+1)]
ans=[0]*n 
for _ in range(m):
    a,b=map(int,input().split())
    tree[a].append(b)
    tree[b].append(a)
    
checked=[False]*(n+1)
checked[1]=True
stack=deque([1])
while stack:
    p=stack.popleft()
    for i in tree[p]:
        if checked[i]:
            continue
        ans[i-1]=p
        checked[i]=True
        stack.append(i)

print('Yes')
for i in ans[1:]:
    print(i)
### BUGGY CODE ###

N = int(input())
A_list = [int(i) for i in input().split()]
staff_count_list = []

for i in range(1, N + 1):
    staff_count = A_list.count(i)
    staff_count_list.append(staff_count)

for staff_count in staff_count_list:
    print(staff_count)

### FIXED CODE ###

N = int(input())
A_list = [int(i) for i in input().split()]

staff_count_list = [0] * N

for i in A_list:
    staff_count_list[i - 1] += 1
for i in staff_count_list:
    print(i)
### BUGGY CODE ###

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

if S[0] != T[0]:
  print(-1)
  exit()

lcm = N * M // math.gcd(N, M)
#1,(L/N) +1, 2*(L/N) +1..(N-1)*(L/N)+1
tekito =[]
for i in range(1,N):
  tekito.append(i*(lcm//N)+1)
  
for i in range(1,M):
  k = i*(lcm//M)+1
  if k in tekito:
#    print(k)
#    print(tekito.index(k)+1)
#    print(i)
    if S[tekito.index(k)+1] != T[i]:
      print(-1)
      exit()
print(lcm)

### FIXED CODE ###

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

if S[0] != T[0]:
  print(-1)
  exit()

lcm = N * M // math.gcd(N, M)
#1,(L/N) +1, 2*(L/N) +1..(N-1)*(L/N)+1
tekito =[]
for i in range(1,N):
  tekito.append(i*(lcm//N)+1)
tekitu =[]
for i in range(1,M):
  tekitu.append(i*(lcm//M)+1)

gattai = set(tekito) & set(tekitu) 
for k in gattai:
  i1 = (k-1) // (lcm//N)
  i2 = (k-1) // (lcm//M)
  if S[i1] != T[i2]:
    print(-1)
    exit()
print(lcm)
### BUGGY CODE ###

import sys
input=sys.stdin.readline
n=int(input())
ss=input()
s=[]
for i in ss:
  s.append(ord(i)-ord('a'))
q=int(input())
bit=[[0]*(n+1) for _ in range(26)]
#print(bit)
def upd(at,by,char):
  while at<=n:
    bit[char][at]+=by
    at+=at&-at
def qry(at,char):
  ret=0
  while at>0:
    #print(at,char,end=" inside \n")
    ret+=bit[char][at]
    at-=at&-at
  return ret
for i in range(n):
  upd(i+1,1,s[i])
for _ in range(q):
  t,l,r=input().split()
  t=int(t)
  if t==1:
    # print(t,l,r,end=" inside if")
    i=int(l)
    cq=ord(r)-ord('a')
    prev=s[i-1]
    if prev==cq:
      continue
    upd(i,-1,prev)
    curr=cq
    upd(i,1,curr)
    s[i-1]=cq
    #change ith character to cq  
  else:
    #    print(t,l,r,end=" inside else")
    l=int(l)
    r=int(r)
    ans=0
    for i in range(26):
      if qry(r,i)-qry(l-1,i)>0:
        ans+=1
    print(ans)


### FIXED CODE ###

import sys
input=sys.stdin.readline
n=int(input())
#print(n,end=' n')
data=[0]*(2*n)
def upd(i,x):
  i+=n
  data[i]=x
  while i>1:
    data[i>>1]=data[i]|data[i^1]
    i>>=1
def qry(l,r):
  l+=n
  r+=n
  res=0
  while l<r:
    if l&1:
      res|=data[l]
      l+=1
    if r&1:
      r-=1
      res|=data[r]
    l>>=1
    r>>=1
  return bin(res).count('1')

for i,c in enumerate(input()[:-1],n):
  data[i]=1<<(ord(c)-ord('a'))
for i in range(n-1,0,-1):
  data[i]=data[i<<1]|data[i<<1|1]
ans=[]
for _ in range(int(input())):
  q,a,b=input().split()
  if int(q)==1:
    upd(int(a)-1,1<<(ord(b)-ord('a')))
  else:
    ans.append(qry(int(a)-1,int(b)))
print('\n'.join(map(str,ans)))
### BUGGY CODE ###

n = int(input())
s = list(map(int,input().split()))
t = []
for i in s:
  t.append(i)
  t = t[::-1]
print(*t)

### FIXED CODE ###

n = int(input())
l = list(map(int,input().split()))
if n%2==0:
  a = l[1::2][::-1]
  b = l[::2]
  for i in a:
    print(i,end=' ')
  for j in b:
    print(j,end=' ')
  
else:
  a = l[0::2][::-1]
  b = l[1::2]
  for i in a:
    print(i,end=' ')
  for j in b:
    print(j,end=' ')