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

from heapq import heappop, heappush
n = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

# B < A の要素が存在すればFalse
if any([b < a for a, b in zip(A, B)]):
  print(-1)
  exit()

# B > A の index をheapqueに入れる。
que = []
for i, (a, b) in enumerate(zip(A, B)):
  if b > a:
    heappush(que,(-b, i)) 

ans = 0
while que:
  val, idx = heappop(que)
  val *= -1
  l = idx - 1
  r = idx + 1 if idx != n - 1 else 0
  ac = B[l] + B[r]
  if val > ac:
    cnt = min((val ) // ac, (val - A[idx]) // ac)
    heappush(que, (-(val - cnt * ac), idx))
    ans += cnt
    B[idx] -= cnt * ac 

if A == B:
  print(ans)
else:
  print(-1)

### FIXED CODE ###

from heapq import heapify, heappop, heappush

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

q = [(-val, i) for i, val in enumerate(b) if val != a[i]]
heapify(q)

# 3print(q)

cnt = 0

while q:
  bval, i = heappop(q)
  bval = - bval - a[i]
  dv, bval = divmod(bval, b[i - 1] + b[(i + 1) % n])
#   print(dv, bval,i)
  if dv == 0:
    print(-1)
    exit()
  bval += a[i]
  b[i] = bval
  cnt += dv
  if bval != a[i]:
    heappush(q, (- bval, i))
print(cnt)
### BUGGY CODE ###

from bisect import bisect_left

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

table = [[-1 for _ in range(n)] for _ in range(n)]
c = [0 for _ in range(n)]

for i in range(n):
    for j in range(n):
        table[i][j] = a[i] ^ a[j]
        if i != j:
            k = bisect_left(a, table[i][j])
            if k < len(c) and a[k] == table[i][j]:
                c[k] += 1
if all((cc == 2 for cc in c)):
    print('Yes')
else:
    print('No')



### FIXED CODE ###

from collections import Counter

N= int(input())

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

x = Counter(a)

ok = False
if len(x) == 3 and len(a) % 3 == 0:
    for i in a:
        if x[i] != len(a) // 3:
            break
    else:
        w = 0
        for j in x:
            w ^= j
        if w == 0:
            ok = True
elif len(x) == 1:
    if x.get(0) is not None:
        ok = True
elif len(x) == 2 and len(a) % 3 == 0:
    if x.get(0) is not None and x[0] == len(a) // 3:
        ok = True

if ok:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

class Dijkstra():
    """ ダイクストラ法
    重み付きグラフにおける単一始点最短路アルゴリズム

    * 使用条件
        - 負のコストがないこと
        - 有向グラフ、無向グラフともにOK

    * 計算量はO(E*log(V))

    * ベルマンフォード法より高速なので、負のコストがないならばこちらを使うとよい
    """
    class Edge():
        """ 重み付き有向辺 """
        def __init__(self, _to, _cost):
            self.to = _to
            self.cost = _cost

    def __init__(self, V):
        """ 重み付き有向辺
        無向辺を表現したいときは、_fromと_toを逆にした有向辺を加えればよい

        Args:
            V(int): 頂点の数
        """
        self.G = [[] for i in range(V)]  # 隣接リストG[u][i] := 頂点uのi個目の隣接辺
        self._E = 0  # 辺の数
        self._V = V  # 頂点の数

    @property
    def E(self):
        """ 辺数
        無向グラフのときは、辺数は有向グラフの倍になる
        """
        return self._E

    @property
    def V(self):
        """ 頂点数 """
        return self._V

    def add(self, _from, _to, _cost):
        """ 2頂点と、辺のコストを追加する """
        self.G[_from].append(self.Edge(_to, _cost))
        self._E += 1

    def shortest_path(self, s):
        """ 始点sから頂点iまでの最短路を格納したリストを返す
        Args:
            s(int): 始点s
        Returns:
            d(list): d[i] := 始点sから頂点iまでの最短コストを格納したリスト。
                     到達不可の場合、値はfloat("inf")
        """
        import heapq
        que = []  # プライオリティキュー（ヒープ木）
        d = [float("inf")] * self.V
        d[s] = 0
        heapq.heappush(que, (0, s))  # 始点の(最短距離, 頂点番号)をヒープに追加する

        while len(que) != 0:
            cost, v = heapq.heappop(que)
            # キューに格納されている最短経路の候補がdの距離よりも大きければ、他の経路で最短経路が存在するので、処理をスキップ
            if d[v] < cost: continue

            for i in range(len(self.G[v])):
                # 頂点vに隣接する各頂点に関して、頂点vを経由した場合の距離を計算し、今までの距離(d)よりも小さければ更新する
                e = self.G[v][i]  # vのi個目の隣接辺e
                if d[e.to] > d[v] + e.cost:
                    d[e.to] = d[v] + e.cost  # dの更新
                    heapq.heappush(que, (d[e.to], e.to))  # キューに新たな最短経路の候補(最短距離, 頂点番号)の情報をpush
        return d

def main():
    N,M=map(int,input().split())
    key=[]
    for i in range(0,M):
        a,b=map(int,input().split())
        c=list(map(int,input().split()))
        s=sum(2**(c[j]-1) for j in range(0,b))
        key.append((s,a))


    node=2**N
    djk=Dijkstra(node)
    for i in range(0,M):
        for j in range(0,node):
            s,a=key[i]
            djk.add(j,s|j,a)

    d=djk.shortest_path(0)
    if d[node-1]==float('inf'):
        print(-1)
    else:
        print(d[node-1])

if __name__=="__main__":
    main()

### FIXED CODE ###

N,M=map(int,input().split())
key=[]
cost=[]
for i in range(0,M):
    a,b=map(int,input().split())
    c=list(map(int,input().split()))
    s=sum(2**(c[j]-1) for j in range(0,b))
    key.append(s)
    cost.append(a)

node=2**N

dp=[[10**10 for i in range(0,node)] for j in range(0,M)]

for i in range(0,M):
    dp[i][node-1]=0
#i:何番までか j:手に入れた鍵
for i in range(0,M):
    for j in range(1,node):
        k=node-1-j
        if i==0:
            if k|key[0]==node-1:
                dp[0][k]=cost[0]
        else:
            dp[i][k]=min(dp[i-1][k],dp[i-1][k|key[i]]+cost[i])

if dp[M-1][0]>=10**10:
    print(-1)
else:
    print(dp[M-1][0])
### BUGGY CODE ###

import numpy as np

k,q=map(int,input().split())
D=np.array(list(map(int,input().split())),dtype="i8")

for i in range(q):
    n,x,m=map(int,input().split())
    mD=D%m #元の列のmodを取る
    a=(n-1)//k
    b=(n-1)%k
    ans=0
    ans+=(len(mD)-np.count_nonzero(mD))*a #0の数
    ans+=len(mD[:b])-np.count_nonzero(mD[:b]) #0の数
    cnt=x%m+sum(mD)*a+sum(mD[:b]) #増えた量
    ans+=cnt//m
    print(n-1-ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

k,q=map(int,input().split())
D=list(map(int,input().split()))
A=[]
for i in range(q):
    n,x,m=map(int,input().split())
    mD=list(map(lambda i: i%m, D)) #元の列のmodを取る
    ans=0
    cnt=x%m
    a=(n-1)//k
    b=(n-1)%k
    for d in mD[:b]: #mod kで余る部分
        if d==0:
            ans+=a+1
        cnt+=d*(a+1)
    for d in mD[b:]: #余らない部分
        if d==0:
            ans+=a
        cnt+=d*a
    ans+=cnt//m
    print(n-1-ans)
### BUGGY CODE ###

from collections import Counter

def main():
    N,P = map(int,input().split())
    S = input()[::-1]
    ans = 0
    if P == 2 or P == 5:
        for i,s in enumerate(S):
            if int(s) % P == 0:
                ans += N-i
    else:
        D = [0] * (N+1)
        for i in range(N):
            D[i] =  int(S[:i+1][::-1]) % P
        C = Counter(D)
        for i in C.values():
            ans += i*(i-1)//2
    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    N,P = map(int,input().split())
    S = input()[::-1]
    ans = 0
    if P == 2 or P == 5:
        for i,s in enumerate(S):
            if int(s) % P == 0:
                ans += N - i
    else:
        mods = [0] * P
        mods[0] = 1
        current = 0
        x = 1
        for s in S:
            current = (current + x * int(s)) % P
            ans += mods[current % P]
            mods[current % P] += 1
            x = x * 10 % P
    print(ans)

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

n = int(input())
a = list(map(int, input().split(" ")))
cnt=0
for i in range(n):
    for j in range(i,n):
        if a[i]-1==j and a[j]-1==i:
            cnt += 1
print(cnt)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split(" ")))
cnt=0
for i in range(n):
    if a[a[i]-1]-1==i:
        cnt += 1
