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

n=int(input())
s=input()
ans=0
def z_algo(S):
    N=len(S)
    A=[0]*N
    i=1;j=0
    A[0]=l=len(S)
    while i<l:
        while i+j<l and S[j]==S[i+j]:
            j+=1
        if not j:
            i+=1
            continue
        A[i]=j
        k=1
        while l-i>k<j-A[k]:
            A[i+k]=A[k]
            k+=1
        i+=k;j-=k
    return A

for i in range(n):
    l=z_algo(s[i:])
    m=len(l)
    for j in range(m):
        ans=max(ans,min(j,l[j]))
print(ans)







### FIXED CODE ###

n=int(input())
s=input()
ans=0
def z_algo(S):
    N=len(S)
    A=[0]*N
    i=1;j=0
    A[0]=l=len(S)
    while i<l:
        while i+j<l and S[j]==S[i+j]:
            j+=1
        if not j:
            i+=1
            continue
        A[i]=j
        k=1
        while l-i>k<j-A[k]:
            A[i+k]=A[k]
            k+=1
        i+=k;j-=k
    return A

for i in range(n):
    l=z_algo(s[i:])
    m=len(l)
    for j in range(m):
        ans=max(ans,min(j,l[j]))
print(ans)
### BUGGY CODE ###

import itertools
k,s=map(int,input().split())
count=0
ans=list(itertools.product(list(range(k+1)),repeat=3))
for i in ans:
    if sum(i)==s:
        count+=1
print(count)

### FIXED CODE ###

k,s=map(int,input().split())
count=0
for x in range(k+1):
    for y in range(k+1):
        if 0<=s-x-y<=k:
            count+=1
print(count)
### BUGGY CODE ###

n = int(input())
ls = [int(input()) for _ in range(n)]
l = ls.copy()

for i in range(n):
    ls = l.copy()
    ls.pop(i)
    print(max(ls))


### FIXED CODE ###

n = int(input())
ls = [int(input()) for _ in range(n)]
sls = sorted(ls)

for i in range(n):
    if sls[-1] == ls[i]:
        print(sls[-2])
    else:
        print(sls[-1])
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
b=[0]*n
for i , j in enumerate(a):
    b[i]=j+i+1
c=[0]*n
q=[]
ans=0
for i , j in enumerate(a):
    c[i]=1+i-j
from collections import Counter
def combination(n, r):
    a = 1
    b = 1
    for i in range(r):
        a *= (n - i)
        b *= (i + 1)
    return a // b
cc=Counter(c)
bb=Counter(b)
for i,j in bb.items():
    for k,l in cc.items():
        if i==k:
            ans+=j*l

