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

import numpy as np
N = int(input())
A = np.array(list(map(int, input().split(' '))))
num_sum = 0
remove_array = np.array([], int)
for i in range(N):
    c1 = np.count_nonzero(A == i + 1)
    c2 = np.count_nonzero(A == A[i])
    if c2 <= 1:
        remove_array = np.append(remove_array, 0)
    else:
        remove_array = np.append(remove_array, c2 - 1)
    num_sum += int(c1 * (c1 - 1) / 2)
print(*(num_sum - remove_array), sep='\n')


### FIXED CODE ###

'''
import numpy as np
N = int(input())
A = np.array(list(map(int, input().split(' '))))
num_sum = 0
remove_array = np.array([], int)
for i in range(N):
    c1 = np.count_nonzero(A == i + 1)
    c2 = np.count_nonzero(A == A[i])
    if c2 <= 1:
        remove_array = np.append(remove_array, 0)
    else:
        remove_array = np.append(remove_array, c2 - 1)
    num_sum += int(c1 * (c1 - 1) / 2)
print(*(num_sum - remove_array), sep='\n')
'''
import collections
N = int(input())
A = list(map(int, input().split()))
cnt = collections.Counter(A)
total = 0
for key in cnt.keys():
    total += cnt[key] * (cnt[key] - 1) // 2
for i in range(N):
    tmp = total
    tmp -= cnt[A[i]] * (cnt[A[i]] - 1) // 2
    tmp += (cnt[A[i]] - 1) * (cnt[A[i]] - 2) // 2
    print(tmp)
### BUGGY CODE ###

n=int(input())
l=list(map(int, input().split()))
l.sort()
count=0
for i in range(n-2):
	for j in range(i+1,n-1):
		k=j+1
		while k<n and l[k]<l[i]+l[j]: #whileでlist indexはみ出さないように注意
			count+=1
			k+=1
print(count)

### FIXED CODE ###

import bisect
n=int(input())
l=list(map(int, input().split()))
l.sort()

count=0
for i in range(n-2):
	for j in range(i+1,n-1):
		maxk=bisect.bisect_left(l,l[i]+l[j],j+1,n)-1
		count+=maxk-j
print(count)
### BUGGY CODE ###

# coding: utf-8

"""
20191116
"""

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


def fun():
    if K >= N:
        return abs(h[N-1]-h[0])

    cost = [abs(h[k]-h[0]) for k in range(K+1)] + [None for i in range(K+1, N)]

    for i in range(K+1, N):
        cost[i] = min([cost[i-k] + abs(h[i]-h[i-k]) for k in range(1, K+1)])

    return(cost[N-1])


print(fun())


### FIXED CODE ###

# coding: utf-8
 
"""
20191116
"""
 
N, K = map(int, input().split())
h = list(map(int, input().split()))
 
 
def fun():
    if K >= N:
        return abs(h[N-1]-h[0])
 
    cost = [abs(h[k]-h[0]) for k in range(K+1)] + [None for i in range(K+1, N)]
 
    for i in range(K+1, N):
        cost[i] = min([cost[i-k] + abs(h[i]-h[i-k]) for k in range(1, K+1)])
 
    return(cost[N-1])
 
 
print(fun())
### BUGGY CODE ###

import fractions
from functools import reduce
def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

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

lcm_A = lcm_list(A)
B = [None]*N
for i in range(N):
    B[i] = lcm_A//A[i]

print(int(sum(B)%(10**9+7)))

### FIXED CODE ###

import fractions
import functools
import sys

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

def lcm(*numbers):
    return functools.reduce(lcm_base, numbers, 1)
"""
def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)
"""
N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))