print(int(cnt/2))
### BUGGY CODE ###

n = int(input())
a = [[int(x) for x in input().split()] for _ in range(n)]


def bit(n, k): return (n >> k) & 1


dp = [0]*(1 << n)
flag = [False]*(1 << n)


def dfs(s):
    if flag[s] or bin(s).count("1") <= 1:
        return dp[s]
    flag[s] = True
    tmp = 0
    for i in range(n):
        for j in range(i+1, n):
            if bit(s, i) & bit(s, j):
                tmp += a[i][j]
    score = tmp
    t = (s-1) & s
    while 0 < t:
        score = max(score, dfs(t)+dfs(s ^ t))
        t = (t-1) & s
    dp[s] = score
    return dp[s]


print(dfs(2**n-1))


### FIXED CODE ###

n = int(input())
a = [[int(x) for x in input().split()] for _ in range(n)]


def bit(n, k): return (n >> k) & 1


dp = [0]*(1 << n)
flag = [False]*(1 << n)


def dfs(s):
    if flag[s] or bin(s).count("1") <= 1:
        return dp[s]
    flag[s] = True
    tmp = 0
    for i in range(n):
        for j in range(i+1, n):
            if bit(s, i) & bit(s, j):
                tmp += a[i][j]
    score = tmp
    t = (s-1) & s
    while 0 < t:
        score = max(score, dfs(t)+dfs(s ^ t))
        t = (t-1) & s
    dp[s] = score
    return dp[s]


