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

"""
累積和っぽい

始点と終点の"2"つを指定しなければいけない
⇨二次元累積和ってやつ。

参考
https://qiita.com/drken/items/56a6b68edef8fc605821
"""

import numpy as np
N,M,Q = map(int,input().split())
A = np.zeros((N+1,N+1))
Acum = np.zeros((N+1,N+1))

for _ in range(M):
    L,R = map(int,input().split())
    A[L-1][R-1] += 1

#2次元累積和
for i in range(N):
    for j in range(N):
        Acum[i+1][j+1] = Acum[i][j+1] + Acum[i+1][j] - Acum[i][j] + A[i][j]

# print(Acum)
for _ in range(Q):
    p,q= map(int,input().split())
    A = Acum[q,q]-Acum[p-1,q]-Acum[q,p-1]+Acum[p-1,p-1]
    print(int(A))

### FIXED CODE ###

N,M,Q = map(int,input().split())
A = [[0 for i in range(N+1)] for j in range(N+1)]
Acum = [[0 for i in range(N+1)] for j in range(N+1)]

for _ in range(M):
    L,R = map(int,input().split())
    A[L-1][R-1] += 1

#2次元累積和
for i in range(N):
    for j in range(N):
        Acum[i+1][j+1] = Acum[i][j+1] + Acum[i+1][j] - Acum[i][j] + A[i][j]

# print(Acum)
for _ in range(Q):
    p,q= map(int,input().split())
    A = Acum[q][q]-Acum[p-1][q]-Acum[q][p-1]+Acum[p-1][p-1]
    print(A)
### BUGGY CODE ###

N=int(input())
S=[list(str(input())) for i in range(N)]

for i in range(N):
  S[i]=sorted(S[i])
r=0
for i in range(N-1):
  for j in range(i+1,N):
    if S[i]==S[j]:
      r+=1
print(r)

### FIXED CODE ###

N=int(input())
M={}
ans=0
for i in range(N):
    s=''.join(sorted(list(str(input()))))
    if s in M:
        ans+=M[s]
        M[s]+=1
    else:
        M[s]=1
print(ans)
### BUGGY CODE ###

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

for i in range(n+1):
    for j in range(n+1):
        for k in range(n+1):
            if i + j + k == n:
                if  10000 * i + 5000 * j + 1000 * k == y:
                    print(i, j, k)
                    exit()
                    
print(-1, -1, -1)  

### FIXED CODE ###

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

for i in range(n + 1):
    for j in range(n + 1 - i):
            if  10000 * i + 5000 * j + 1000 * (n - i - j) == y:
                print(i, j, n - i - j)
                exit()
                    
print(-1, -1, -1)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 0
mod = (10 ** 9 + 7)
for i in range(n):
    for j in range(i + 1, n):
        ans = (ans + a[i] * a[j]) % mod

print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 0
mod = (10 ** 9 + 7)
total = sum(a)
for i in range(n):
    total -= a[i]
    ans = (ans + total * a[i]) % mod
print(ans)
### BUGGY CODE ###

S = input()[::-1]
keta = len(S)
mod = 10 ** 9 + 7

dp = [[0 for _ in range(13)] for _ in range(keta + 1)]
dp[0][0] = 1
for i in range(1, keta + 1):
    if S[i - 1] != "?":
        x = int(S[i - 1]) * (10 ** (i - 1)) % 13
        for j in range(13):
            dp[i][(x + j) % 13] += dp[i - 1][j] % mod
    else:
        for k in range(10):
            x = k * (10 ** (i - 1)) % 13
            for j in range(13):
                dp[i][(x + j) % 13] += dp[i - 1][j] % mod

print(dp[keta][5] % mod)


### FIXED CODE ###

S = input()[:: -1]
mod = 10 ** 9 + 7
dp = [[0 for _ in range(13)] for _ in range(len(S) + 1)]

if S[0] == "?":
    for k in range(10):
        dp[1][k % 13] += 1
else:
    dp[1][int(S[0]) % 13] += 1

