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

import bisect

N, Q = map(int, input().rstrip().split(' '))

construction = [list(map(int, input().rstrip().split(' '))) for _ in range(N)]
D = [int(input()) for _ in range(Q)]
construction = sorted(construction, key=lambda x: x[2])

d2i = dict([(d, i) for i, d in enumerate(D)])
dist = [-1] * Q
indices = list(range(Q))
for c in construction:
    i1 = bisect.bisect_left(D, c[0] - c[2])
    i2 = bisect.bisect_left(D, c[1] - c[2])
    for i in range(i2-1, i1-1, -1):
        d = D.pop(i)
        dist[d2i[d]] = c[2]
    
for d in dist:
    print(d)
    

### FIXED CODE ###

import sys
import bisect
input=sys.stdin.readline

N, Q = map(int, input().split(' '))

construction = [list(map(int, input().split(' '))) for _ in range(N)]
D = [int(input()) for _ in range(Q)]
construction = sorted(construction, key=lambda x: x[2])

dist = [-1] * Q
jump = [-1] * Q
indices = list(range(Q))
for s, t, x in construction:
    i1 = bisect.bisect_left(D, s-x)
    i2 = bisect.bisect_left(D, t-x)
    i = i1
    while i < i2:
        k = jump[i]
        if k != -1:
            i = k
        else:
            jump[i] = i2
            dist[i] = x
            i += 1
    
for d in dist:
    print(d)
### BUGGY CODE ###

# coding: utf-8


def solve(*args: str) -> str:
    t = int(args[0])
    ret = []
    for i in range(1, 3*t+1, 3):
        n = int(args[i])
        A = map(int, args[i+1].split())
        S = map(int, tuple(args[i+2]))

        A0 = set()
        A1 = set()
        for a, s in zip(A, S):
            if s == 1:
                A0.add(a)
            elif s == 0:
                A1.add(a)

        Y = set([0])
        for a in A0:
            if a not in Y:
                for y in Y.copy():
                    Y.add(a ^ y)

        is_subset = True
        X = set([0])
        for a in A1:
            Z = set()
            if a not in X:
                for x in X:
                    Z.add(a ^ x)

            if not Z <= Y:
                is_subset = False
                break
            X |= Z

        ret.append(0 if is_subset else 1)

    return '\n'.join(map(str, ret))


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))


### FIXED CODE ###

# coding: utf-8


def solve(*args: str) -> str:
    t = int(args[0])
    ret = []
    for i in range(1, 3*t+1, 3):
        n = int(args[i])
        A = tuple(map(int, args[i+1].split()))
        S = tuple(map(int, tuple(args[i+2])))

        ans = False
        dp = [0]*(max(A).bit_length()+1)
        for a, s in reversed(tuple(zip(A, S))):
            m = a.bit_length()
            if s == 0:
                while 0 < a and 0 < dp[m]:
                    a ^= dp[m]
                    m = a.bit_length()
                if 0 < a:
                    dp[m] = a
            elif s == 1:
                while 0 < a:
                    if 0 < dp[m]:
                        a ^= dp[m]
                        m = a.bit_length()
                    else:
                        ans = True
                        break

        ret.append(1*ans)

    return '\n'.join(map(str, ret))


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))
### BUGGY CODE ###

import math
from functools import lru_cache


def resolve():
    MOD = 10**9 + 7
    N, K = map(int, input().split())
    A = list(map(int, input().split()))

    A.sort()
    B = A[::-1]

    @lru_cache(maxsize=None)
    def permutations_count(n, r):
        return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

    sum = 0
    for i in range(K-1, N):
        sum += permutations_count(i, K-1) * A[i] % MOD - permutations_count(i, K-1) * B[i] % MOD

    print(sum % MOD)


if __name__ == "__main__":
    resolve()

### FIXED CODE ###

import math
from functools import lru_cache
from operator import mul
from functools import reduce