print(dfs(2**n-1))
### BUGGY CODE ###

# seishin.py
from collections import deque
N = int(input())
*P, = map(int, input().split())
MOD = 10**9 + 7

G = [[] for i in range(N+1)]
U = [0]*(N+1)
C = [0]*(N+1)
for i, p in enumerate(P):
    G[p].append(i+1)
    U[i+1] = u = U[p]+1
    C[u] += 1
Q = [None]*(N+1)
PP = {}
def pp(k):
    if k not in PP:
        PP[k] = p = pow(2, k, MOD)
        return p
    return PP[k]
L = [0]*(N+1)

sz = L.__getitem__
for i in range(N, -1, -1):
    g = G[i]
    if not g:
        continue

    # 子ノードのdequeを集める
    g.sort(key=sz, reverse=1)
    k = len(g)
    e = [pp(k) - k, k, 0]

    g0 = g[0]
    L[i] = L[g0] + 1
    if L[g0] == 0:
        Q[i] = deque([e])
        continue
    Q[i] = R = Q[g0]
    for j in g[1:]:
        S = Q[j]
        if not S:
            break

        # dequeの小さい方から大きい方へマージする処理
        for (a0, a1, a2), r in zip(S, R):
            b0, b1, b2 = r
            r[0] = a0*b0 % MOD
            r[1] = (a0*b1 + a1*b0) % MOD
            r[2] = ((a0+a1)*b2 + a1*b1) % MOD

    # a0 <- a2
    for r in R:
        r[0] += r[2]
        r[2] = 0
    R.appendleft(e)
print((pp(N) + sum(pp(N+1-c) * a1 % MOD for (a0, a1, a2), c in zip(Q[0], C[1:]))) % MOD)

### FIXED CODE ###

# seishin.py
from collections import deque
N = int(input())
*P, = map(int, input().split())
MOD = 10**9 + 7

G = [[] for i in range(N+1)]
U = [0]*(N+1)
C = [0]*(N+1)
for i, p in enumerate(P):
    G[p].append(i+1)
    U[i+1] = u = U[p]+1
    C[u] += 1
Q = [None]*(N+1)
PP = {}
def pp(k):
    if k not in PP:
        PP[k] = p = pow(2, k, MOD)
        return p
    return PP[k]