tmp = 1
for i in range(2, len(S) + 1):
    tmp *= 10
    tmp %= 13
    for j in range(13):
        if dp[i - 1][j] > 0:
            if S[i - 1] == "?":
                for k in range(10):
                    dp[i][(tmp * k + j) % 13] += dp[i - 1][j] % mod
            else:
                dp[i][(tmp * int(S[i - 1]) + j) % 13] += dp[i - 1][j] % mod

print(dp[len(S)][5] % mod)
### BUGGY CODE ###

import sys
HK,WK,M = map(int, input().split())
W = [0] * (WK + 1)
H = [0] * (HK + 1)
HW = [[0 for i in range(WK+1)] for _ in range(HK+1)]
# 3*10^5

for i in range(M):
    h, w = map(int, input().split())

    H[h] += 1
    W[w] += 1

    HW[h][w] = 1

answer = 0
HMAX = max(H)
WMAX = max(W)

HEMAX = H.count(HMAX)
WEMAX = W.count(WMAX)
if HEMAX * WEMAX > M:
    print(HMAX + WMAX)
    sys.exit(0)

HMAXES = [i for i, _ in enumerate(H) if _ == HMAX]
WMAXES = [i for i, _ in enumerate(W) if _ == WMAX]

# 3*10^5
answer = HMAX + WMAX
for h in HMAXES:
    for w in WMAXES:
        if HW[h][w] == 0:
            print(answer)
            sys.exit(0)
print(answer-1)

### FIXED CODE ###

import sys
HK,WK,M = map(int, input().split())
W = [0] * (WK + 1)
H = [0] * (HK + 1)
HW = {}
# 3*10^5

for i in range(M):
    h, w = map(int, input().split())

    H[h] += 1
    W[w] += 1

    HW[(h,w)] = 1

answer = 0
HMAX = max(H)
WMAX = max(W)

HEMAX = H.count(HMAX)
WEMAX = W.count(WMAX)
if HEMAX * WEMAX > M:
    print(HMAX + WMAX)
    sys.exit(0)

HMAXES = [i for i, _ in enumerate(H) if _ == HMAX]
WMAXES = [i for i, _ in enumerate(W) if _ == WMAX]

# 3*10^5
answer = HMAX + WMAX
for h in HMAXES:
    for w in WMAXES:
        if not (h,w) in HW:
            print(answer)
            sys.exit(0)
print(answer-1)
### BUGGY CODE ###

n = int(input())
S = []
for i in range(n):
    tmp = "".join(sorted(input()))
    S.append(tmp)
count = 0
for j in range(len(S)):
    for k in range(j+1,len(S)):
        if S[j] == S[k]:
            count+=1
print(count)

### FIXED CODE ###

import collections
n = int(input())
s = collections.Counter(["".join(sorted(input())) for _ in range(n)]).most_common()
#print(s)
cnt = 0
for i in s:
    for j in range(1, i[1]):
        cnt += j
print(cnt)
### BUGGY CODE ###

def is_prime(q):
    q = abs(q)
    if q == 2: return True
    if q < 2 or q&1 == 0: return False
    return pow(2, q-1, q) == 1


N=input()
l=[ map(int,raw_input().split()) for i in range(N)]

a=[]
for m in l:
	cnt=0
	for i in range(m[0],m[1]+1):
		if i%2==0:
			continue
		elif i%3==0 and i!=3:
			continue
		else:
			if is_prime(i) and is_prime( (i+1)/2 ):
				cnt+=1
	a.append(cnt)


for i in a:
	print i
		

### FIXED CODE ###

N=input()
min_n=float("inf")
max_n=float("-inf")
a=[]
for i in range(N):
	l,r=map(int,raw_input().split())
	a.append((l,r))
	min_n=min(min_n,l)
	max_n=max(max_n,r)

prime=[i for i in range(0, max_n+1)]
prime[1]=0
p_len=len(prime)
for i in range(2,p_len):
	if prime[i]!=0:
		for j in range (i+i,p_len,i):
			prime[j]=0
#print prime

C=[0 for i in range(max_n+1)]
cnt=0
for i in range(max_n+1):
	if prime[i]!=0 and prime[(i+1)/2]!=0:
		cnt+=1
		C[i]=cnt
	else:
		C[i]=cnt

#print C


