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

n=int(input())
l=[0]+list(map(int,input().split()))
for i in range(1,1+n):
  l[i]+=l[i-1]
s=set(l)
ans=0
for i in s:
  a=l.count(i)
  ans+=((a-1)*a//2)
print(ans)

### FIXED CODE ###

n=int(input())
l=[0]+list(map(int,input().split()))
for i in range(1,n+1):
  l[i]+=l[i-1]
d={}
for i in l:
  if i not in d:
    d[i]=1
  else:
    d[i]+=1
ans=0
for a in d.values():
  ans+=a*(a-1)//2
print(ans)
### BUGGY CODE ###

N, M = map(int, input().split())
A = [0 for i in range(N + 2)]
A[0] = 0
A[1] = 1
brokun = []
for i in range(M):
    brokun.append(int(input()) + 1)
for i in range(2, N+2):
    if i in brokun:
        A[i] = 0
    else:
        A[i] = A[i-1]+ A[i-2]
        A[i] = A[i] % 1000000007
    #print(A)
print(A[N + 1])





### FIXED CODE ###

N, M = map(int, input().split())
A = [0 for i in range(N + 2)]
A[0] = 0
A[1] = 1
for i in range(M):
    a = int(input()) + 1
    A[a] = -1
for i in range(2, N+2):
    if A[i] ==  -1:
        A[i] = 0
    else:
        A[i] = A[i-1]+ A[i-2]
        A[i] = A[i] % 1000000007
    #print(A)
print(A[N + 1])
### BUGGY CODE ###

#!/usr/bin/python

import sys

def main(argv):
    line = sys.stdin.readline()
    while line:
        N = int(line.rstrip("\n"))

        timestamps = [0]
        for i in xrange(N - 1):
            if i > 0:
                timestamps.append(0)

            c, s, f = map(
              lambda i: int(i), sys.stdin.readline().rstrip("\n").split(" "))

            for i in xrange(len(timestamps)):
                if timestamps[i] <= s:
                    timestamps[i] = s + c
                else:
                    next_s = s
                    while timestamps[i] > next_s:
                        next_s = next_s + f
                    timestamps[i] = next_s + c

        for timestamp in timestamps:
            print timestamp
        print 0

        line = sys.stdin.readline()

if __name__ == "__main__":
    main(sys.argv)

### FIXED CODE ###

#!/usr/bin/python

import sys

def main(argv):
    line = sys.stdin.readline()
    while line:
        N = int(line.rstrip("\n"))

        timestamps = [0]
        for i in xrange(N - 1):
            if i > 0:
                timestamps.append(0)

            c, s, f = map(
              lambda i: int(i), sys.stdin.readline().rstrip("\n").split(" "))

            for i in xrange(len(timestamps)):
                if timestamps[i] <= s:
                    timestamps[i] = s + c
                else:
                    d = timestamps[i] % f
                    if d == 0:
                        timestamps[i] += c
                    else:
                        timestamps[i] += (f - d) + c

        for timestamp in timestamps:
            print timestamp
        print 0

        line = sys.stdin.readline()

if __name__ == "__main__":
    main(sys.argv)
### BUGGY CODE ###

#coding:UTF-8
from collections import defaultdict
d = defaultdict(dict)
def prime_table(n):
    l = [True for _ in range(n + 1)]
    i = 2
    while i * i <= n:
        j = i + i
        while j <= n:
            l[j] = False
            j += i
        i += 1
    table = []
    for i in range(n + 1):
        if l[i] and i >= 2:
            table.append(i)
            d[i] = True
    return table


Q = int(input())
prime_list = prime_table(10 ** 5)
for _ in range(Q):
    count = 0
    l, r = map(int,(input().split()))
    for p in prime_list:
        if l > p:
            continue
        if p > r:
            break
        if p == 2017 or d[((lambda x:(x + 1) // 2)(p))]:
            count += 1
    print(count)


### FIXED CODE ###

#coding:UTF-8

def is_prime(n):
    i = 2
    while i * i <= n:
        if n % i == 0:
            return False
        i += 1
    return True


mx = 10 ** 5
p = [0 for _ in range(mx + 1)]
for i in range(3, mx + 1):
    if i == 2017 or (is_prime(i) and is_prime((i + 1) // 2)):
        p[i] = 1
d = [0 for i in range(mx + 1)]
for i in range(3, mx + 1):
    d[i] += p[i] + d[i - 1]

Q = int(input())
for i in range(Q):
    l, r = map(int, input().split())
    print(d[r] - d[l - 1])
### BUGGY CODE ###

n,k=map(int, input().split())
a= list(map(int, input().split()))
maxans=0
for i in range(len(a)):
  ans=sum(a[i:i+k])
  maxans=max(ans,maxans)
print((maxans+k)/2)
  

### FIXED CODE ###

n,k=map(int, input().split())
a= list(map(int, input().split()))
l=[]
for i in range(len(a)):
  l.append((a[i]+1)/2)
maxans=sum(l[0:k])
ans=sum(l[0:k])
for i in range(len(l)-k):
  ans=ans+l[i+k]-l[i]
  maxans=max(ans,maxans)
 
print(maxans)
### BUGGY CODE ###

x,y,z=map(int,input().split())
while True:
  n=0
  if n*y+(n+1)*z>x:
    print(n-1)
    exit()
  n+=1

### FIXED CODE ###

x,y,z=map(int,input().split())
n=0
while True:
  if n*y+(n+1)*z>x:
    print(n-1)
    exit()
  n+=1
### BUGGY CODE ###

N, Q = map(int, input().split())
in_str_root = input()
l = []
r = []
for i in range(Q):
    in1, in2 = map(int, input().split())
    l.append(in1)
    r.append(in2)

for i in range(Q):
    in_str = in_str_root[l[i]-1:r[i]]
    AC = "AC"
    AC_count = in_str.count(AC)
    print(AC_count)

### FIXED CODE ###

N, Q = map(int, input().split())
in_str = input()
AC_count = []
r = [0]*(N+1)
for i in range(N):
    r[i+1] = r[i] + (1 if in_str[i:i+2] == "AC" else 0) 
    
    
for i in range(Q):
    in1, in2 = map(int, input().split())
    print(r[in2-1]-r[in1-1])
### BUGGY CODE ###

n=int(input())
f=[0]*10005
for x in range(1,n+1):
  for j in range(1,n+1):
    for z in range(1,n+1):
      c=x**2+j**2+z**2+x*j+j*z+z*x
      if c<=n:
        f[c]+=1
for i in range(1,n+1):
  print(f[i])

### FIXED CODE ###

n=int(input())
f = [0]*10005

for x in range(1,101):
	for y in range(1,101):
		for z in range(1,101):
			c = x**2+y**2+z**2+x*y+y*z+z*x
			if c<=n: f[c]+=1
for i in range(1,n+1):
	print(f[i])
### BUGGY CODE ###

h,w = map(int, input().split())
s = []
for i in range(h):
  s.append(input())

l = [[0 for i in range(w)] for j in range(h)]
for i in range(h):
  for j in range(w):
    if j == 0:
      if s[i][j] == '#':
        l[i][j] = 0
      else:
        l[i][j] = 1
    else:
      if s[i][j] == '#':
        l[i][j] = 0
      else:
        l[i][j] = l[i][j-1] + 1

r = [[0 for i in range(w)] for j in range(h)]
for i in range(h):
  for j in range(w-1, -1, -1):
    if j == w-1:
      if s[i][j] == '#':
        r[i][j] = 0
      else:
        r[i][j] = 1
    else:
      if s[i][j] == '#':
        r[i][j] = 0
      else:
        r[i][j] = r[i][j+1] + 1

u = [[0 for i in range(w)] for j in range(h)]
for j in range(w):
  for i in range(h):
    if i == 0:
      if s[i][j] == '#':
        u[i][j] = 0
      else:
        u[i][j] = 1
    else:
      if s[i][j] == '#':
        u[i][j] = 0
      else:
        u[i][j] = u[i-1][j] + 1

d = [[0 for i in range(w)] for j in range(h)]
for j in range(w):
  for i in range(h-1, -1, -1):
    if i == h-1:
      if s[i][j] == '#':
        d[i][j] = 0
      else:
        d[i][j] = 1
    else:
      if s[i][j] == '#':
        d[i][j] = 0
      else:
        d[i][j] = d[i+1][j] + 1

ans = 0
for i in range(h):
  for j in range(w):
    a = l[i][j] + r[i][j] + u[i][j] + d[i][j] - 3
    ans = max(ans, a)

print(ans)

### FIXED CODE ###

h,w = map(int, input().split())
s = []
for i in range(h):
  s.append(input())

l = [[0 for i in range(w)] for j in range(h)]
for i in range(h):
  for j in range(w):
    if j == 0:
      if s[i][j] == '#':
        l[i][j] = 0
      else:
        l[i][j] = 1
    else:
      if s[i][j] == '#':
        l[i][j] = 0
      else:
        l[i][j] = l[i][j-1] + 1

r = [[0 for i in range(w)] for j in range(h)]
for i in range(h):
  for j in range(w-1, -1, -1):
    if j == w-1:
      if s[i][j] == '#':
        r[i][j] = 0
      else:
        r[i][j] = 1
    else:
      if s[i][j] == '#':
        r[i][j] = 0
      else:
        r[i][j] = r[i][j+1] + 1

u = [[0 for i in range(w)] for j in range(h)]
for j in range(w):
  for i in range(h):
    if i == 0:
      if s[i][j] == '#':
        u[i][j] = 0
      else:
        u[i][j] = 1
    else:
      if s[i][j] == '#':
        u[i][j] = 0
      else:
        u[i][j] = u[i-1][j] + 1

d = [[0 for i in range(w)] for j in range(h)]
for j in range(w):
  for i in range(h-1, -1, -1):
    if i == h-1:
      if s[i][j] == '#':
        d[i][j] = 0
      else:
        d[i][j] = 1
    else:
      if s[i][j] == '#':
        d[i][j] = 0
      else:
        d[i][j] = d[i+1][j] + 1

ans = 0
for i in range(h):
  for j in range(w):
    a = l[i][j] + r[i][j] + u[i][j] + d[i][j] - 3
    ans = max(ans, a)

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

n,m=map(int,input().split())
h=list(map(int,input().split()))
p=[i for i in range(1,n+1)]
for i in range(m):
  a=list(map(int,input().split()))
  if h[a[0]-1]<=h[a[1]-1]:
    if a[0] in p:
      p.remove(a[0])
  if h[a[0]-1]>=h[a[1]-1]:
    if a[1] in p:
      p.remove(a[1])
print(len(p))

### FIXED CODE ###

n,m=map(int,input().split())
h=list(map(int,input().split()))
p=[i for i in range(1,n+1)]
q=[]
for i in range(m):
  a=list(map(int,input().split()))
  if h[a[0]-1]<=h[a[1]-1]:
    q.append(a[0])
  if h[a[0]-1]>=h[a[1]-1]:
    q.append(a[1])
p=set(p)
q=set(q)
print(len(p-q))
### BUGGY CODE ###

S = list(input().strip())
is_irrversible = 0
answer = 0
while is_irrversible == 0:
    answer_when_start = answer
    for i in range(len(S)-1):
        if S[i] == 'B' and S[i+1] == 'W':
            S[i],S[i+1] = 'W','B'
            answer += 1
    if answer_when_start == answer:
        is_irrversible = 1
print(answer)

### FIXED CODE ###

S = list(input().strip())
is_irrversible = 0
answer = 0
position_key_sum = 0
number_of_white = 0
sigma = 0
for i in range(len(S)):
    if S[i] == 'W':
        position_key_sum += (i+1)
        number_of_white += 1
        sigma += number_of_white
answer = position_key_sum - sigma
print(answer)
### BUGGY CODE ###

def main():
  _max = max
  from itertools import chain
  h, w = map(int, input().split())
  s = [input() + '#' for _ in range(h)]
  s.append('#' * (w + 1))

  rt = [[-1] * (w + 1) for _ in range(h + 1)]

  tstart = [-1] * (w + 1)
  for i in range(h + 1):
    si = s[i]
    rti = rt[i]
    ystart = -1
    for j in range(w + 1):
      if si[j] == '#':
        if ystart != -1:
          jy = j - ystart
          for k in range(ystart, j):
            rti[k] += jy
          ystart = -1
        tj = tstart[j]
        if tj != -1:
          itj = i - tj
          for k in range(tj, i):
            rt[k][j] += itj
          tstart[j] = -1
      else:
        if ystart == -1:
          ystart = j
        if tstart[j] == -1:
          tstart[j] = i

  print(_max(chain.from_iterable(rt)))

main()

### FIXED CODE ###

h, w = map(int, input().split())
s = [input() + '#' for _ in range(h)]
s.append('#' * w)

yoko = [[0] * w for _ in range(h)]
for i in range(h):
  if s[i][0] == '.':
    start = 0
  else:
    start = -1
  for j in range(1, w + 1):
    if s[i][j] == '#':
      if start != -1:
        for k in range(start, j):
          yoko[i][k] = j - start
        start = -1
    else:
      if start == -1:
        start = j

tate = [[0] * w for _ in range(h)]
for i in range(w):
  if s[0][i] == '.':
    start = 0
  else:
    start = -1
  for j in range(1, h + 1):
    if s[j][i] == '#':
      if start != -1:
        for k in range(start, j):
          tate[k][i] = j - start
        start = -1
    else:
      if start == -1:
        start = j
result = 0
for i in range(h):
  for j in range(w):
    t = yoko[i][j] + tate[i][j] - 1
    if t > result:
      result = t

print(result)
### BUGGY CODE ###

n = int(input())
list = []
for i in range(n):
  s = str(input())
  if s not in list:
    list.append(s)
print(len(list))

### FIXED CODE ###

import collections
n = int(input())
list = []
for i in range(n):
  s = str(input())
  list.append(s)
print(len(collections.Counter(list)))
### BUGGY CODE ###

import math

def tgcd(a,b,c):
    return math.gcd(a,math.gcd(b,c))

K = int(input())
ans = 0

for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            ans += tgcd(i,j,k)

print(ans)

### FIXED CODE ###

import math

K = int(input())
ans = 0
for a in range(1,K-1):
    for b in range(a+1,K):
        for c in range(b+1,K+1):
            r = math.gcd(math.gcd(a,b),c)
            r *= 6
            ans += r
for a in range(1,K):
    for b in range(a+1,K+1):
        r = math.gcd(a,b)
        r *= 6
        ans += r
for a in range(1,K+1):
    ans += a
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def two_int():
    N, K = map(int, input().split())
    return N,K

def one_int():
    return int(input())

def one_str():
    return input()

def many_int():
    return list(map(int, input().split()))



N, M =two_int()

key_list=[]
treasures=[]

for i in range(M):
    mon,_ =two_int()
    key_list.append(mon)
    
    
    temp= many_int()
    sums = 0
    for i in temp:
        sums += 1<<(i-1)
    treasures.append(sums)

treasures

max_index=2**N
INF=10**15

dp=[INF for i in range(max_index)]
dp[0]=0

for i in range(max_index):
    for j in range(M):
        new_i = int(bin(treasures[j] | i),2)
        cost = dp[i] + key_list[j]
        dp[new_i] = min(dp[new_i], cost) 

goal_index=max_index-1
if dp[goal_index]!=INF:
    print(dp[goal_index])
else:
    print(-1)

### FIXED CODE ###

import sys
input = sys.stdin.readline

def two_int():
    N, K = map(int, input().split())
    return N,K

def one_int():
    return int(input())

def one_str():
    return input()

def many_int():
    return list(map(int, input().split()))


def main():
    N, M =two_int()

    key_list=[]
    treasures=[]
    check={}

    for i in range(M):
        mon,_ =two_int()
        temp = map(lambda x: 1<<(x-1), many_int())
        sums = sum(temp)
        
        if sums in check:
            if check[sums] > mon:
                check[sums]=mon
        else:
            check[sums]=mon
            
    for k,v in check.items():
        key_list.append(v)
        treasures.append(k)

    max_index=2**N
    INF=10**15

    dp=[INF for i in range(max_index)]
    dp[0]=0
    M=len(key_list)

    for i in range(max_index-1):
        for j in range(M):
            new_i = int(bin(treasures[j] | i),2)
            cost = dp[i] + key_list[j]
            dp[new_i] = min(dp[new_i], cost) 
        
    goal_index=max_index-1
    if dp[goal_index]!=INF:
        print(dp[goal_index])
    else:
        print(-1)

main()
### BUGGY CODE ###

n, k = map(int, input().split())
alist = list(map(int, input().split()))
t = [0] * 40
for a in alist:
  for i in range(40):
    t[i] += a & 1
    a >>= 1
result = 0
t2 = [None] * 40
m = 1
for l in range(40):
  t2[l] = [m * t[l], m * (n - t[l])]
  m <<= 1
for i in range(0, k + 1):
  j = i
  m = 1
  s = 0
  for l in range(40):
    s += t2[l][j & 1]
    j >>= 1
  result = max(result, s)
print(result)


### FIXED CODE ###

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

bcs = [0] * 41
for i in range(N):
  a = A[i]
  for j in range(41):
    if a & (1 << j) != 0:
      bcs[j] += 1

X = 0
for i in range(40, -1, -1):
  if bcs[i] >= N - bcs[i]:
    continue  
  t = 1 << i
  if X + t <= K:
    X += t

result = 0
for i in range(N):
  result += X ^ A[i]
print(result)
### BUGGY CODE ###

#!/usr/local/bin/python3.5 -tt

import random
import sys

if __name__ == '__main__':
    def _(f):
        for l in f:
            for i in l.split():
                yield(int(i))

    g = _(sys.stdin)

    N = next(g)

    S = 1

    for i in range(N):
        A = next(g)

        S *= A

    if S <= 10 ** 18:
        print(S)
    else:
        print(-1)


### FIXED CODE ###

#!/usr/local/bin/python3.5 -tt

import random
import sys

if __name__ == '__main__':
    def _(f):
        for l in f:
            for i in l.split():
                yield(int(i))

    g = _(sys.stdin)

    N = next(g)

    a = []

    for i in range(N):
        a.append(next(g))

    a.sort()

    S = 1

    for i in a:
        S *= i

        if S == 0:
            print(0)
            sys.exit(0)
        elif S > 10 ** 18:
            print(-1)
            sys.exit(0)

    print(S)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

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

cnt, prev_cnt = 0, -1
while cnt != prev_cnt:
    prev_cnt = cnt
    for i in range(n):
        
        adj_sum = b[i - 1] + b[(i + 1) % n]
        k = (b[i] - a[i]) // adj_sum
        if k > 0:
            b[i] -= k * adj_sum
            cnt += k

print(cnt if a == b else -1)

### FIXED CODE ###

#import sys
#input = sys.stdin.readline

n = int(input())
a = [0]*n
b = [0]*n
a =[int(xi) for xi in input().split()]
b =[int(yi) for yi in input().split()]

cnt, prev_cnt = 0, -1
while cnt != prev_cnt:
    prev_cnt = cnt
    for i in range(n):
        
        adj_sum = b[i - 1] + b[(i + 1) % n]
        k = (b[i] - a[i]) // adj_sum
        if k > 0:
            b[i] -= k * adj_sum
            cnt += k

print(cnt if a == b else -1)
### BUGGY CODE ###

s = input()
t = input()

n = len(s);m = len(t)

# dp [n+1][m+1]

dp = [[0 for i in range(m+1)] for j in range(n+1)]

for i in range(n+1):
  dp[i][0] = 0
  
for j in range(m+1):
  dp[0][j] = 0
  
for i in range(1,n+1):
  for j in range(1,m+1):
    if s[i-1] == t[j-1]:
      dp[i][j] = 1 + dp[i-1][j-1]
    else:
      dp[i][j] = max(dp[i-1][j], dp[i][j-1])
   
def path():
    ans=""
    ls=n;lt=m
    while ls>0 and lt>0:
        if dp[ls][lt]==dp[ls-1][lt]:
            ls-=1
        elif dp[ls][lt]==dp[ls][lt-1]:
            lt-=1
        else:
            ans=s[ls-1]+ans
            ls-=1
            lt-=1
 
    print(ans)
    
path()
#print(dp)

    
    
    

### FIXED CODE ###

s = input()
t = input()

n = len(s);m = len(t)

# dp [n+1][m+1]

dp = [[0 for i in range(m+1)] for j in range(n+1)]

for i in range(n+1):
  dp[i][0] = 0
  
for j in range(m+1):
  dp[0][j] = 0
  
for i in range(1,n+1):
  for j in range(1,m+1):
    if s[i-1] == t[j-1]:
      dp[i][j] = 1 + dp[i-1][j-1]
    else:
      dp[i][j] = max(dp[i-1][j], dp[i][j-1])
   
def path():
    ans=""
    ls=n;lt=m
    while ls>0 and lt>0:
        if dp[ls][lt]==dp[ls-1][lt]:
            ls-=1
        elif dp[ls][lt]==dp[ls][lt-1]:
            lt-=1
        else:
            ans=s[ls-1]+ans
            ls-=1
            lt-=1
 
    print(ans)
    
path()
#print(dp)
### BUGGY CODE ###

from sys import stdin
n,k = map(int,stdin.readline().rstrip().split())
li = list(map(int,stdin.readline().rstrip().split()))
ma = 0
for i in range(n-k+1):
    lin = li[i:i+k]
    point = 0
    if len(lin) != k:
        break
    for j in lin:
        point += (1+j)/2
    ma = max(ma,point)
print(ma)

### FIXED CODE ###

from sys import stdin
from itertools import accumulate
n,k = map(int,stdin.readline().rstrip().split())
li = list(map(int,stdin.readline().rstrip().split()))
ma = 0
lin = []
for i in li:
    lin.append((i+1)/2)
lis = [0]+list(accumulate(lin))
ma = 0
for i in range(n-k+1):
    if i+k > n:
        break
    l = lis[i+k]-lis[i]
    ma = max(ma,l)
print(ma)
### BUGGY CODE ###

import sys

fin = sys.stdin.readline

N, M = map(int, fin().split())
As = list(map(int, fin().split()))
BC = [tuple(map(int, fin().split())) for _ in range(M)]

As = sorted(As)
# BC = sorted(BC, key=lambda x: x[1], reverse=True)

BC_ = {}
for num, val in BC:
    if val in BC_:
        BC_[val] += num
    else:
        BC_[val] = num

BC_ = sorted(BC_.items(), reverse=True)


def f(a, n, v):
    count = 0
    for i in range(min(n, len(a))):
        if a[i] < v:
            count += 1
        else:
            break
    return v * count, a[count:]


sum__ = 0
for val, num in BC_:
    if len(As) == 0 or As[0] >= val:
        break
    sum_, As = f(As, num, val)
    sum__ += sum_

print(sum__ + sum(As))


### FIXED CODE ###

import sys

fin = sys.stdin.readline

N, M = map(int, fin().split())
As = list(map(int, fin().split()))
BC = [tuple(map(int, fin().split())) for _ in range(M)]

As = sorted(As)
# BC = sorted(BC, key=lambda x: x[1], reverse=True)

BC_ = {}
for num, val in BC:
    if val in BC_:
        BC_[val] += num
    else:
        BC_[val] = num

BC_ = sorted(BC_.items(), reverse=True)

#
# def f(a, n, v):
#     if a[min(n-1, len(a)-1)] < v:
#         return v * min(n, len(a)), a[n:]
#     count = 0
#     for i in range(min(n, len(a))):
#         if a[i] < v:
#             count += 1
#         else:
#             break
#     return v * count, a[count:]


sum__ = 0
now = 0
for val, num in BC_:
    if now >= len(As) or As[now] >= val:
        break

    if As[min(num - 1 + now, len(As) - 1)] < val:
        sum_ = val * min(num, len(As) - now)
        now += min(num, len(As) - now)
    else:
        count = 0
        for i in range(min(num, len(As)-now)):
            if As[i + now] < val:
                count += 1
            else:
                break
        sum_ = val * count
        now += count
    sum__ += sum_

print(sum__ + sum(As[now:]))
### BUGGY CODE ###

def uf_find(x):
  if x == p[x]:
    return x
  else:
    p[x] = uf_find(p[x])
    return p[x]

def uf_unite(x,y):
  global rand
  x = uf_find(x)
  y = uf_find(y)
  if x != y:
    if r[y]>r[x]:
      x,y = y,x
    if r[x]==r[y]:
      r[x]+= 1
    p[y] = x


N, M = map(int, input().split())
p = list(range(N))
r = [0]*N

rand = 0

for i in range(M):
  A, B = [int(j)-1 for j in input().split()]
  uf_unite(A,B)
  #print(p)
  
for i in range(N):
  p[i] = uf_find(i)

q = [0]*N
for i in range(N):
  q[i] = p.count(i)
  
print(max(q))


### FIXED CODE ###

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

par = list(range(N))
rank = [1]*N
size = [1]*N

def find(x):
  if par[x] == x:
    return x
  else:
    return find(par[x])
  
def unite(x,y):
  x = find(x)
  y = find(y)
  
  if x == y:
    return
  if rank[x]<rank[y]:
    par[x]=y
    size[y]+= size[x]
  else:
    par[y] = x
    size[x] += size[y]
    if rank[x]==rank[y]:
      rank[x]+=1
    
for i in range(M):
  a,b = [int(i)-1 for i in input().split()]
  unite(a,b)
  
print(max(size))
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
count = 0
for i in range(len(a)):
    count += a.count(a[i])-1
count //= 2
for i in range(len(a)):
    print(count - a.count(a[i])+1)

### FIXED CODE ###

from collections import Counter
n = int(input())
a = list(map(int, input().split()))
counter = Counter(a)
d = [0]*(n+1)
count = 0
for el, cnt in counter.most_common():
    d[el] = cnt
    count += cnt*(cnt-1)
count //= 2
for el in a:
    print(count - d[el] + 1)
### BUGGY CODE ###

H, W, D = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
Q = int(input())
LR = [list(map(int, input().split())) for _ in range(Q)]

li = [[]] * (H * W)
for i in range(H):
  for j in range(W):
    li[A[i][j] - 1] = [j, i]

cost = [[0 for _ in range(H * W)] for _ in range(D)]
for i in range(H * W):
  d, m = divmod(i, D)
  if d > 0:
    cost[m][d] = cost[m][d - 1] + abs(li[i][0] - li[i - D][0]) + abs(li[i][1] - li[i - D][1]) 

# print(cost)

for l, r in LR:
  print(cost[(l - 1) % D][(r - 1) // D] - cost[(l - 1) % D][(l - 1) // D])

### FIXED CODE ###

H, W, D = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
Q = int(input())
LR = [list(map(int, input().split())) for _ in range(Q)]

li = [[]] * (H * W)
for i in range(H):
  for j in range(W):
    li[A[i][j] - 1] = [j, i]

cost = [[0 for _ in range((H * W) // D + 1)] for _ in range(D)]
for i in range(H * W):
  d, m = divmod(i, D)
  if d > 0:
    cost[m][d] = cost[m][d - 1] + abs(li[i][0] - li[i - D][0]) + abs(li[i][1] - li[i - D][1]) 

# print(cost)

for l, r in LR:
  print(cost[(l - 1) % D][(r - 1) // D] - cost[(l - 1) % D][(l - 1) // D])