L = [0]*(N+1)

ept = []
sz = L.__getitem__
for i in range(N, -1, -1):
    g = G[i]
    if not g:
        continue

    # 子ノードのdequeを集める
    g.sort(key=sz, reverse=1)
    k = len(g)
    e = [pp(k) - k, k, 0]

    g0 = g[0]
    L[i] = L[g0] + 1
    if L[g0] == 0:
        Q[i] = deque([e])
        continue
    Q[i] = R = Q[g0]
    if k > 1:
        # a0 <- a2
        for s, r in zip(Q[g[1]] or ept, R):
            r[0] += r[2]; r[2] = 0

        for j in g[1:]:
            S = Q[j]
            if not S:
                break

            # dequeの小さい方から大きい方へマージする処理
            for (a0, a1, a2), r in zip(S, R):
                b0, b1, b2 = r; a0 += a2
                r[0] = a0*b0 % MOD
                r[1] = (a0*b1 + a1*b0) % MOD
                r[2] = ((a0+a1)*b2 + a1*b1) % MOD
    R.appendleft(e)
print((pp(N) + sum(pp(N+1-c) * a1 % MOD for (a0, a1, a2), c in zip(Q[0], C[1:]))) % MOD)
### BUGGY CODE ###

n,q=map(int,input().split())
c=list(map(int,input().split()))
for _ in range(q):
  l,r=map(int,input().split())
  print(len(set(c[l-1:r])))

### FIXED CODE ###

def segfunc(x,y):
  return x+y
ide_ele=0
class SegTree():
  def __init__(self,init_val,segfunc,ide_ele):
    n=len(init_val)
    self.segfunc=segfunc
    self.ide_ele=ide_ele
    self.num=1<<(n-1).bit_length()
    self.tree=[ide_ele]*2*self.num
    for i in range(n):
      self.tree[self.num+i]=init_val[i]
    for i in range(self.num-1,0,-1):
      self.tree[i]=self.segfunc(self.tree[2*i], self.tree[2*i+1])
  def update(self,k,x):
    k+=self.num
    self.tree[k]=x
    while k>1:
      self.tree[k>>1]=self.segfunc(self.tree[k],self.tree[k^1])
      k>>=1
  def query(self,l,r):
    res=self.ide_ele
    l+=self.num
    r+=self.num
    while l<r:
      if l&1:
        res=self.segfunc(res,self.tree[l])
        l+=1
      if r&1:
        res=self.segfunc(res,self.tree[r-1])
      l>>=1
      r>>=1
    return res
n,q=map(int,input().split())
c=list(map(int,input().split()))
st=SegTree([0]*n,segfunc,ide_ele)
lr=[[]for _ in range(n+1)]
for i in range(q):
  l,r=map(int,input().split())
  lr[r]+=[(l,i)]
d={}
for i in range(n):
  if not d.get(c[i]):d[c[i]]=[i]
  else:d[c[i]]+=[i]
for i in d:
  st.update(d[i][-1],1)
ans=[0]*q
r=n
while r>0:
  if lr[r]:
    l,i=lr[r].pop()
    ans[i]=st.query(l-1,r)
  while not lr[r] and r>0:
    if d[c[r-1]]:st.update(d[c[r-1]].pop(),0)
    if d[c[r-1]]:st.update(d[c[r-1]][-1],1)
    r-=1
for i in ans:print(i)
### BUGGY CODE ###

n,a=map(int,input().split())
x=sorted(list(map(int,input().split())))
for i in range(n):
    x[i]-=a
cnt=0
for i in range(2**n):
    ans=0
    for j in range(n):
        if ((i>>j)&1):
            ans+=x[j]
    if ans==0:
        cnt+=1
print(cnt-1)

### FIXED CODE ###

n,a=map(int,input().split())
X=[int(i)-a for i in input().split()]

memo={0:1}
for x in X:
    for k,v in list(memo.items()):
        memo[x+k]=memo.get(x+k,0)+v
print(memo[0]-1)
### BUGGY CODE ###

N,K=map(int,input().split())
A=list(map(int,input().split()))
ans=0
if N<K:
  pass
else:
  for i in range(N-K):
    ans+=min(A)
    A.remove(min(A))  