for i,j in a:
	print C[j]-C[i-1]
### BUGGY CODE ###

A, B, M = map(int, input().split())
a = list(input().split())
b = list(input().split())
l = []
n = []
for i in range(M):
  x, y, c = map(int, input().split())
  l.append(int(a[x-1])+int(b[y-1])-c)
l.sort()
for k in range(A):
  for m in range(B):
    n.append(int(a[k])+int(b[m]))
n.sort()
print(min(l[0],n[0]))

### FIXED CODE ###

A, B, M = map(int, input().split())
a = list(input().split())
b = list(input().split())
l = []
for i in range(M):
  x, y, c = map(int, input().split())
  l.append(int(a[x-1])+int(b[y-1])-c)
l.sort()
n = int(min(a)) + int(min(b))
print(min(l[0], n))
### BUGGY CODE ###

n = int(input())
c = []
for i in range(n):
    a = int(input())
    if a in c:
        c.pop(c.index(a))
    else:
        c.append(a)
print(len(c))

### FIXED CODE ###

n = int(input())
a = {}
for i in range(n):
    b = int(input())
    if b in a.keys():
        a[b] += 1
    else:
        a[b] = 1
ans = 0
for i in a.keys():
    if a[i]%2 == 1:
        ans += 1
print(ans)
### BUGGY CODE ###

n, q = list(map(int, input().split()))
s = input().split()[0]
lr_list = []

for _ in range(q):
    l, r = list(map(int, input().split()))
    lr_list.append((l, r))

count_ac_list = []
for i in range(n):
    count_ac_list.append(s[:i+1].count('AC'))

# print(count_ac_list)
count_list = [str(count_ac_list[r-1] - count_ac_list[l-1])
    if l > 1 else str(count_ac_list[r-1])
    for l, r in lr_list]

print('\n'.join(count_list))


### FIXED CODE ###

n, q = list(map(int, input().split()))
s = input().split()[0]
lr_list = [list(map(int, input().split())) for _ in range(q)]

count_ac_list = [0] * n
for i in range(n-1):
    # print('{}: {}'.format(i, s[i:i+2]))
    if s[i:i+2] == 'AC':
        count_ac_list[i+1] = count_ac_list[i] + 1
    else:
        count_ac_list[i+1] = count_ac_list[i]

count_list = [str(count_ac_list[r-1] - count_ac_list[l-1]) for l, r in lr_list]

print('\n'.join(count_list))
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
B = [A.count(i+1) for i in range (N)]
C = [int(B[j]*(B[j]-1)/2) for j in range (N)]
D = sum(C)
for k in range(N):
  print(D if B[A[k]-1] < 2 else D-B[A[k]-1]+1)

### FIXED CODE ###