print(ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
b=[0]*n
for i , j in enumerate(a):
    b[i]=j+i+1
c=[0]*n
q=[]
ans=0
for i , j in enumerate(a):
    c[i]=1+i-j
from collections import Counter
def combination(n, r):
    a = 1
    b = 1
    for i in range(r):
        a *= (n - i)
        b *= (i + 1)
    return a // b
cc=Counter(c)
bb=Counter(b)
f=bb&cc
for i in f.keys():
    ans+=bb[i]*cc[i]

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

n = int(input())
lst = list(map(int,input().split()))
for i in range(n):
  print(lst.count(i + 1))

### FIXED CODE ###

n = int(input())
lst = list(map(int,input().split()))
lst2 = [0 for i in range(n)]
for i in range(n - 1):
  x = lst[i]
  lst2[x - 1] = lst2[x - 1] + 1
for i in range(n):
  print(lst2[i])
### BUGGY CODE ###

s = input()

n = len(s)
ans = 0
flag = 0
for i in range(n):
    flag = 0
    for j in range(i+1,n):
        if flag != 0:
            flag -= 1
            continue
        if int(s[i:j+1]) % 2019 == 0:
            ans += 1
            flag = 3
print(ans)


### FIXED CODE ###

s = input()
#s = '9' * 200000

mod = [1] + [0]*2018
t = 0
a = 1
n = len(s)
s = s[::-1]
for i in range(n):
    t = (t + int(s[i])*a) % 2019
    a = a * 10 % 2019
    mod[t] += 1
ans = 0
for i in range(2019):
    ans += mod[i]*(mod[i]-1)//2
print(ans)
### BUGGY CODE ###

S=list(input())

while S[0]=="W":
	S.pop(0)

n=S.count("W")

c=0
for i in range(n):
	c+= S.index("W")-i
	S[S.index("W")]="X"

print(c)

### FIXED CODE ###

S=list(input())

#while S[0]=="W":
#	S.pop(0)

#n=S.count("W")

c=0
x=0
for i in range(len(S)):
	if S[i]=="B": x+=1
	else: c+=x

print(c)
### BUGGY CODE ###

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

def pop_count(b):
	return sum(map(int, list(bin(b)[2:])))

def dfs(x, p, bit):
	for v, j in adj[x]:
		if v == p or paths[p][v] > 0:
			continue
		paths[p][v] = bit + (1<<j)
		dfs(v, p, bit + (1<<j))
	return

for i in range(n):
	dfs(i, i, 0)

cons = []
m = int(input())
for _ in range(m):
	u, v = map(int, input().split())
	cons.append(paths[u-1][v-1])

ans = 1<<(n-1)
for b in range(1, 1<<m):
	use = 0
	pop = pop_count(b) % 2
	for i in range(m):
		if (b>>i) & 1 == 0:
			continue
		use |= cons[i]
	if pop:
		ans -= 1 << (n-1 - pop_count(use))
	else:
		ans += 1 << (n-1 - pop_count(use))

print(ans)

### FIXED CODE ###

import sys
def input():
	return sys.stdin.readline()[:-1]

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

def pop_count(b):
	return sum(map(int, list(bin(b)[2:])))

def dfs(x, p, bit):
	for v, j in adj[x]:
		if v == p or paths[p][v] > 0:
			continue
		paths[p][v] = bit + (1<<j)
		dfs(v, p, bit + (1<<j))
	return

for i in range(n):
	dfs(i, i, 0)

#print(*paths, sep="\n")

cons = []
m = int(input())
for _ in range(m):
	u, v = map(int, input().split())
	cons.append(paths[u-1][v-1])

#print(cons)

uses = [0 for _ in range(1<<m)]
ans = 1<<(n-1)
for b in range(1, 1<<m):
	pop = pop_count(b) % 2
	cur = 0
	while not (1<<cur) & b:
		cur += 1
	use = uses[b - (1<<cur)] | cons[cur]
	uses[b] = use
	if pop:
		ans -= 1 << (n-1 - pop_count(use))
	else:
		ans += 1 << (n-1 - pop_count(use))

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

# Check Examples

#python 3.7.
# Check Examples

#python 3.7.1

n=int(input())
p=input().split()  
p=list(map(int,p))          
cnt=0
det=len([])

p=sorted(p)
for i in range(n):
	arc=p[i:]
	abc=p[:i]
	
	if det and len(arc)<=len(abc):
		cnt=p[i]-p[i-1]
		break
	if arc>abc:det=True

print (cnt)



### FIXED CODE ###

# Check Examples

#python 3.7.1

n=int(input())
p=input().split()  
p=list(map(int,p))          
cnt=0

p=sorted(p)

if p[n//2]!=p[(n//2)-1]:
	cnt=p[n//2]-p[(n//2)-1]



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

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


def is_prime(p, s):
    tmp = 0
    sum = 0
    for i in s:
        tmp = (tmp * 10 + i) % p
        if tmp == 0:
            sum += 1
    return sum


n = len(s)
cnt = 0

for i in range(n):
    cnt += is_prime(p, s[i:])

print(cnt)

### FIXED CODE ###


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


cnt = [0] * p
cnt[0] = 1
rem = 0
sum = 0

if p == 2 or p == 5:
    for i in range(n):
        if s[i] % p == 0:
            sum += i + 1

else:
    for i in range(n):
        rem = (int(s[-i - 1]) * pow(10, i, p) + rem) % p
        sum += cnt[rem]
        cnt[rem] += 1

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

n,k = map(int,input().split())
p = [int(i) for i in input().split()]

max = 0
j = n-k+1
s = []
for i in range(j):
    if max < sum(p[i:i+k]):
        s = p[i:i+k]
        max = sum(p[i:i+k])

def summ(i):
    return i*(i+1)/2

ss = 0


for i in s:
    ss += summ(i)/i

print(ss)

### FIXED CODE ###

n,k = map(int,input().split())
p = [int(i) for i in input().split()]


j = n-k
s = p[0:k]
max = sum(s)
su = max

for i in range(j):
    t = su+p[i+k]
    u = t-p[i]
    if max < u:
        max = t-p[i]
        s = p[i+1:i+1+k]

    su = u

def summ(i):
    return i*(i+1)/2

ss = 0


for i in s:
    ss += summ(i)/i

print(ss)
### BUGGY CODE ###

for i in range(10**18):
  b=[0,1,2]
  a=b.pop()
  x=a**2+a
a=1/0

### FIXED CODE ###

[print(-1) for i in range(10000)]
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)
I=lambda:map(int,input().split())
n,m=I()
g=[set() for _ in range(n+1)]
v=[1 for _ in range(n+1)]
v[1]=0

for _ in range(m):
  a,b=I()
  g[a]|={b}
  g[b]|={a}

def dfs(x):
  for j in g[x]:
    if v[j]:
      v[j]=0
      return dfs(j)+[j]
      break
  else:
    return []
z=dfs(1)+[1]+dfs(1)[::-1]
print(len(z))
print(*z)

### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)
I=lambda:map(int,input().split())
n,m=I()
g=[set() for _ in range(n+1)]
v=[1 for _ in range(n+1)]
v[1]=0

for _ in range(m):
  a,b=I()
  g[a].add(b)
  g[b].add(a)

def dfs(x):
  for j in g[x]:
    if v[j]:
      v[j]=0
      l=dfs(j)
      l.append(j)
      return l
      break
  else:
    return []
z=dfs(1)+[1]+dfs(1)[::-1]
print(len(z))
print(*z)
### BUGGY CODE ###

def gcd(a,b): 
    if a == 0: 
        return b 
    return gcd(b % a, a) 
  
def lcm(a,b): 
    return (a*b) // gcd(a,b) 
  
n = int(input())
arr = input()   # takes the whole line of n numbers
a = list(map(int,arr.split(' ')))
l = a[0]
ans = 0
for i in range(n):
    l = lcm(l, a[i])
for i in range(n):
    ans = ans + l//a[i]
print(ans%1000000007)

### FIXED CODE ###

def gcd(a,b): 
    if a == 0: 
        return b 
    return gcd(b % a, a) 
  
def lcm(a,b): 
    return (a*b) // gcd(a,b) 
  
n = int(input())
arr = input()   # takes the whole line of n numbers
a = list(map(int,arr.split(' ')))
l = a[0]
ans = 0
for i in range(n):
    l = lcm(l, a[i])
for i in range(n):
    ans = ans + l//a[i]
print(ans%1000000007)
### BUGGY CODE ###

from collections import deque
import sys
input = sys.stdin.readline

H ,W = map(int, input().split())#↓H行数 →W列数
#List = [list(str(input())) for i in range(H)]
#H=3
#W=3
#List=[['.', '.', '.'], ['.', '#', '.'], ['.', '.', '.']]
cheak=[['0' for i in range(W)] for j in range(H)]

q = deque([])
List=[]
for h in range(H):
    qwe=list(str(input()))
    List.append(qwe)
    for w in range(W):
        if qwe[w]=='#':
            cheak[h][w]='1'
            q.append([h,w])
#print(List)
#print(cheak)
move=[[1,0],[-1,0],[0,1],[0,-1]]
num=-1
#print(q)
while q:
    for rt in range(len(q)):
        i=q.popleft()
        for u in move:
            if 0<=i[0]+u[0]<=H-1 and 0<=i[1]+u[1]<=W-1 and cheak[i[0]+u[0]][i[1]+u[1]]=='0':
                q.append([i[0]+u[0],i[1]+u[1]])
                cheak[i[0]+u[0]][i[1]+u[1]]='1'
    #print(cheak)
    num+=1
print(num)  

### FIXED CODE ###

from collections import deque
import sys
input = sys.stdin.readline

H ,W = map(int, input().split())#↓H行数 →W列数
List = [list(str(input())) for i in range(H)]
#H=3
#W=3
#List=[['.', '.', '.'], ['.', '#', '.'], ['.', '.', '.']]
cheak=[['0' for i in range(W)] for j in range(H)]

q = deque([])

for h in range(H):
    for w in range(W):
        if List[h][w]=='#':
            cheak[h][w]='1'
            q.append([h,w])
#print(List)
#print(cheak)
move=[[1,0],[-1,0],[0,1],[0,-1]]
num=-1
#print(q)
while q:
    for rt in range(len(q)):
        i=q.popleft()
        for u in move:
            if 0<=i[0]+u[0]<=H-1 and 0<=i[1]+u[1]<=W-1 and cheak[i[0]+u[0]][i[1]+u[1]]=='0':
                q.append([i[0]+u[0],i[1]+u[1]])
                cheak[i[0]+u[0]][i[1]+u[1]]='1'
    #print(cheak)
    num+=1
print(num)
### BUGGY CODE ###

import collections
n = int(input())
s = [input() for i in range(n)]
p = collections.Counter(s)
res = sorted(p.items(), key=lambda x: x[1],reverse = True)

keys = []
#keys = [i for i,m in p.items() if m == p.values()]
for i,m in res:
  if(m == max(p.values())):
    keys.append(i)
  else:
    break
keys=sorted(keys)
for i in range(len(keys)):
  print(keys[i])

### FIXED CODE ###

import collections
n = int(input())
s = [input() for i in range(n)]
p = collections.Counter(s)
res = sorted(p.items(), key=lambda x: x[1],reverse = True)
 
keys = []
#keys = [i for i,m in p.items() if m == p.values()]
u = max(p.values())
for i,m in res:
  if(m == u):
    keys.append(i)
  else:
    break
keys=sorted(keys)
for i in range(len(keys)):
  print(keys[i])
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N, W = map(int, input().split())
w_v = [[int(x) for x in input().split()] for _ in range(N)]
dp = [[0] * (W+1) for _ in range(N)]

for i in range(w_v[0][0], W+1):
    dp[0][i] = w_v[0][1]
    
for i in range(1, N):
    for w in range(W+1):
        if w - w_v[i][0] < 0:
            dp[i][w] = dp[i-1][w]
        else:
            dp[i][w] = max(dp[i-1][w], dp[i-1][w - w_v[i][0]] + w_v[i][1])

print(dp[N-1][W])

### FIXED CODE ###

import numpy as np


N, W = map(int, input().split())
w_v = [[int(_) for _ in input().split()] for _ in range(N)]
dp = np.zeros([N, W+1], dtype=int)
dp[0][w_v[0][0]:] = w_v[0][1]

for i in range(1, N):
    key = w_v[i][0]
    dp[i][:key] = dp[i-1][:key]
    dp[i][key:] = np.maximum(dp[i-1][key:], dp[i-1][:-key] + w_v[i][1])

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

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

left, right = map(int, input().split())
ans = set(range(left, right+1))
               
for i in range(m-1):
  left, right = map(int, input().split())
  set_temp = set(range(left, right+1))
  ans = ans & set_temp
print(len(ans))

### FIXED CODE ###

n, m = map(int, input().split())
min_num = 0
max_num = 10**5
           
for i in range(m):
  min_temp, max_temp = map(int, input().split())
  if min_temp > min_num:
    min_num = min_temp
  if max_temp < max_num:
    max_num = max_temp
print(max(max_num - min_num + 1, 0))
### BUGGY CODE ###

import sys #追加

n=int(input())
sys.setrecursionlimit(10**6*2)

s=input()
X=int(s,2)
ans=[]

ans_memo=[0]*(2**10)
#print(ans_memo)
ans_memo[1]=1
ans_memo[2]=1

def DEF(x,cnt):
    global ans_memo
    #print(x,cnt,ans_memo)
    if x==0:
        return 0
    if x<2**10:    
        if ans_memo[x]!=0:
            return ans_memo[x]
        else:
            if x%(str(bin(x)).count("1"))==0:
                ans_memo[x]=1
                return 1
            else:
                tmp=DEF(x%(str(bin(x)).count("1")),cnt+1)+1
                ans_memo[x]=tmp
                return tmp
    else:
        if x%(str(bin(x)).count("1"))==0:
            return 1
        else:
            tmp=DEF(x%(str(bin(x)).count("1")),cnt+1)+1
            return tmp


ans=[]

for i in range(n):
    tmp=2**(n-i-1)
    tmp_num=X
    #1の時
    if tmp&tmp_num:
        tmp_num-=tmp
        #print(bin(tmp_num),n-i-1)
        ans.append(DEF(tmp_num,0))
        
    else:
        tmp_num+=tmp
        #print(bin(tmp_num),n-i-1)
        ans.append(DEF(tmp_num,0))

#print(ans_memo)

for item in ans:
    print(item)
            









### FIXED CODE ###

def popcount(x):
    return bin(x).count("1")

n=int(input())
s=input()
X=int(s,2)

one_cnt=popcount(X)

modp=X%(one_cnt+1)
modm=X%(one_cnt-1) if one_cnt-1!=0 else 0

for i in range(n):
    if s[i]=="1":
        if one_cnt-1==0:
            print(0)
            continue
        else:
            num=(modm-pow(2,n-i-1,one_cnt-1))%(one_cnt-1)
    else:
        num=(modp+pow(2,n-i-1,one_cnt+1))%(one_cnt+1)

    #print(i,"num",num)
    cnt=1
    while num!=0:
        num=num%popcount(num)
        cnt+=1
    print(cnt)
### BUGGY CODE ###

input()
a = map(int, input().split())
ret = 1
for x in a:
  ret *= x
if ret > 1e+18:
  print(-1)
else:
  print(ret)

### FIXED CODE ###

_, *a = map(int, open(0).read().split())
ret = 1
for x in sorted(a):
  ret *= x
  if ret > 10 ** 18:
    ret = -1; break
    
print(ret)
### BUGGY CODE ###

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

A = sorted([a for a in A if a < K])
N = len(A)

l, r = -1, N
while r - l > 1:
    m = (l + r) // 2
    B = A[:m] + A[m + 1:]

    if sum(B) < K - A[m]:
        l = m
        continue

    dp = [False] * (K + 1)
    dp[0] = True
    for i in range(N - 1):
        for j in range(K + 1)[::-1]:
            if B[i] > j:
                continue
            else:
                dp[j] = dp[j - B[i]]

    if 1 in dp[K-A[m]:K]:
        r = m
    else:
        l = m

print(r)


### FIXED CODE ###

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

A = sorted([a for a in A if a < K])
N = len(A)
S = sum(A)

# あああああああああああああああああああ＼(＾o＾)／
if S < K:
    print(N)
    exit()
elif S - A[0] < N:
    print(0)
    exit()

l, r = -1, N
while r - l > 1:
    m = (l + r) // 2
    B = A[:m] + A[m + 1:]

    if S - A[m] < K - A[m]:
        l = m
        continue

    dp = [False] * (K + 1)
    dp[0] = True
    flg= False

    for i in range(N - 1):
        for j in range(K + 1)[::-1]:
            if B[i] > j:
                continue
            else:
                dp[j] = dp[j - B[i]]

            if dp[j] and K-A[m] <= j < K:
                r = m
                flg = True
                break
        if flg:
            flg = False
            break
    else:
        l = m

print(r)
### BUGGY CODE ###

from collections import deque
N, M = map(int, input().split())

G = {k: [] for k in range(N+1)}
r = [True]*(N+1)
for _ in range(N+M-1):
    a, b = map(int, input().split())
    r[b] = False
    # 有向グラフ
    G[a].append(b)

for i in range(1, N+1):
    if r[i] is True:
        root = i


P = [-1]*(N+1)
P[root] = 0
dist = [-1]*(N+1)

que = deque([(root, 0, 0)])


while que:
    ci, pi, d = que.popleft()
    if d > dist[ci]:
        P[ci] = pi
        dist[ci] = d

    for ni in G[ci]:
        que.append((ni, ci, d+1))

print(*P[1:], sep='\n')


### FIXED CODE ###

from collections import deque, defaultdict

N, M = map(int, input().split())
ab = []
for _ in range(N + M - 1):
    ab.append(tuple(map(int, input().split())))

in_cnt = defaultdict(int)
rev = defaultdict(list)
outs = defaultdict(list)
for a, b in ab:
    in_cnt[b - 1] += 1
    outs[a - 1].append(b - 1)
    rev[b - 1].append(a - 1)

res = []
queue = deque([i for i in range(N) if in_cnt[i] == 0])
while queue:
    v = queue.popleft()
    res.append(v)
    for v2 in outs[v]:
        in_cnt[v2] -= 1
        if in_cnt[v2] == 0:
            queue.append(v2)

order = [i for i, v in sorted(enumerate(res), key=lambda x: x[1])]

ans = [0] * N
ans[res[0]] = 0
for v in res[:0:-1]:
    ans[v] = max([(order[v2], v2) for v2 in rev[v]])[1] + 1

for a in ans:
    print(a)
### BUGGY CODE ###

def main():
  import sys
  input = sys.stdin.readline
  n, k = map(int, input().split())
  arr = list(map(int, input().split()))
  dp = [1000000000] * n
  dp[0] = 0
  for i in range(1, n):
    for j in range(max(0, i - k), i):
      dp[i] = min(dp[i], dp[j] + abs(arr[i] - arr[j]))
  print(dp[-1])
main()  

### FIXED CODE ###

def main():
  import sys
  input = sys.stdin.readline
  n, k = map(int, input().split())
  arr = list(map(int, input().split()))
  dp = [1000000000] * n
  dp[0] = 0
  for i in range(1, n):
    for j in range(max(0, i - k), i):
      dp[i] = min(dp[i], dp[j] + abs(arr[i] - arr[j]))
  print(dp[-1])
main()
### BUGGY CODE ###

import math
N = int(input())
A = [int(s) for s in input().split()]
B = [0 for i in range(N)]
idx = []
for i in range(N):
  B[A[i]-1] += 1
  if B[A[i]-1] == 2:
    idx.append(A[i]-1)

from operator import mul
from functools import reduce

def nCr(n,r):
    if n == 1:
        return 0
    r = min(n-r,r)
    if r == 0:
        return 1
    ov = reduce(mul, range(n, n-r, -1))
    un = reduce(mul, range(1, r+1))
    return ov // un

Cs = []
C = []
Ctot = 0
for j in idx:
  if B[j]-1 >= 2:
    Cs.append(nCr(B[j]-1, 2))
  else:
    Cs.append(0)
  tmp = nCr(B[j], 2)
  C.append(tmp)
  Ctot += tmp
for i in range(N):
  current_idx = A[i]-1
  if current_idx in idx:
    count = Ctot + Cs[idx.index(current_idx)]-C[idx.index(current_idx)]
  else:
    count = Ctot
  print(count)

### FIXED CODE ###

N = int(input())
A = [int(s) for s in input().split()]
B = [0 for i in range(N)]
def nC2(n):
  return n*(n-1)//2
for i in range(N):
  B[A[i]-1] += 1
Ctot = 0
for i in range(N):
  Ctot += nC2(B[i])
for i in range(N):
  current_idx = A[i]-1
  if B[current_idx] == 1:
    count = Ctot
  else:
    count = Ctot + nC2(B[current_idx]-1) - nC2(B[current_idx])
  print(count)
### BUGGY CODE ###

X,Y,Z,K=[int(i) for i in input().split(" ")]
A=[int(i) for i in input().split(" ")]
B=[int(i) for i in input().split(" ")]
C=[int(i) for i in input().split(" ")]

AB=[]

A=sorted(A,reverse=True)[:K:]
B=sorted(B,reverse=True)[:K:]
C=sorted(C,reverse=True)[:K:]
for a in A:
    for b in B:
        AB.append(a+b)

AB=sorted(AB,reverse=True)[:K:]

ABC=[]
for ab in AB:
    for c in C:
        ABC.append(ab+c)

ABC=sorted(ABC,reverse=True)[:K:]


for abc in ABC:
    print(abc)


### FIXED CODE ###

import heapq
X,Y,Z,K=[int(i) for i in input().split(" ")]
A=[int(i) for i in input().split(" ")]
B=[int(i) for i in input().split(" ")]
C=[int(i) for i in input().split(" ")]

AB=[]
for a in A:
    for b in B:
        AB.append(a+b)

AB=heapq.nlargest(K,AB)
ABC=[]
for ab in AB:
    for c in C:
        ABC.append(ab+c)

for cake in heapq.nlargest(K,ABC):
    print(cake)
### BUGGY CODE ###

class DisjointSet():
    def __init__(self, n):
        self._p = [x for x in range(n)]
        self._size = [-1 for x in range(n)]
    
    def find(self, p):
        while p != self._p[p]:
            p = self._p[p]
        return p

    def union(self, p, q):
        pp, qq = self.find(p), self.find(q)
        if pp != qq:
            if self.size(pp) > self.size(qq):
                self._p[qq] = self._p[pp]
                self._size[pp] += self._size[qq]
            else:
                self._p[pp] = self._p[qq]
                self._size[qq] += self._size[pp]
    
    def size(self, p):
        return self._size[self.find(p)]


n, m = [int(x) for x in input().split()]
b =  [tuple(map(lambda x: int(x) - 1, input().split())) for _ in range(m)]
b.reverse()
r = []
t = n*(n-1)//2
ds = DisjointSet(n)
for q, p in b:
  r.append(t)
  qq, pp = ds.find(p), ds.find(q)
  if pp != qq:
    t -= ds.size(pp) * ds.size(qq)
  ds.union(p, q)
for x in reversed(r):
  print(x)

### FIXED CODE ###

class Unionfind():
    def __init__(self, progsize):
        self.table = [-1 for _ in range(progsize)]
        self.size = [1 for _ in range(progsize)]

    def find(self, x):
        while(self.table[x] >= 0):
            x = self.table[x]
        return x

    def union(self, x, y):
        xl = self.find(x)
        yl = self.find(y)
        if xl != yl:
            if self.table[xl] <= self.table[yl]:
                self.table[yl] = xl
                self.table[xl] -= 1
                self.size[xl] += self.size[yl]
            else:
                self.table[xl] = yl
                self.table[yl] -= 1
                self.size[yl] += self.size[xl]

n, m = map(int, input().split())
bridge = [tuple(map(int, input().split())) for _ in range(m)]
bridge.reverse()
uf = Unionfind(n)
cur = n * (n-1) // 2
ans = [cur]
for a, b in bridge:
    ap = uf.find(a-1)
    bp = uf.find(b-1)
    if ap != bp:
        cur -= uf.size[ap] * uf.size[bp]
    uf.union(a-1, b-1)
    ans.append(cur)
for a in reversed(ans[0:m]):
    print(a)
### BUGGY CODE ###

h,w,d = map(int,input().split())
a = []
branch = dict()
for i in range(1,h*w+1):
	branch[i] = []
for i in range(h):
	atemp = list(map(int,input().split()))
	for k in range(w):
		branch[atemp[k]].append(i+1)
		branch[atemp[k]].append(k+1)
	a.append(atemp)
q = int(input())
l = []
r = []
for i in range(q):
	ltemp,rtemp = map(int,input().split())
	l.append(ltemp)
	r.append(rtemp)

for i in range(q):
	ans = 0
	now = l[i]
	while now != r[i]:
		ans += abs(branch[now][0]-branch[now+d][0])+abs(branch[now][1]-branch[now+d][1])
		now = now+d
	print(ans)

### FIXED CODE ###

h,w,d = map(int,input().split())
branch = dict()
for i in range(1,h*w+1):
	branch[i] = []
for i in range(h):
	atemp = list(map(int,input().split()))
	for k in range(w):
		branch[atemp[k]].append(i+1)
		branch[atemp[k]].append(k+1)

q = int(input())
l = []
r = []
for i in range(q):
	ltemp,rtemp = map(int,input().split())
	l.append(ltemp)
	r.append(rtemp)

calc = dict()
for i in range(d):
	calc[i+1] = []
for i in range(1,d+1):
	now = i
	calc[i].append(0)
	k = 0
	while now+d <= h*w:
		calc[i].append(calc[i][k]+abs(branch[now][0]-branch[now+d][0])+abs(branch[now][1]-branch[now+d][1]))
		now = now+d
		k += 1

for i in range(q):
	div = l[i]//d
	if l[i]%d != 0:
		sur = l[i]%d
	else:
		sur = d
	ansdiv = r[i]//d
	if sur == d:
		print(calc[sur][ansdiv-1]-calc[sur][div-1])
	else:
		print(calc[sur][ansdiv]-calc[sur][div])