lcm_A = functools.reduce(lcm_base, A, 1)
B = [None]*N
B = [lcm_A//a for a in A]
#B[i] = lcm_A//A[i]

print(sum(B)%(10**9+7))
### BUGGY CODE ###

import sys
import numpy as np
sys.setrecursionlimit(10**6)
n,k = map(int,input().split())
h = list(map(int, input().split()))

dp = np.zeros(n)
dp[0] = 0
dp[1] = np.abs(h[0]-h[1])

for i in range(2,n):
     j = max(0,i-k)
     dp[i] = np.min([dp[l]+abs(h[i]-h[l]) for l in range(j,i)])

print(int(dp[n-1]))


### FIXED CODE ###

import numpy as np
N, K = (int(i) for i in input().split())  
h = np.array([int(i) for i in input().split()])
 
dp = np.empty(N, dtype='int')
 
for i in range(N):
  if i == 0:
    dp[i] = 0
  elif i - K < 0:
    dp[i] = np.min(np.abs(h[i] - h[:i]) + dp[:i])
  else:
    dp[i] = np.min(np.abs(h[i] - h[i-K:i]) + dp[i-K:i])
 
print(dp[N-1])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(2147483647)


n=int(input())

c={}
tree=[[] for _ in range(n)]

for _ in range(n-1):
    i,j,k=map(int,input().split())
    i-=1
    j-=1
    tree[i].append(j)
    tree[j].append(i)
    c[(i,j)]=k
    c[(j,i)]=k

result=[]
q,k=map(int,input().split())

memo=[-1]*n

def DEF(z,cnt):
    global memo,tree,c
    memo[z]=cnt
    for item in tree[z]:
        if memo[item]==-1:
            DEF(item,cnt+c[(item,z)])

DEF(k-1,0)
result=[]
for item in range(q):
    a,b=map(int,input().split())
    result.append(memo[a-1]+memo[b-1])

for item in result:
    print(item)







### FIXED CODE ###

import sys
sys.setrecursionlimit(2147483647)


n=int(input())

c={}
tree=[set([]) for _ in range(n)]

for _ in range(n-1):
    i,j,k=map(int,input().split())
    i-=1
    j-=1
    tree[i].add(j)
    tree[j].add(i)
    c[(min(i,j),max(i,j))]=k

result=[]
q,k=map(int,input().split())

memo=[-1]*n

def DEF(z,cnt):
    global memo,tree,c
    memo[z]=cnt
    for item in tree[z]:
        if memo[item]==-1:
            DEF(item,cnt+c[(min(item,z),max(item,z))])

DEF(k-1,0)
result=[]
for item in range(q):
    a,b=map(int,input().split())
    result.append(memo[a-1]+memo[b-1])

for item in result:
    print(item)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
R = [0] * (N + 1)
P = [1] * (N + 1)
mod = 10 ** 9 + 7

def power(x, y):
    if y == 0:
        return 1
    elif y == 1: 
        return x % mod
    elif y % 2 == 0: 
        return power(x, y//2)**2 % mod
    else: 
        return power(x, y//2)**2 * x % mod

def rev(a):
    return power(a, mod - 2)
    
for n in range(N + 1):
    R[n] = R[n - 1] + rev(n)
    if n != 0:
        P[n] = P[n - 1] * n
    
C = [(R[j] + R[N - j + 1] - 1) % mod for j in range(1, N + 1)]

print(sum([a * c for a, c in zip(C, A)]) * P[N] % mod)

### FIXED CODE ###

import numpy as np
N = int(input())
A = list(map(int, input().split()))
R = np.zeros(N + 1, dtype="int64")
P = np.ones(N + 1, dtype="int64")
mod = 10 ** 9 + 7

def rev(a):
    return pow(a, mod - 2, mod)
    
for n in range(N + 1):
    r = rev(n)
    R[n] = (R[n - 1] + r) % mod
    if n != 0:
        P[n] = (P[n - 1] * n) % mod

C = [(R[j] + R[N - j + 1] - 1) % mod for j in range(1, N + 1)]

res = 0
for i in range(N):
    res = (res + (A[i] * C[i]) % mod) % mod

print(res * P[N] % mod)
#print((sum([a * c % mod for a, c in zip(C, A)]) * P[N]) % mod)
### BUGGY CODE ###

s=input()
n=len(s)
k=int(input())
lst=list(s)
lst.sort()
ans=[]
for i in range(min(k,n)):
    a=lst[i]
    for j in range(n):
        if s[j]==a:
            for l in range(min(5,n-j)):
                ans.append(s[j:j+l+1])
ans.sort()
t=1
while t<len(ans):
    if ans[t]==ans[t-1]:
        ans.pop(t)
    else:
        t+=1
print(ans[k-1])

### FIXED CODE ###

s=input()
n=len(s)
k=int(input())
lst=list(s)
lst.sort()
ans=[]
for i in range(min(k,n)):
    a=lst[i]
    count=0
    for j in range(n):
        if s[j]==a:
            count+=1
            for l in range(min(5,n-j)):
                ans.append(s[j:j+l+1])
    if count>=5:
        break
ans.sort()
t=1
while t<len(ans):
    if ans[t]==ans[t-1]:
        ans.pop(t)
    else:
        t+=1
print(ans[k-1])
### BUGGY CODE ###

import sys
input = lambda: sys.stdin.readline()[:-1]
n,m=map(int,input().split())
a=list(map(int,input().split()))
data=[list(map(int,input().split())) for i in range(m)]
for b,c in data:
	a+=[c]*b
a.sort(reverse=True)
ans=sum(a[:n])
print(ans)


### FIXED CODE ###

import sys
input = lambda: sys.stdin.readline()[:-1]
n,m=map(int,input().split())
a0=list(map(int,input().split()))
data=[list(map(int,input().split())) for i in range(m)]
for i in a0:
	data.append([1,i])
data.sort(key=lambda tup:-tup[1])
ans=0
for num,val in data:
	if n>=num:
		n-=num
		ans+=val*num
	else:
		ans+=val*n
		break
print(ans)
### BUGGY CODE ###

import sys
# 整数の入力
N,M=list(map(int, input().split()))
p=[]
q=0
count=0
for i in range(0,M):
  p.append(list(map(int, input().split())))
for i in range(0,M):
  q+=p[i][0]-p[i][1]
if q%2==1:
  print("NO")
else:
  for j in range(1,min(100,M)):
    for i in range(0,M):
      if p[i][0]==j or p[i][1]==j:
        count+=1
    if count%2==1:
      print("NO")
      sys.exit()
  else: 
    print("YES")

### FIXED CODE ###

import sys
# 整数の入力
N,M=list(map(int, input().split()))
p=[]
for i in range(0,N):
  p.append(0)
for i in range(0,M):
  count=list(map(int, input().split()))
  p[count[0]-1]+=1
  p[count[1]-1]+=1
for i in range(0,M):
  if p[i]%2==1:
    print("NO")
    sys.exit()
print("YES")
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()
s = S[:2]
ans = 'AC'
lst=[s == ans]
for i in range(1, N-1):
    s = s[1:] + S[i + 1]
    lst.append(s == ans)

for _ in range(Q):
    a, b = map(int, input().split())
    res = 0
    for i in range(a - 1, b - 1):
        res += lst[i]
    print(res)


### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
s = S[:2]
ans = 'AC'
lst = [0]
count = 0
for i in range(N-1):
    s = S[i] + S[i + 1]
    count += (s == ans)
    lst.append(count)

for _ in range(Q):
    a, b = map(int, input().split())
    print(lst[b - 1] - lst[a - 1])
### BUGGY CODE ###

X, Y, Z, K = input().split()
X = int(X)
Y = int(Y)
Z = int(Z)
K = int(K)
A = [int(a) for a in input().split()]
B = [int(b) for b in input().split()]
C = [int(c) for c in input().split()]
AB = []
for a in range(len(A)):
    for b in range(len(B)):
        AB.append(A[a] + B[b])
AB = sorted(AB, reverse=True)
ABC = []
if K <= len(AB):
    k = K
else:
    k = len(AB)
for ab in range(k):
    for c in range(len(C)):
        ABC.append(AB[ab] + C[c])
ABC = sorted(ABC, reverse=True)
for i in range(K):
    print(ABC[i])

### FIXED CODE ###

X, Y, Z, K = [int(x) for x in input().split()]
A = [int(a) for a in input().split()]
B = [int(b) for b in input().split()]
C = [int(c) for c in input().split()]
A = sorted(A, reverse=True)
B = sorted(B, reverse=True)
C = sorted(C, reverse=True)
ABC = []
for a in range(len(A)):
    if a+1 > K:
        break
    for b in range(len(B)):
        if b+1 > K:
            break
        elif (a+1)*(b+1) > K:
            break
        for c in range(len(C)):
            if c+1 > K:
                break
            elif (a+1)*(c+1) > K:
                break
            elif (b+1)*(c+1) > K:
                break
            elif (a+1)*(b+1)*(c+1) > K:
                break
            ABC.append(A[a] + B[b] + C[c])
ABC = sorted(ABC, reverse=True)
for i in range(K):
    print(ABC[i])
### BUGGY CODE ###

import sys
import collections
sys.setrecursionlimit(1000000)
n, q = map(int, input().split())
cost = collections.deque([])
res = collections.deque([])
tree = collections.deque([])
level = collections.deque([])
parent = collections.deque([])
cache = collections.deque([])
for i in range(210000):
    res.append(0)
    tree.append(collections.deque([]))
    level.append(-1)
    parent.append(-1)
    cost.append(0)
    cache.append(-1)

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

for loop in range(q):
    p, x = map(int, input().split())
    cost[p] += x

def make_level(index, lev, pp):
    level[index] = lev
    parent[index] = pp
    for next in tree[index]:
        if level[next] != -1:
            continue
        parent[next] = index
        cost[next] += cost[index]
        make_level(next, lev + 1, index)

make_level(1, 0, -1)

res = list(map(str, cost))
print(" ".join(res[1:n+1]))


### FIXED CODE ###

edge = []
n, q = map(int, input().split())
for _ in range(n+100):
    edge.append([])
for _ in range(n-1):
    a,b = map(int, input().split())
    edge[a].append(b)
    edge[b].append(a)
res = [0] * (n+1)
cost = [0] * (n+1)
for _ in range(q):
    a,b = map(int, input().split())
    res[a] += b

import collections
q = collections.deque([[1, 0]])
used = [False] * (n+1)
while len(q) > 0:
    #print(q)
    curnode, cost = q.popleft()
    res[curnode] += cost
    used[curnode] = True
    for i in range(len(edge[curnode])):
        nnext = edge[curnode][i]
        if used[nnext] is True:
            continue
        else:
            q.append([nnext, res[curnode]])
res=res[1:]
print(" ".join(list(map(str, res))))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n,m= map(int,input().split())

B = []
C = [0]*n
ans = 0
pna = 0
for i in range(m):
    a,b= input().split()
    if ans == n:
        break
    if b=="AC":
        if a not in B :
            B.append(a)
            ans += 1
            pna += C[int(a)-1]
    else:
        C[int(a)-1] += 1 
print(ans,pna)

### FIXED CODE ###

N,M = [int(x) for x in input().split()]
count = [0]*N
ac = 0
wa = 0
ireta = []
for i in range(M):
    a,b = input().split()
    a = int(a)
    if b == "AC" and count[a-1] == 0:
        count[a-1] = 1
        ac += 1
    elif count[a-1] == 0:
        ireta.append(a)
        wa += 1
for i in range(len(ireta)):
    if count[ireta[i]-1] == 0:
        wa -= 1
print(ac,wa)
### BUGGY CODE ###

import math
n = int(input())
s = int(input())

result = -1
if n == s:
  result = n + 1
elif s > n:
  pass
else:
  sqrt_n = math.floor(math.sqrt(n))
  for b in range(2, sqrt_n + 1):
    temp_n = n
    temp_b = 0
    while temp_n >= b:
      temp_b += temp_n % b
      temp_n = temp_n // b
    if temp_b + temp_n == s:
      result = b
      break
  if result == -1:
    for quot in range(sqrt_n, 0, -1):
      if n - s % quot != 0:
        b = (n - s) // quot + 1
        temp_n = n
        temp_b = 0
        while temp_n >= b:
          temp_b += temp_n % b
          temp_n = temp_n // b
        if temp_b + temp_n == s:
          result = b
          break
print(result)

### FIXED CODE ###

import math
n = int(input())
s = int(input())

result = -1
if n == s:
  result = n + 1
elif s > n:
  pass
else:
  temp_sqrt_n = math.floor(math.sqrt(n))
  for b in range(2, temp_sqrt_n + 1):
    temp_n = n
    temp_b = 0
    while temp_n >= b:
      temp_b += temp_n % b
      temp_n = temp_n // b
    if temp_b + temp_n == s:
      result = b
      break
  if result == -1:
    temp_sqrt_n = math.floor(math.sqrt(n - 1))
    for quot in range(temp_sqrt_n, 0, -1):
      if n - s % quot != 0:
        b = (n - s) // quot + 1
        if quot + n % b == s:
          result = b
          break
print(result)
### BUGGY CODE ###

#!/usr/bin/env python3

n, m = map(int, input().split())
h = list(map(int, input().split()))
not_good = []
for i in range(m):
    a, b = map(int, input().split())
    if h[a - 1] > h[b - 1]:  # bはダメ
        if b not in not_good:
            not_good.append(b)
    elif h[a - 1] == h[b - 1]:
        if a not in not_good:
            not_good.append(a)
        if b not in not_good:
            not_good.append(b)
    else:
        if a not in not_good:
            not_good.append(a)
ans = 0
not_good = list(set(not_good))
for i in range(1, n + 1):
    if i not in not_good:
        ans += 1
        # print(i, end=" ")
print(ans)


### FIXED CODE ###

#!/usr/bin/env python3
n, m = map(int, input().split())
h = list(map(int, input().split()))
not_good = []
for i in range(m):
    a, b = map(int, input().split())
    if h[a - 1] > h[b - 1]:  # bはダメ
        not_good.append(b)
    elif h[a - 1] == h[b - 1]:
        not_good.append(a)
        not_good.append(b)
    else:
        not_good.append(a)
ans = 0
not_good = list(set(not_good))
not_good.sort()
# print(not_good)
idx = 0
for i in range(1, n + 1):
    if i < not_good[idx]:
        ans += 1
        # print(i, end=" ")
    elif i == not_good[idx]:
        idx += 1
        if idx == len(not_good):
            ans += n - i
            break
    else:
        pass
print(ans)
### BUGGY CODE ###

N,Q = map(int, input().split())
import copy
import sys

sys.setrecursionlimit(10**6)
es = {}
for i in range(N-1):
    a,b = map(int, input().split())
    a,b = a-1, b-1
    if a in es:
        es[a].append(b)
    else:
        es[a] = [b]


point_root = [0] * N
query = [None]
for i in range(Q):
    p,x = map(int, input().split())
    point_root[p-1] += x 
point_root = tuple(point_root)
ans = [0] * N
visited = [False] * N

def solve(node, point):
    
    ans[node] += point
    visited[node] = True
    #print("aa", *ans, visited)
    if all(visited) == True:
        print(*ans)
        exit()

    if es.get(node, None) != None:
        for i in es[node]:
            solve(i, point+point_root[i])
solve(0, point_root[0])

### FIXED CODE ###

N,Q = map(int, input().split())
import copy
import sys

sys.setrecursionlimit(10**6)
es = [[] for i in range(N)]

for i in range(N-1):
    a,b = map(int, input().split())
    a,b = a-1, b-1
    es[a].append(b)
    es[b].append(a)


point = [0] * N

for i in range(Q):
    p,x = map(int, input().split())
    point[p-1] += x 

ans = [0] * N
ans[0] = point[0] # 一番上の根なのでこれだけ
visited = [False] * N
visit_cnt = 1
from collections import deque
nexts = deque([0])
while len(nexts) >= 1:
    now = nexts.popleft()
    visited[now] = True

    for next in es[now]:
        if visited[next] == True:
            continue
        nexts.append(next)
        ans[next] = ans[now] + point[next]


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

from functools import reduce
from fractions import gcd


def least_common_multiple(iter):
    '''
    最小公倍数を返す
    '''
    lcm = lambda x, y: x*y//gcd(x, y)
    return reduce(lcm, iter)


N = int(input())
A = list(map(int, input().split()))
# 全て同じ値
if len(set(A)) == 1:
    print(N)
    exit()
l = least_common_multiple(A)
ans = 0
MOD = 10**9+7
for a in A:
    ans = (ans + l // a) % MOD
print(ans)


### FIXED CODE ###

from fractions import gcd


N = int(input())
A = list(map(int, input().split()))
lcm = lambda x, y: x*y//gcd(x, y)
l = 1
for a in A:
    l = lcm(l, a)
ans = 0
MOD = 10**9+7
for a in A:
    ans += l // a
print(ans % MOD)
### BUGGY CODE ###

n=int(input())
arr=list(map(int,input().split()))
ans=0
for i in range(1,n):
    m=0
    c=0
    for j in range(i,0,-1):
       
        if arr[j-1]>m:
            m=arr[j-1]
        
    if arr[i]<m:
        c+=m-arr[i]
    ans+=c
print(ans)

### FIXED CODE ###

n=int(input())
arr=list(map(int,input().split()))
c=0
for i in range(1,n):
    if arr[i]<arr[i-1]:
        c+=arr[i-1]-arr[i]
        arr[i]+=arr[i-1]-arr[i]
        
print(c)
### BUGGY CODE ###

H,W,K=map(int,input().split())
S=[[int(s) for s in input()] for i in range(H)]

ans=1000000
for i in range(2**(H-1)):
    tmp=0
    L=[]
    for j in range(H-1):
        if i>>j&1:
            L.append(j)
    tmp+=len(L)
    L.append(H-1)
    c=[0]*len(L)
    for k in range(W):
        h=0
        c1=[0]*len(L)
        for l in range(len(L)):
            for m in range(h,L[l]+1):
                c1[l]+=S[m][k]
            h=L[l]+1
        p=0
        for l in range(len(L)):
            if c1[l]>K:
                p=2
                break
            elif c[l]+c1[l]>K:
                p=1
            else:
                c[l]+=c1[l]
        if p==2:
            break
        elif p==1:
            c=[i for i in c1]
            tmp+=1
    else:
        ans=min(ans,tmp)
print(ans)

### FIXED CODE ###

H,W,K=map(int,input().split())
S=[[int(s) for s in input()] for i in range(H)]

ans=1000000
for i in range(2**(H-1)):
    tmp=0
    L=[]
    for j in range(H-1):
        if i>>j&1:
            L.append(j)
    tmp+=len(L)
    L.append(H-1)
    c=[0]*len(L)
    for k in range(W):
        h=0
        c1=[0]*len(L)
        for l in range(len(L)):
            for m in range(h,L[l]+1):
                c1[l]+=S[m][k]
            h=L[l]+1
        p=0
        for l in range(len(L)):
            if c1[l]>K:
                p=2
                break
            elif c[l]+c1[l]>K:
                p=1
            else:
                c[l]+=c1[l]
        if p==2:
            break
        elif p==1:
            c=[i for i in c1]
            tmp+=1
    else:
        ans=min(ans,tmp)
print(ans)
### BUGGY CODE ###

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


def gcd(a, b):
    if a < b:
        return gcd(b, a)
    else:
        return a if b == 0 else gcd(b, a % b)


def lcm(a, b):
    return a * b // gcd(b, a%b)


L = lcm(N, M)

r = ["*" for i in range(L)]
s = 0
t = 0
f = False

s_step = L // N
t_step = L //M
i = 0
j = 0
while s < L:
    r[s] = S[i]
    s += s_step
    i += 1


while t < L:
    if r[t] == T[j]:
        t += t_step
        j += 1
        continue
    elif r[t] == "*":
        r[t] = T[j]
        t += t_step
        j += 1
    else:
        f = True
        break
if f:
    print(-1)
else:
    print(L)


### FIXED CODE ###

N, M = map(int, input().split())
S = input()
T = input()
# def gcd(a, b):
#     if a < b:
#         return gcd(b, a)
#     else:
#         return a if b == 0 else gcd(b, a % b)

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


L = lcm(N, M)

f = False

s_step = L // N
t_step = L // M
sL = lcm(s_step, t_step)
s = 0
t = 0

for i in range(0, L, sL):
    if i == 0:
        if S[i] == T[i]:
            continue
        else:
            f = True
            break
    else:
        s = i // s_step
        t = i // t_step
        if s > N - 1:
            break
        if t > M - 1:
            break
        if S[s] == T[t]:
            continue
        else:
            f = True
            break

if f:
    print(-1)
else:
    print(L)
### BUGGY CODE ###

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

V = [-1, 2, 5, 5, 4, 5, 6, 3, 7, 6]

memo = [-1] * (N + 1)
memo[N] = 0
while 1:
    next_memo = [-1] * (N + 1)
    next_memo[0] = memo[0]
    fin = True
    for i in range(N, 0, -1):
        if memo[i] < 0: continue

        for j in range(1, 10):
            if not j in A: continue
            idx = i - V[j]
            if idx >= 0:
                next_memo[idx] = max(next_memo[idx], memo[i] * 10 + j)
                if idx >0:
                    fin = False
    memo = next_memo
    if fin:
        break
print(memo[0])


### FIXED CODE ###

N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
A.sort(reverse=True)

V = [-1, 2, 5, 5, 4, 5, 6, 3, 7, 6]

dp = [-1e10] * (N + 1)
dp[0] = 0

for i in range(1, N + 1):
    # i 本で表せる最大の桁数を dp に求める
    l = [dp[i - V[j]] + 1 for j in A if i - V[j] >= 0]
    if l:
        dp[i] = max(l)
# 各桁の最大値を求めていく
n = N
while n > 0:
    for j in A:
        if n - V[j] < 0: continue
        if dp[n] == dp[n - V[j]] + 1:
            print(j, end='')
            n = n - V[j]
            break
print()
### BUGGY CODE ###

N=int(input())
A=[None]*N

for i in range(N):
    A[i]=int(input())

X=set(A)

Ans=0
for i in X:
    if A.count(i)%2==1:
        Ans+=1

print(Ans)


### FIXED CODE ###

N=int(input())
A=[None]*N

for i in range(N):
    A[i]=int(input())

Ans=0
A.sort()
A+=[-1]
j=1
for i in range(1,N+1):
    if A[i]==A[i-1]:
        j+=1
    else:
        if j%2==1:
            Ans+=1
        j=1

print(Ans)
### BUGGY CODE ###

a, b = map(int, input().split())
large = max(a, b)
ans = 0

for i in range((a+b)//2, large):
	if abs(a - i) == abs(b - i):
		ans = i
		break

if ans == 0:
	print("IMPOSSIBLE")
else:
	print(ans)


### FIXED CODE ###

a, b = map(int, input().split())
large = max(a, b)
ans = ((a + b) / 2)

if ans.is_integer():
	print(int(ans))
else:
	print("IMPOSSIBLE")
### BUGGY CODE ###

H, W, D = map(int, input().split())
A = [None]*(H*W+1)
for i in range(H):
    a = [int(i) for i in input().split()]
    for j, v in enumerate(a):
        A[v] = (i+1, j+1)

Q = int(input())
LR = [[int(i) for i in input().split()] for _ in range(Q)]
for l, r in LR:
    ans = 0
    while l < r:
        ans += abs(A[l][0]-A[l+D][0])+abs(A[l][1]-A[l+D][1])
        l += D
    print(ans)


### FIXED CODE ###

H, W, D = map(int, input().split())
A = [None]*(H*W+1)
for i in range(H):
    a = [int(i) for i in input().split()]
    for j, v in enumerate(a):
        A[v] = (i+1, j+1)

Q = int(input())
LR = [[int(i) for i in input().split()] for _ in range(Q)]

c = [0]*(H*W+1)
for i in range(1+D, W*H+1):
    c[i] = c[i-D]+abs(A[i][0]-A[i-D][0])+abs(A[i][1]-A[i-D][1])

for l, r in LR:
    print(c[r]-c[l])