print(ans)

### FIXED CODE ###

N,K=map(int,input().split())
ans=0
if N<=K:
  pass
else:
  A=list(map(int,input().split()))
  A.sort()
  ans=sum(A[:N-K])
print(ans)
### BUGGY CODE ###

from math import floor

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

max_v = 0
for i in range(n + 1):
  t = floor(a * i / b) - a * floor(i / b)
  if t > max_v:
    max_v = t
print(max_v)

### FIXED CODE ###

from math import floor

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

max_v = 0
if n < b:
  max_v = floor(a * n / b)
else:
  if b != 1:
    for i in range(b - 1, n + 1, b):
      j = 0
      t = floor(a * i / b) - a * j
      if t > max_v:
        max_v = t
      j += 1
print(max_v)
### BUGGY CODE ###

import copy

N = int(input())

input_list = []
tmplist = []

for i in range(N):
  input_list.append(int(input()))

for i in input_list:
  tmplist = copy.copy(input_list)
  tmplist.remove(i)
  print(max(tmplist))

### FIXED CODE ###

N = int(input())
 
input_list = []
tmplist = []
 
for i in range(N):
  input_list.append(int(input()))

sorted_list = sorted(input_list)

first_val = sorted_list[-1]
second_val = sorted_list[-2]

for i in input_list:
  if i == first_val:
    print(second_val)
  else:
    print(first_val)
### BUGGY CODE ###

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

for i in range(N):
    ans = ans * A[i]
'''
for i in range(N):
    if ans > 10**18+1:
        break
    else:
        ans = ans * A[i]
'''
if ans > 10**18:
    print(-1)
else:
    print(ans)


### FIXED CODE ###

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

for i in range(N):
    if ans > 10**18+1:
        break
    else:
        ans = ans * A[i]

if 0 in A:
    print(0)
elif ans > 10**18:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

n,q = [int(x) for x in input().split()]
G = [[] for _ in range(n)]
for _ in range(n-1):
    a,b = [int(x)-1 for x in input().split()]
    G[a].append(b)
    G[b].append(a)
count = [0]*n
for _ in range(q):
    a,b = [int(x) for x in input().split()]
    a -= 1
    count[a] += b

from collections import deque
ans = [0]*n
q = deque()
used = [0]*n
q.append(0)
used[0]=1
ans[0] += count[0]

while q:
    p = q.popleft()
    for i in G[p]:
        if used[i]!=1:
            used[i]=1
            ans[i]+=ans[p]+count[i]
            q.append(i)

an = ""
for i in ans:
    an += str(i) + " "
print(an)

### FIXED CODE ###

n,q = [int(x) for x in input().split()]
G = [[] for _ in range(n)]
for _ in range(n-1):
    a,b = [int(x)-1 for x in input().split()]
    G[a].append(b)
    G[b].append(a)
count = [0]*n
for _ in range(q):
    a,b = [int(x) for x in input().split()]
    a -= 1
    count[a] += b

from collections import deque
ans = [0]*n
q = deque()
used = [0]*n
q.append(0)
used[0]=1
ans[0] += count[0]

while q:
    p = q.popleft()
    for i in G[p]:
        if used[i]!=1:
            used[i]=1
            ans[i]+=ans[p]+count[i]
            q.append(i)

for i in ans:
    print(i,end=" ")
### BUGGY CODE ###

N = int(input())
A = list(input().split())
B = [int(a) for a in A]
x = 10**9+7
summation = sum((B[i] * (sum(B[j] for j in range(i+1,N)))) for i in range(N-1)) % x
print(summation)

### FIXED CODE ###