def resolve():
    import sys
    input = sys.stdin.readline
    MOD = 10**9 + 7
    N, K = map(int, input().split())
    A = list(map(int, input().split()))

    A.sort()
    B = A[::-1]

    @lru_cache(maxsize=None)
    def combinations_count__(n, r):
        return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

    @lru_cache(maxsize=None)
    def combinations_count____(n, r):
        r = min(r, n - r)
        numer = reduce(mul, range(n, n - r, -1), 1)
        denom = reduce(mul, range(1, r + 1), 1)
        return numer // denom

    def combinations_count_(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

    def modinv(a, mod=10**9+7):
        return pow(a, mod-2, mod)

    def combinations_count(n, r, mod=10**9+7):
        if (r < 0) or (n < r):
            return 0
        r = min(r, n-r)
        return fact[n] * factinv[r] * factinv[n-r] % mod
    
    fact = [1, 1]
    factinv = [1, 1]
    inv = [0, 1]
    for i in range(2, N + 1):
        fact.append((fact[-1] * i) % MOD)
        inv.append((-inv[MOD % i] * (MOD // i)) % MOD)
        factinv.append((factinv[-1] * inv[-1]) % MOD)

    sum = 0
    for i in range(K-1, N):
        sum += combinations_count(i, K-1) * A[i] % MOD - combinations_count(i, K-1) * B[i] % MOD

    print(sum % MOD)


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

from collections import Counter

N, *S = open(0).read().split()
count = Counter(S)
ans_list = [i for i, j in count.items() if j == max(count.values())]
ans_list.sort()
print("\n".join(ans_list))

### FIXED CODE ###

from collections import Counter

N, *S = open(0).read().split()
count = Counter(S)
max_value = max(count.values())
ans_list = [i for i, j in count.items() if j == max_value]
ans_list.sort()
print("\n".join(ans_list))
### BUGGY CODE ###

s = input()
k = 0
while True:
  if "10" in s:
    k += s.count("10")*2
    s = s.replace("10","")
  elif "01" in s:
    k += s.count("01")*2
    s = s.replace("01","")
  else:
    print(k)
    break

### FIXED CODE ###

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

N,M=map(int,input().split())
high_list=list(map(int,input().split()))
pathlist=[]
for i in range(M):
    pathlist.append(list(map(int,input().split())))
waylist=[0]*N
ans=N
for n in range(1,N+1):
    for m in pathlist:
        if(n in m):#もし経路に入っていたら
            if(m[0]==n):#自身じゃない方の灯台
                if(high_list[n-1]<=high_list[m[1]-1]):#経路先が自身よりも高い
                    ans=ans-1#回答に含まない
                    break
            else:
                if(high_list[n-1]<=high_list[m[0]-1]):#経路先が自身よりも高い
                    ans=ans-1
                    break
print(ans)




### FIXED CODE ###

N,M=map(int,input().split())
high_list=list(map(int,input().split()))
highest=[True]*N
for i in range(M):
    a,b=map(int,input().split())
    if(high_list[a-1]>=high_list[b-1]):
        highest[b-1]=False
    if(high_list[a-1]<=high_list[b-1]):
        highest[a-1]=False
print(sum(highest))
### BUGGY CODE ###

n,m=map(int,input().split())
x=list(map(int,input().split()))
x.sort()
y=[]
for i in range(1,m):
    y.append(x[i]-x[i-1])
for j in range(n-1):
    if len(y)!=0:
        y.pop(y.index(max(y)))
print(sum(y))

### FIXED CODE ###

n,m=map(int,input().split())
x=list(map(int,input().split()))
def main(n,m,x):
    x.sort()
    y=[]
    if m<=n:return 0
    if m==1:return 0
    if n==1:return x[-1]-x[0]
    for i in range(1,m):
        y.append(x[i]-x[i-1])
    y.sort()
    y=y[:(1-n)]
    return sum(y)

print(main(n,m,x))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def main():
    n = int(input())
    s = input()
    R = []
    G = []
    B = []
    R_a = R.append
    G_a = G.append
    B_a = B.append

    for i in range(n):
        if s[i] == "R":
            R_a(i + 1)
        elif s[i] == "G":
            G_a(i + 1)
        else:
            B_a(i + 1)
    res = 0
    for r in R:
        for g in G:
            for b in B:
                if r + g != b * 2 and g + b != r * 2 and b + r != g * 2:
                    res += 1
    print(res)
if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    n = int(input())
    s = input()
    R = 0
    G = 0
    B = 0

    for i in range(n):
        if s[i] == "R":
            R += 1
        elif s[i] == "G":
            G += 1
        else:
            B += 1
            
    res = R*G*B
    for i in range(n - 2):
        for j in range(i + 1, i + 1 + (n - 1 - i) // 2):
            k = j + (j - i)
            if s[i] != s[j] != s[k] != s[i]:
                res -= 1
    print(res)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import copy
n, max_w = map(int, input().split())

dp = [0]*(max_w+1)
for _ in range(n):
    dp_copy = copy.copy(dp)
    w, v = map(int, input().split())
    for i in range(w, max_w+1):
        if i >= w:
            dp_copy[i] = max(dp[i-w] + v, dp[i])
    dp = copy.copy(dp_copy)

print(max(dp))

### FIXED CODE ###

import numpy as np
n, max_w = map(int, input().split())

dp = [0]*(max_w+1)
dp = np.array(dp)

for _ in range(n):
    w, v = map(int, input().split())
    np.maximum(dp[:-w] + v, dp[w:], out=dp[w:])

print(max(dp))
### BUGGY CODE ###

N, M = [int(v) for v in input().split()]
A = [int(v) for v in input().split()]
for i in range(1, N):
    A[i] += A[i - 1]

ans = 0
for l in range(N):
    for r in range(l, N):
        if l <= 0:
            lc = 0
        else:
            lc = A[l - 1]
        cnt = A[r] - lc
        if cnt % M == 0:
            ans += 1
print(ans)

### FIXED CODE ###

N, M = [int(v) for v in input().split()]
A = [0] + [int(v) for v in input().split()]
for i in range(1, N + 1):
    A[i] = (A[i] + A[i - 1]) % M

from collections import Counter
import math


def combinations_count(n, r):
    if n <= 1:
        return 1
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


counter = Counter()
for a in A:
    counter[a] += 1

ans = 0
for c in counter.values():
    if c <= 1: continue
    ans += combinations_count(c, 2)
print(ans)
### BUGGY CODE ###

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

#n=4
#a=8
#x=[7,9,8,9]

#n=8
#a=5
#x=[3,6,2,8,7,6,5,9]

for i in range(n):
    x[i]=x[i]-a
    
n2=n//2
n3=n-n2

y=[]
for i in range(n3):
    y.append(x[i+n2])

# itertools 使用 bit全探索
import itertools

xsum=[]
for i in itertools.product([0,1], repeat=n2):
    isum=0
    for ii in range(n2):
        if i[ii]==0:
            isum=isum+x[ii]
    xsum.append(isum)
    
icnt=0
for ix in range(len(xsum)):
    for i in itertools.product([0,1], repeat=n3):
        isum=0
        for ii in range(n3):
            if i[ii]==0:
                isum=isum+y[ii]
#        print(isum,xsum[ix])
        if isum==-xsum[ix]:
            icnt=icnt+1

print(icnt-1)

### FIXED CODE ###

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

for i in range(n):
    x[i]=x[i]-a
    
nx=n*n
dp=[[0]*(2*nx+1) for i in range(n+1)]

#print(dp)

dp[0][nx]=1

for j in range(1,n+1):
    jj=j-1
    for t in range(2*nx+1):
        if t-x[jj]<0 or 2*nx<t-x[jj]:
            dp[j][t]=dp[j-1][t]
        elif 0<t-x[jj] and  t-x[jj]<2*nx:
            dp[j][t]=dp[j-1][t]+dp[j-1][t-x[jj]]
        else:
            dp[j][t]=0

print(dp[n][nx]-1)
### BUGGY CODE ###

n,k = map(int,input().split())
while n > abs(n-k):
    n = abs(n-k)
print(n)

### FIXED CODE ###

n,k = map(int,input().split())
n %= k
ans = min(n,abs(n-k))
print(ans)
### BUGGY CODE ###

from collections import defaultdict
N, M = map(int, input().split())
dic = defaultdict(list)
for i in range(M):
  u, v = map(int, input().split())
  dic[u-1] += [v-1]
S, T = map(int, input().split())
S -= 1
T -= 1
dist = [[float('inf')]*3 for i in range(N)]
ls = [float('inf')]*3
dist[S][0] = 0
q = [(S,0)]
flag = False
while q:
  e, m = q.pop()
  n = (m+1)%3
  for p in dic[e]:
    if p==T:
      flag = True
    if dist[p][n]>dist[e][m]+1:
      dist[p][n] = dist[e][m]+1
      q += [(p,n)]
if flag:
  ans = dist[T][0] if dist[T][0]!=float('inf') else -1
  print(ans//3)
else:
  print(-1)
      

### FIXED CODE ###

from collections import defaultdict, deque
N, M = map(int, input().split())
dic = defaultdict(list)
for i in range(M):
  u, v = map(int, input().split())
  dic[u-1] += [v-1]
S, T = map(int, input().split())
S -= 1
T -= 1
dist = [[float('inf')]*3 for i in range(N)]
dist[S][0] = 0
q = deque([(S,0)])
flag = False
cnt = 0
while q:
  cnt += 1
  e, m = q.popleft()
  n = (m+1)%3
  for p in dic[e]:
    if p==T:
      flag = True
    if dist[p][n]>dist[e][m]+1:
      dist[p][n] = dist[e][m]+1
      q += [(p,n)]
if flag:
  ans = dist[T][0] if dist[T][0]!=float('inf') else -1
  print(ans//3)
else:
  print(-1)
### BUGGY CODE ###

import math
n=input()
a=map(int, raw_input().split())
a.sort()
a.reverse()

def comb(N,R):
	return math.factorial(N)/( math.factorial(N-R)*math.factorial(R) )



l=1
r=n-1
c=a[0]
for i in range(20):
	if comb(c,a[(l*2+r)/3]) > comb(c,a[(l+r*2)/3]):
		r=(l+r*2)/3
	else:
		l=(l*2+r)/3


if comb(c,a[(l*2+r)/3]) > comb(c,a[(l+r*2)/3]):
	print c,a[(l*2+r)/3]
else:
	print c,a[(l+r*2)/3]
	 

### FIXED CODE ###

import math
n=input()
a=map(int, raw_input().split())
a.sort()
a.reverse()


c=a[0]

b=[0 for i in range(n)]
for i in range(1,n):
	b[i]=abs(a[i]-c/2)

min_b=min(b[1:])

d=[]
for i in range(1,n):
	if b[i]==min_b:
		d.append(a[i])

d.sort()
d.reverse()

print c,d[0]
### BUGGY CODE ###

n,m = map(int,input().split())
PS = [list(input().split()) for i in range(m)]
AC = []
WA = 0

for i in range(m):
    if PS[i][1] == "AC":
        p = PS[i][0]
        if p not in AC:
            WA += PS[:i+1].count([p,"WA"])
            AC.append(p)

print(len(AC),WA)

### FIXED CODE ###

n,m = map(int,input().split())
AC = [0] * n
WA = [0] * n
penalty = 0

for i in range(m):
    p,s = input().split()
    p = int(p) - 1
    
    if s == "WA":
        WA[p] += 1
    else:
        if AC[p] == 0:
            AC[p] = 1
            penalty += WA[p]
            
print(sum(AC),penalty)
### BUGGY CODE ###

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

dp = [[-float("INF")]*(n+1) for i in range(n+1)]
low = [-float("INF")]*(n+1)
col = [-float("INF")]*(n+1)
m = 0
a,b = A[:2]
dp[a][b] = 0
dp[b][a] = 0
low[a] = 0
col[a] = 0
low[b]
col[b] = 0
base = 0

for _ in range(1,n):
    a,b,c = A[3*_-1:3*_+2]
    q = []
    if a==b==c:
        base += 1
        continue
    for j in range(3):
        q.append((a,b,max(m,dp[c][c]+1)))
        for i in range(1,n+1):
            q.append((a,i,low[i]))
        if a==b:
            for i in range(1,n+1):
                q.append((c,i,dp[a][i]+1))
        a,b,c = b,c,a
    for a,b,v in q:
        dp[a][b] = max(dp[a][b],v)
        dp[b][a] = max(dp[b][a],v)
        low[a] = max(low[a],v)  
        low[b] = max(low[b],v)  
        col[a] = max(col[a],v)  
        col[b] = max(col[b],v) 
        m = max(m,v)     
print(max(m,dp[A[-1]][A[-1]]+1)+base)


### FIXED CODE ###

import sys
input = sys.stdin.readline

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

dp = [[-float("INF")]*(n+1) for i in range(n+1)]
low = [-float("INF")]*(n+1)
m = 0
a,b = A[:2]
dp[a][b] = 0
dp[b][a] = 0
low[a] = 0
low[b] = 0
base = 0

for _ in range(1,n):
    a,b,c = A[3*_-1:3*_+2]
    q = []
    if a==b==c:
        base += 1
        continue
    m1 = max(m,max(dp[a][a],dp[b][b],dp[c][c])+1)
    for j in range(3):
        q.append((a,b,max(m,dp[c][c]+1)))
        for i in range(1,n+1):
            q.append((a,i,low[i]))
        if a==b:
            for i in range(1,n+1):
                q.append((c,i,dp[a][i]+1))
                m1 = max(m1,dp[a][i]+1)
        a,b,c = b,c,a
    for a,b,v in q:
        dp[a][b] = max(dp[a][b],v)
        dp[b][a] = max(dp[b][a],v)
        low[a] = max(low[a],v)  
        low[b] = max(low[b],v)      
    m = m1
print(max(m,dp[A[-1]][A[-1]]+1)+base)
### BUGGY CODE ###

N = int(input())


def f_func(X):
    ans = [0] * (X - 1)
    n = 2
    for _ in range(X - 1):
        j = 1
        while True:
            mod = X % n
            if mod != 0:
                break
            ans[n-2] = j
            X = X // n
            j += 1
        n += 1
    result = 1
    for i in ans:
        result = result * (i + 1)
    return result

ans = 1
for i in range(2, N + 1):
    ans += i * f_func(i)
print(ans)

### FIXED CODE ###

N = int(input())


def f(x):
    result = N // x
    return result

ans = 0
for x in range(1, N + 1):
    Y = f(x)
    ans += x * Y * (Y + 1) / 2
print(int(ans))
### BUGGY CODE ###

N,M=map(int,input().split())
#dab={}
lab=[]
for i in range(N):
    a,b=map(int,input().split())
    #dab[a]=b
    lab.append([a,b])
#dab.sort(key=lambda )
lab.sort(key=lambda x:-x[1])
#print("lab",lab)
#lsch=[-1]*M#ミスしてた#やっぱおk_どうせM番目には入らない
#lsch=[M-1-i for i in range(M)]
dsch={i:0 for i in range(M)}
ans=0
for ab in lab:
    if ab[0]<=M:
        d=M-ab[0]
        #while d>=0:
        #for i in range(d,-1,-1):
        #    if lsch[i]==-1:#whileから書き直したときiではなくdのままにしていた
        #        lsch[i]=1
        #        ans+=ab[1]
        #        #print("ab",ab)
        #        break
            #d-=1
        #while d>=0:
        for i in range(d,-1,-1):
            if i in dsch:
                ans+=ab[1]
                #print("ab",ab)
                del dsch[i]
                break
#print("lsch",lsch)
#print("dsch",dsch)
print(ans)


### FIXED CODE ###

import heapq
import sys
input=sys.stdin.readline
N,M=map(int,input().split())
lab=[]
for i in range(N):
    llab=list(map(int,input().split()))
    lab.append(llab)
lab.sort(key=lambda ab:ab[0])
hq=[]
ind=0
ans=0
#print(lab)
#c=0
for i in range(M):
    if hq:
            ans-=heapq.heappop(hq)
    for j in range(ind,N):
        #if f==0:
        #print(i,j,lab[j][0])
        if lab[j][0]==i+1:
            heapq.heappush(hq,-lab[j][1])#
        else:
            ind=j
            #j=N-1#これダメ、抜けられていない
            break
        #c+=1
    #if hq:
    #        ans-=heapq.heappop(hq)
    #print(hq)
#print(c)
if hq:
    ans-=heapq.heappop(hq)
print(ans)
#for i in range(3):
#    i=3
#    print(12345)
### BUGGY CODE ###


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

## 種類数の求め方
# 1. A内の要素を取り出して、それがA内に存在するとき：種類＋１
# 2. その要素を重複数だけAから削除してループ

kinds = 0
A = sorted(A)
A_Left = A
duplicatedList = []
while len(A_Left) > 0:
    if A_Left[0] in A_Left:
        kinds += 1
        duplicatedList.append(A.count(A_Left[0]))
        for j in range(A_Left.count(A_Left[0])):
            A_Left.remove(A_Left[0])

if kinds <= K:
    print('0')
elif kinds > K:
    duplicatedList = sorted(duplicatedList)
    i = 0
    tmp = 0
    while kinds > K:
        kinds -= 1
        tmp += duplicatedList[i]
        i += 1
    print(tmp)

### FIXED CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
d={}
l=[]
for i in range(n):
    try:
        l[d[a[i]]]+=1
    except:
        d[a[i]]=len(l)
        l.append(1)
ans=0
l.sort()
for i in range(len(l)-k):
    ans+=l[i]
print(ans)
### BUGGY CODE ###

def ncr(n,r,p):
    num = den = 1
    for i in range(r):
        num = (num * (n-i)) % p
        den = (den * (i + 1)) % p
    return (num * pow(den, p-2, p)) % p

n,m,k = (int(x) for x in input().split())
p = 998244353
ans = 0
for i in range(k+1):
    ans += m*pow(m-1, n-i-1,p) * ncr(n-1,i,p)
    if ans > p:
        ans = ans % p 
print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline

f = [(1,1), ]

def ncr(n,r,p):
    num = (f[-1][0] * (n-(r-1))) % p
    den = (f[-1][1] * ((r-1) + 1)) % p
    f.append([num, den])
    return (num * pow(den, p-2, p)) % p

n,m,k = (int(x) for x in input().split())
p = 998244353
ans = 0

for i in range(k+1):
    if i == 0:
        ans += m*pow(m-1, n-i-1,p)
    else:
        ans += m*pow(m-1, n-i-1,p) * ncr(n-1,i,p)
    ans = ans % p 
print(ans)
### BUGGY CODE ###

N = int(input())

s = []
for i in range(N):
    x = sorted(input())
    s.append(x)

count = 0
start = 0
while(start<N):
    for j in range(len(s)):
        if j <= start:
            pass
        else:
            if s[start] == s[j]:
                count += 1

    start += 1

    if s==False:
        break

print(count)

### FIXED CODE ###

N = int(input())
s = [''.join(sorted(input())) for _ in range(N)]

from collections import Counter
counter = Counter(s)
ans = sum(n*(n-1)//2 for n in counter.values())
print(ans)
### BUGGY CODE ###

n=int(input())

for i in range(1000):
  for j in range(1000):
    for k in range(1000):
      for l in range(1000):
        for m in range(1000):
          for n in range(1000):
            price = i*100+j*101+k*102+l*103+m*104+n*105
            if price == n:
              print(1)

print(0)

### FIXED CODE ###

import sys
import math

n=int(input())
a=n%100
b=math.floor(n/100)+1
f=True
while b != 0:
  for i in range(b):
    for j in range(b-i):
      for k in range(b-i-j):
        for l in range(b-i-j-k):
          for m in range(b-i-j-k-l):
            if i+2*j+3*k+4*l+5*m == a:
              print(1)
              sys.exit()
  a+=100
  b-=1
print(0)
### BUGGY CODE ###

N,S,Q,*K = open(0).read().split()
N = int(N)
K = map(int,K)
for k in K:
  C = [0]*N
  M = [0]*N
  CMS = [0]*N
  SDMC = 0
  SMC = 0
  SC = 0
  Ms = 0
  for i in range(N):
    if i>=k:
      Ms -= M[i-k]
    if S[i]=='C':
      CMS[i] = Ms
    elif S[i]=='M':
      Ms += 1
      M[i] = 1
  for i in range(N-1,-1,-1):
    if i<=N-1-k:
      SC -= C[i+k]
      SMC -= CMS[i+k]
    if S[i]=='C':
      SC += 1
      C[i] = 1
    elif S[i]=='M':
      SMC += SC
    elif S[i]=='D':
      SDMC += SMC
  print(SDMC)


### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

N = int(readline())
S = np.frombuffer(readline().rstrip(),'S1')
Q = int(readline())
query = map(int,read().split())

isD = S == b'D'
isM = S == b'M'
isC = S == b'C'

cumD = isD.cumsum(dtype=np.int64)
cumM = isM.cumsum(dtype=np.int64)

def F(K):
    """
    ・Cごとに数える。
    ・そのためには(i-K,i] 内のDMの個数を調べる（負インデックスには関係ない文字があると思っておく）
    ・区間内のDの個数、Mの個数が取得できれば、差分が取得できるので最後に累積和
    """
    # (i-K,i]内のDの個数、Mの個数
    D = cumD.copy(); D[K:] -= cumD[:-K]
    M = cumM.copy(); M[K:] -= cumM[:-K]
    # 最後がMのとき、Dの個数分増える
    DM = isM * D
    # 左端のDを捨てるとき、Mの個数分減る
    DM[K:] -= isD[:-K] * M[K-1:-1]
    np.cumsum(DM,out=DM)
    # Cごとに集計
    return DM[isC].sum()

print('\n'.join(str(F(K)) for K in query))
### BUGGY CODE ###

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

def lcm(a):
    from fractions import gcd
    x = a[0]
    for i in range(1, len(a)):
        x = (x * a[i]) // gcd(x, a[i])
    return x

ans = 0

for i in range(N):
    ans += (lcm(a)-1)%a[i]
    
print(ans)

### FIXED CODE ###

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

def lcm(a):
    from fractions import gcd
    x = a[0]
    for i in range(1, len(a)):
        x = (x * a[i]) // gcd(x, a[i])
    return x

ans = 0
pi = 1

for i in range(N):
    pi *= a[i]

for i in range(N):
    ans += (pi-1)%a[i]
    
print(ans)