import collections
N = int(input())
A = list(map(int, input().split()))
B = collections.Counter(A)
L = {key:(B[key] * (B[key] - 1) // 2) for key in B}
total = sum(L.values())
#print(f"A = {A}\nB = {B}\nL = {L}\ntotal = {total}")
[print(total if L[i] == 0 else total - L[i] + ((B[i] - 1) * (B[i] - 2) // 2)) for i in A]
### BUGGY CODE ###

N = int(input())
lists = input().split()
#print(lists)
ans = ''
for n in range(1,N+1):
    a = lists.index(str(n))+1
    #print(a)
    ans = ans + str(a) + " "
print(ans)    

### FIXED CODE ###

N = int(input())
lists = list(map(int, input().split()))
#print(lists)
ans = [0]*N
for i, order in enumerate(lists):
    ans[order-1] = i+1
print(*ans)
### BUGGY CODE ###

from copy import deepcopy as dc
S=list(map(len,input().split("T")))
x,y=map(int,input().split())
x=abs(x-S[0])
y=abs(y)
L=S[2::2]
R=S[1::2]
sumL=sum(L)
sumR=sum(R)
flag=0    
if sumL>=x and sumR>=y and (sumL-x)%2==0 and (sumR-y)%2==0 and flag==0:
    setL={0}
    setR={0}
    setL1={0}
    setR1={0}
    gL=(sumL-x)//2
    gR=(sumR-y)//2
    if gL==0:
        flag=1
    else:
        for i in L:
            setL=dc(setL1)
            for j in setL:
                k=i+j
                if k<gL:
                    setL1.add(k)
                elif k==gL:
                    flag=1
                    break
            if flag==1:
                break
    if flag==1:
        if gR==0:
            flag=2
        else:
            for i in R:
                for j in setR:
                    setR=dc(setR1)
                    k=i+j
                    if k<gR:
                        setR1.add(k)
                    elif k==gR:
                        flag=2
                        break
                if flag==2:
                    break
if flag==2:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

from itertools import accumulate
S=list(map(len,input().split("T")))
x,y=map(int,input().split())
x=abs(x-S[0])
y=abs(y)
L=S[2::2]
R=S[1::2]
La=list(accumulate(L))
Ra=list(accumulate(R))
sumL=sum(L)
sumR=sum(R)
flag=0
if sumL>=x and sumR>=y and (sumL-x)%2==0 and (sumR-y)%2==0 and flag==0:
    setL1={0}
    setR1={0}
    gL=(sumL-x)//2
    gR=(sumR-y)//2
    if gL==0:
        flag=1
    else:
        for cnt,i in enumerate(L):
            setL=setL1
            setL1=set()
            s=setL1.add
            h=sumL-La[cnt]
            for j in setL:
                k=i+j
                #if k<gL and h+k>=gL:
                s(k)
                #if j<gL and h+j>=gL:
                s(j)
                if k==gL:
                    flag=1
                    break
            if flag==1:
                break
    if flag==1:
        if gR==0:
            flag=2
        else:
            for cnt,i in enumerate(R):
                setR=setR1
                setR1=set()
                s=setR1.add
                h=sumR-Ra[cnt]
                for j in setR:
                    k=i+j
                    #if k<gR and h+k>=gR:
                    s(k)
                    #if j<gR and h+j>=gR:
                    s(j)
                    if k==gR:
                        flag=2
                        break
                if flag==2:
                    break
if flag==2:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

N, M, Q = [int(_) for _ in input().split()]
listN = [[0] * (N+1) for i in range(N+1)]

for i in range(M):
	L, R = [int(_) for _ in input().split()]
	listN[L][R] += 1

retList = []
for i in range(Q):
	p, q = [int(_) for _ in input().split()]
	retList.append(sum(sum(_) for _ in [l[p:q+1] for l in listN[p:q+1]]))

for i in retList:
	print(i)

### FIXED CODE ###

#
#	106 D - AtCoder Express 2
#

N, M, Q = [int(_) for _ in input().split()]
listN = [[0] * (N+1) for i in range(N+1)]
listNsum = [[0] * (N+1) for i in range(N+1)]

for i in range(M):
	L, R = [int(_) for _ in input().split()]
	listN[L][R] += 1

#累積和計算
for iIdx, iList in enumerate(listN):
	for jIdx, jList in enumerate(iList):
		if jIdx == 0:
			listNsum[iIdx][jIdx] = listN[iIdx][jIdx]
		else:
			listNsum[iIdx][jIdx] = listNsum[iIdx][jIdx-1] + listN[iIdx][jIdx]


retList = []
for i in range(Q):
	p, q = [int(_) for _ in input().split()]
	sumv = 0
	for j in range(p, q+1):
		sumv += listNsum[j][q] - listNsum[j][p-1]
	retList.append(sumv)

for i in retList:
	print(i)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.buffer.readline().rstrip()
read = sys.stdin.buffer.read
def resolve():
    n,q=map(int,input().split())
    data = list(map(int,read().split()))
    S = data[:3*n:3]
    T = data[1:3*n:3]
    X = data[2:3*n:3]
    D = data[3*n:]

    E=[]
    E+=[(s-x,1,x) for s,x in zip(S,X)]
    E+=[(t-x,2,x) for t,x in zip(T,X)]
    E+=[(d,3,i) for i,d in enumerate(D)]
    E.sort()
    from collections import defaultdict
    cnt=defaultdict(int)
    cnt[INF]=1

    from heapq import heappop,heappush
    Q=[INF]
    ans=[None]*q
    for a,b,c in E:
        if(b==1):
            heappush(Q,c)
            cnt[c]+=1
        elif(b==2): # 本来はここでqからcを削除したいが、できないためb==3で処理する
            cnt[c]-=1
        else:
            while(cnt[Q[0]]==0): # 本来削除されるべき通行止めをここで消す
                heappop(Q)
            x=Q[0]
            ans[c]=x if(x!=INF) else -1
    print(*ans,sep="\n")
resolve()

### FIXED CODE ###

import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.buffer.readline().rstrip()
read = sys.stdin.buffer.read
def resolve():
    n,q=map(int,input().split())
    data = list(map(int,read().split()))
    S = data[:3*n:3]
    T = data[1:3*n:3]
    X = data[2:3*n:3]
    D = data[3*n:]

    E=[]
    E+=[(s-x,1,x) for s,x in zip(S,X)]
    E+=[(t-x,2,x) for t,x in zip(T,X)]
    E+=[(d,3,i) for i,d in enumerate(D)]
    E.sort()
    from collections import defaultdict
    cnt=defaultdict(int)
    cnt[INF]=1

    from heapq import heappop,heappush
    Q=[INF]
    ans=[None]*q
    for a,b,c in E:
        if(b==1):
            heappush(Q,c)
            cnt[c]+=1
        elif(b==2): # 本来はここでqからcを削除したいが、できないためb==3で処理する
            cnt[c]-=1
        else:
            while(cnt[Q[0]]==0): # 本来削除されるべき通行止めをここで消す
                heappop(Q)
            x=Q[0]
            ans[c]=x if(x!=INF) else -1
    print(*ans,sep="\n")
resolve()
### BUGGY CODE ###

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

ans = 0
for i in range(n-1):
    for j in range(i + 1, n):
        ans += a[i] * a[j]
        ans %= mod

print(ans)


### FIXED CODE ###

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

ans = 0
sum_a = sum(a)
for i in range(n):
    sum_a -= a[i]
    ans += sum_a * a[i]
    ans %= mod

print(ans)
### BUGGY CODE ###

import sys

input = sys.stdin.readline
n = int(input())
sl = list(input())[:-1]

q = int(input())
kl = list(map(int,input().split()))

for k in kl:
    # i文字目までのdとmとdmの数

    dp = [[0, 0, 0] for i in range(n+1)]
    ans = 0
    for i, s in enumerate(sl):
        if i - k >= 0:
            if sl[i-k] == "D":
                dp[i][0] -= 1
                dp[i][2] -= dp[i][1]
            if sl[i-k] == "M":
                dp[i][1] -= 1
        if s == "D":
            dp[i+1][0] = dp[i][0] + 1
        else:
            dp[i+1][0] = dp[i][0]
        if s == "M":
            dp[i+1][1] = dp[i][1] + 1
            dp[i+1][2] = dp[i][2] + dp[i][0]
        else:
            dp[i+1][1] = dp[i][1]
            dp[i + 1][2] = dp[i][2]
        if s == "C":
            ans += dp[i][2]

    print(ans)









### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    N = int(input())
    S = input()
    Q = int(input())
    x = tuple(map(int,input().split()))
    for k in x:
        d,m,dm,dmc = 0,0,0,0
        for i in range(N):
            if S[i] == "D":
                d += 1
            elif S[i] == "M":
                m += 1
                dm += d
            elif S[i] == "C":
                dmc += dm
            if i >= k-1:
                if S[i-k+1] == "D":
                    dm -= m
                    d -= 1
                elif S[i-k+1] == "M":
                    m -= 1
        print(dmc)
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

n,q = map(int,input().split())
s = input()
lr = []
for i in range(q): lr.append(list(map(int, input().split())))
ac = ['1' if 'AC'==s[i-1:i+1] else '0' for i in range(1,len(s))]
for i in lr: print(ac[i[0]-1:i[1]-1].count('1'))

### FIXED CODE ###

import itertools
n,q = map(int,input().split())
s = input()
lr = []
for i in range(q): lr.append(list(map(int, input().split())))
ac = [1 if i!=0 and 'AC'==s[i-1:i+1] else 0 for i in range(0,len(s))]
acc = list(itertools.accumulate(ac))
for i in lr: print(acc[i[1]-1]-acc[i[0]-1])
### BUGGY CODE ###

n = int(input())

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

q = int(input())

for i in range(q):
    
    b,c = map(int, input().split())
    
    if b in a:
        index = [i for i, x in enumerate(a) if x == b]
        
        if len(index) == n:
            a = [c] * n
        else:  
            for i in index:
                a[i] = c

    print(sum(a))

### FIXED CODE ###

n = int(input())

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

q = int(input())

#初期化

a_dic ={}
ans = 0

for i in a:
    if i not in a_dic:
        a_dic[i] = 1
    else:
        a_dic[i] += 1
    
    ans += i

#print(ans)
#a_sorted = sorted(a)
for i in range(q):
    #ans = 0
    b,c = map(int, input().split())
    #print(a_dic)
    
    if b in a_dic:
        if c not in a_dic:
            a_dic[c] = a_dic[b]

        else:
            tmp_c = a_dic[c]
            tmp_c += a_dic[b]
            a_dic[c] = tmp_c
        tmp_a = (c-b) * a_dic[b]
        a_dic.pop(b)
        ans += tmp_a
    print(ans)
### BUGGY CODE ###

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

def didWin(idx, c, tt):
    if c == 'r' and tt[idx] == 's':
        return True
    if c == 's' and tt[idx] == 'p':
        return True
    if c == 'p' and tt[idx] == 'r':
        return True
    return False

def solve(idx):
    ans = 0
    tt = []
    dp = [[0] * 4 for _ in range(n + 1)]

    for i in range(idx, n, k):
        tt.append(t[i])
    # print('tt:', tt)

    l = len(tt)

    prev = None
    for i in range(len(tt)):
        # Case rock
        if didWin(i, 'r', tt):
            dp[i + 1][0] = max(dp[i][1], dp[i][2]) + r
        else:
            dp[i + 1][0] = max(dp[i][1], dp[i][2])
        # Case scissors
        if didWin(i, 's', tt):
            dp[i + 1][1] = max(dp[i][0], dp[i][2]) + s
        else:
            dp[i + 1][1] = max(dp[i][0], dp[i][2])
        # Case paper
        if didWin(i, 'p', tt):
            dp[i + 1][2] = max(dp[i][0], dp[i][1]) + p
        else:
            dp[i + 1][2] = max(dp[i][0], dp[i][1])

    # print('dp:', dp)
    # print('max:', max(dp[l][0], dp[l][1], dp[l][2]))
    return max(dp[l][0], dp[l][1], dp[l][2])

ans = 0
for i in range(k):
    ans += solve(i)

print(ans)

### FIXED CODE ###

import math
n, k = map(int, input().split())
r, s, p = map(int, input().split())
t = input()

def didWin(idx, c):
    if c == 'r' and t[idx] == 's':
        return True
    if c == 's' and t[idx] == 'p':
        return True
    if c == 'p' and t[idx] == 'r':
        return True
    return False

def solve(mod):
    # print('mod:',mod)
    # tt = []
    #
    # for i in range(mod, n, k):
    #     tt.append(t[i])
    # print('tt:', tt)
    # print('n/k:', n / k)

    # tt[i] = t[i * k + mod]
    l = math.ceil((n - mod) / k)
    # print('l:', l)
    dp = [[0] * 4 for _ in range(l + 1)]

    for i in range(l):
        # Case rock
        if didWin(i * k + mod, 'r'):
            dp[i + 1][0] = max(dp[i][1], dp[i][2]) + r
        else:
            dp[i + 1][0] = max(dp[i][1], dp[i][2])
        # Case scissors
        if didWin(i * k + mod, 's'):
            dp[i + 1][1] = max(dp[i][0], dp[i][2]) + s
        else:
            dp[i + 1][1] = max(dp[i][0], dp[i][2])
        # Case paper
        if didWin(i * k + mod, 'p'):
            dp[i + 1][2] = max(dp[i][0], dp[i][1]) + p
        else:
            dp[i + 1][2] = max(dp[i][0], dp[i][1])

    # print('dp:', dp)
    # print('max:', max(dp[l][0], dp[l][1], dp[l][2]))
    return max(dp[l][0], dp[l][1], dp[l][2])

ans = 0
for i in range(k):
    ans += solve(i)

print(ans)
### BUGGY CODE ###

import math
def cmb(n, r):
    if n==0:
        return 0

    if n==1 and r==2:
        return 0
    if n==2 and r==2:
        return 1

    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


def main():
    import sys
    from collections import defaultdict

    N=int(sys.stdin.readline())
    AL=list(map(int,sys.stdin.readline().split()))
    dic=defaultdict(int)
    for a in AL:
        dic[a]+=1


    K=[cmb(v,2) for k,v in dic.items()]
    total=sum(K)

    for i in range(N):
        a=dic[AL[i]]
        print(total-cmb(a,2)+cmb(a-1,2))

main()

### FIXED CODE ###



def cmb(n,r):#r==2固定
    return n*(n-1)//2

def main():
    import sys
    from collections import defaultdict

    N=int(sys.stdin.readline())
    AL=list(map(int,sys.stdin.readline().split()))
    dic=defaultdict(int)
    for a in AL:
        dic[a]+=1


    K=[cmb(v,2) for k,v in dic.items()]
    total=sum(K)

    for i in range(N):
        a=dic[AL[i]]
        print(total-cmb(a,2)+cmb(a-1,2))

main()
### BUGGY CODE ###

a = int(input())
b = input().split()
c = 1
for i in range(a):
    if b[i] == 0:
        c = 0
        break

    c = c*int(b[i])

if c > 1000000000000000000:
    print(-1)
else:
    print(c)

### FIXED CODE ###

a = int(input())
b = input().split()
c = 1
for i in range(a):
    if int(b[i]) == 0:
        c = 0

if c == 1:
    for i in range(a):
        c = c*int(b[i])
        if c > 1000000000000000000:
            break

if c > 1000000000000000000:
    print(-1)
else:
    print(c)
### BUGGY CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
mod = int(1e+9 + 7)
a = sorted(a)

def main():
    kai = [1]*(n+1)
    gyaku = [1]*(n+1)
    
    for i in range(2, n+1):
        kai[i] = kai[i-1]*i % mod
        gyaku[i] = gyaku[i-1]*pow(i, mod-2, mod) %mod
    
    answer = 0
    for i in range(n-k+1):
        for j in range(i+k-1,n):
            answer = (answer + ((a[j] - a[i])%mod * kai[j-i-1] *gyaku[j-i-1-(k-2)])%mod * gyaku[k-2])%mod
    
    if k == 1:
        print(0)
    else:
        print(answer)
        
if __name__ == "__main__":
    main()

### FIXED CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
mod = int(1e+9 + 7)
a = sorted(a)

kai = [1]*(n+1)
gyaku = [1]*(n+1)

for i in range(2, n+1):
    kai[i] = kai[i-1]*i % mod
    gyaku[i] = gyaku[i-1]*pow(i, mod-2, mod) %mod

answer = 0
for i in range(k-1,n):
    answer = (answer + a[i] * kai[i] * gyaku[(i)-(k-1)] * gyaku[k-1]) % mod

answer2 = 0
for i in range(n-k+1):
    answer2 = (answer2 + a[i] * kai[n-i-1] * gyaku[(n-i)-k] * gyaku[k-1]) % mod


if k == 1:
    print(0)
else:
    print((answer - answer2)%mod)
### BUGGY CODE ###

import numpy as np
n,k,q = map(int,input().split())
data = np.array([k for i in range(n)])

  
for i in range(q):
  answer = int(input()) - 1
  data -= 1
  data[answer] += 1
  
for i in data:
  print('Yes' if i > 0 else 'No')
  

### FIXED CODE ###

n,k,q = map(int,input().split())
parti = range(n)
res = [0 for i in parti]
data = [0 for i in parti]

for i in range(q):
  answer = int(input()) - 1
  data[answer] += 1

for key,val in enumerate(data):
  if val + k - q > 0:
    index = int(key)
    res[index] = 1
for i in res:
  print('Yes' if i else 'No')