N = int(input())
A = list(input().split())
B = [int(a) for a in A]
x = 10**9+7
summation1 = sum(B) ** 2
summation2 = sum(b ** 2 for b in B)
summation = ((summation1 - summation2) // 2) % x
print(summation)
### BUGGY CODE ###

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

dp=[[0 for _ in range(p)] for _ in range(n+1)]
for i in range(1,n+1):
    dp[i][int(s[i-1])%p]=1
    for j in range(p):
        dp[i][(j*10+int(s[i-1]))%p]+=dp[i-1][j]
print(sum([dp[i][0] for i in range(1,n+1)]))

### FIXED CODE ###

#E
from collections import Counter
n,p=map(int,input().split())
s=input()
cnt=0

if p==2 or p==5:
    for i in range(n):
        if int(s[i])%p==0:
            cnt+=i+1
else:
    U=[0]*(n+1)
    for i in range(n,0,-1):
        U[i-1]=(int(s[i-1])*pow(10,n-i,p)+U[i])%p
    #print(U)
    C=Counter(U)
    for c in C.values():
        cnt+=c*(c-1)//2

print(cnt)
### BUGGY CODE ###

#!/usr/bin/env python
import sys

def main():
    S = sys.stdin.readline().rstrip()
    N = len(S)
    s1 = ""
    s2 = ""
    for i in range(N):
        if i % 2 == 0:
            s1 = s1 + "1"
            s2 = s2 + "0"
        elif i % 2 == 1:
            s1 = s1 + "0"
            s2 = s2 + "1"

    ans = float("inf")
    tmp = 0
    for i, j in zip(S, s1):
        if i != j:
            tmp += 1
    ans = min(ans, tmp)
    tmp = 0
    for i, j in zip(S, s2):
        if i != j:
            tmp += 1
    ans = min(ans, tmp)
    print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python
import sys

def main():
    S = sys.stdin.readline().rstrip()
    N = len(S)

    ans = float("inf")
    tmp1 = 0
    tmp2 = 0
    for i in range(N):
        if i % 2 == 0:
            s1 = "1"
            s2 = "0"
            if S[i] != s1:
                tmp1 += 1
            elif S[i] != s2:
                tmp2 += 1
        elif i % 2 == 1:
            s1 = "0"
            s2 = "1"
            if S[i] != s1:
                tmp1 += 1
            elif S[i] != s2:
                tmp2 += 1
    print(min(tmp1, tmp2))

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

a,b,x = map(int,input().split())

count = 0
for i in range(a, b+1):
  if i % x == 0:
    count += 1

print(count)


### FIXED CODE ###

a,b,x = map(int, input().split())
print(b//x - (a-1)//x)
### BUGGY CODE ###

from functools import reduce
from math import gcd

K = int(input())
l = [0 for i in range(K**3)]

ans = 0

for i in range(1,K+1):
    num = [0, 0, 0]
    num[0] = i
    for k in range(1,K+1):
        num[1] = k
        for m in range(1,K+1):
            num[2] = m
            ans += reduce(gcd, num)


print(ans)

### FIXED CODE ###

from math import gcd

K = int(input())
ans = 0

for i in range(1,K+1):
    for k in range(1,K+1):
        b = gcd(i, k)
        for m in range(1,K+1):
            ans += gcd(b, m)

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

# from sys import stdin
import math


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


N = int(input())
A = list(map(int, input().split()))
# print(A)
d = {}
cnt = 0
for l in range(N):
    for i in range(N):
        if i != cnt:

            # else:
            d[A[i]] = d.get(A[i], 0)+1
    # print(d)
    # print(len(d))
    sum = 0
    for key,value in enumerate(d):
        # print(key,value)
        sum = sum+combinations_count(d.get(value, 0), 2)
    print(sum)
    d = {}
    cnt += 1


### FIXED CODE ###

# from sys import stdin
# import math
from functools import lru_cache


@lru_cache(maxsize=1000)
def combinations_count(n, r):
    if n < 2:
        return 0
    return n*(n-1)//2


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

d = {}
cnt = 0
for i in range(N):
    d[A[i]] = d.get(A[i], 0)+1
# print(d)
sum1 = 0
for key, value in enumerate(d):
    # print(key,value)
    sum1 = sum1+combinations_count(d.get(value, 0), 2)

for l in range(N):

    # print(d)
    # print(len(d))
    sum = 0
    sum = sum1-combinations_count(d.get(A[cnt], 0), 2)
    d[A[cnt]] = d.get(A[cnt], 0)-1
    sum = sum+combinations_count(d.get(A[cnt], 0), 2)
    # for key, value in enumerate(d):
    #     # print(key,value)
    #     sum = sum+combinations_count(d.get(value, 0), 2)
    print(sum)
    d[A[cnt]] = d.get(A[cnt], 0)+1
    # d = {}
    cnt += 1
### BUGGY CODE ###

N, M, K = map(int, input().split())
MOD = 10 ** 9 + 7

def comb(n, r) :
    if n - r < 0 or r < 0 :
        return 0
    
    r = min(n-r, r)

    a, b = 1, 1
    for i in range(r) :
        a *= (n - i) % MOD
        b *= (i + 1) % MOD

    return (a // b) % MOD

res = 0

for i in range(1, N + 1) :
    for j in range(1, M + 1) :
        if i > 1 and j > 1 :
            res += 2 * (N + 1 - i) * (M + 1 - j) * (i + j - 2)
        else :
            res += (N + 1 - i) * (M + 1 - j) * (i + j - 2)

res *= comb(N * M - 2, K - 2)

print(res % MOD)

### FIXED CODE ###

N, M, K = map(int, input().split())
MOD = 10 ** 9 + 7

def pow(x, n) :
    y = 1
    while n > 0 :
        if n & 1 :
            y = (y * x) % MOD
        x = (x * x) % MOD
        n >>= 1

    return y

def comb(n, r) :
    if n < r or n < 0 :
        return 0

    factorial = [0] * (n + 1)
    factorial[0] = 1

    for i in range(1, n + 1) :
        factorial[i] = (factorial[i-1] * i) % MOD

    return (factorial[n] * pow(factorial[n-r], MOD - 2) * pow(factorial[r], MOD - 2)) % MOD

res = 0

for i in range(N) :
    for j in range(M) :
        if i > 0 and j > 0 :
            res += 2 * (N - i) * (M - j) * (i + j)
        else :
            res += (N - i) * (M - j) * (i + j)

res *= comb(N * M - 2, K - 2)

print(res % MOD)
### BUGGY CODE ###

import sys
cnt2 = 0

def bubble_sort(a):
	cnt = 0
	n = len(a)
	for i in range(n):
		for j in range(n-1, i, -1):
			if a[j] < a[j-1]:
				tmp = a[j]
				a[j] = a[j-1]
				a[j-1] = tmp
				cnt += 1
	return cnt

def merge_sort(a):
	merge_sort_(a, 0, len(a))

def merge_sort_(a, left, right):
	if left + 1 < right:
		mid = int(left + (right - left) / 2)
		merge_sort_(a, left, mid)
		merge_sort_(a, mid, right)
		merge(a, left, mid, right)

def merge(a, left, mid, right):
	n1 = mid - left
	n2 = right - mid
	L = a[left:left+n1]
	R = a[mid:mid+n2]
	L.append(sys.maxsize)
	R.append(sys.maxsize)
	i = j = 0
	for k in range(left, right):
		if L[i] <= R[j]:
#			a[k] = L[i]
			i += 1
		else:
			if L[i] != sys.maxsize:
				global cnt2
				cnt2 += 1
#			a[k] = R[j]
			j += 1

def inversion(a):
	cnt = 0
	for i in range(n):
		for j in range(i+1, n):
			if a[i] > a[j]:
				cnt += 1
	return cnt
	
n = int(input())
a1 = list(map(int, input().split()))
a2 = [0] * n
for i in range(n):
	a2[i] = a1[i]

#cnt1 = bubble_sort(a1)
#print(a1)
#print(cnt1)
cnt2 = inversion(a2)
#print(a2)
print(cnt2)



### FIXED CODE ###

import sys
cnt = 0

def merge_sort(a, left, right):
	if left + 1 < right:
		mid = int(left + (right - left) / 2)
		merge_sort(a, left, mid)
		merge_sort(a, mid, right)
		merge(a, left, mid, right)

def merge(a, left, mid, right):
	n1 = mid - left
	n2 = right - mid
	L = a[left:left+n1]
	R = a[mid:mid+n2]
	L.append(sys.maxsize)
	R.append(sys.maxsize)
	i = j = 0
	for k in range(left, right):
		if L[i] <= R[j]:
			a[k] = L[i]
			i += 1
		else:
			if i < n1:
				global cnt
				cnt += n1 - i
			a[k] = R[j]
			j += 1
	
n = int(input())
a = list(map(int, input().split()))
merge_sort(a, 0, len(a))
print(cnt)