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

n, m = map(int, input().split())
s = []
e = []
for i in range(m):
    a, b = map(int, input().split())
    if a == 1 and b not in s:
        s.append(b)
    elif b == n and a not in e:
        e.append(a)
if len(set(s) & set(e)) != 0:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')


### FIXED CODE ###

n, m = map(int, input().split())
s = []
e = []
for i in range(m):
    a, b = map(int, input().split())
    if a == 1:
        s.append(b)
    elif b == n:
        e.append(a)
if len(set(s) & set(e)) != 0:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')
### BUGGY CODE ###

import time
time.sleep(3)

### FIXED CODE ###

from itertools import combinations

N, M = list(map(lambda x:int(x),input().split()))

def nCr(n, r):
    """
    Calculate the number of combination (nCr = nPr/r!).
    The parameters need to meet the condition of n >= r >= 0.
    It returns 1 if r == 0, which means there is one pattern
    to choice 0 items out of the number of n.
    """

    # 10C7 = 10C3
    r = min(r, n-r)

    # Calculate the numerator.
    numerator = 1
    for i in range(n, n-r, -1):
        numerator *= i

    # Calculate the denominator. Should use math.factorial?
    denominator = 1
    for i in range(r, 1, -1):
        denominator *= i

    return numerator // denominator

if N <= 1 and M <= 1:
    print(0)
elif N <= 1 and not M <= 1:
    print(nCr(M,2))
elif not N <= 1 and M <= 1:
    print(nCr(N,2))
else:
    print(nCr(N, 2) + nCr(M,2))
### BUGGY CODE ###

n, k = map(int, input().split(' '))
l = map(int, input().split(' '))

s = 1
if n == k:
	for i in l:
		s *= i
	print(s % 1000000007)
else:
	pos = []
	neg = []

	for i in l:
		if i >= 0:
			pos.append(i)
		else:
			neg.append(i)

	pos = sorted(pos)
	neg = sorted(neg)[::-1]
	answer = []
	s = 1

	if k % 2 == 1 and not pos:
		for i in neg[:k]:
			s *= i
		print(s % 1000000007)

	else:
		if k % 2 == 1:
			s = pos.pop()
		while len(pos) >= 2:
			answer.append(pos.pop()*pos.pop())
		while len(neg) >= 2:
			answer.append(neg.pop()*neg.pop())
		answer = sorted(answer)[::-1]
		for i in range(k//2):
			s *= answer[i]
		print(s % 1000000007)

### FIXED CODE ###

n, k = map(int, input().split(' '))
l = map(int, input().split(' '))

s = 1
if n == k:
	for i in l:
		s *= i
		s %= 1000000007
	print(s)
else:
	pos = []
	neg = []

	for i in l:
		if i >= 0:
			pos.append(i)
		else:
			neg.append(i)

	pos.sort()
	neg.sort(reverse=True)
	answer = []

	if k % 2 == 1 and not pos:
		for i in range(k):
			s *= neg[i]
			s %= 1000000007
		print(s)

	else:
		if k % 2 == 1:
			s = pos.pop()
		for i in range(k//2):
			if len(pos) >= 2:
				answer.append(pos.pop()*pos.pop())
			else:
				break
		for i in range(k//2):
			if len(neg) >= 2:
				answer.append(neg.pop()*neg.pop())
			else:
				break
		answer.sort(reverse=True)
		for i in range(k//2):
			s *= answer[i]
			s %= 1000000007
		print(s)
### BUGGY CODE ###

from sys import stdin
def main():
    n = int(stdin.readline().rstrip())
    a = list(map(int,stdin.readline().rstrip().split()))
    mod = 10**9+7
    point = 0
    kai = [2**i%mod for i in range(61)]
    for i in range(61):
        now = 0
        for j in a:
            now += (j >> i)&1
        now *= n-now
        now *= kai[i]
        point += now
    print(point%mod)
if __name__ == "__main__":
    main()

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
mod = 10**9+7
point = 0
for i in range(61):
    now = 0
    for j in a:
        now += (j >> i&1)
    now *= n-now
    now %= mod
    for k in range(i):
        now *= 2
        now %= mod
    point += now
    point %= mod
print(point)
### BUGGY CODE ###

n, k = map( int, input().split() )
h = [ int( hi ) for hi in input().split() ]
#print( n, k )
#print( h )

cost = [ 1000000000 ] * n
cost[ 0 ] = 0
for ni in range( 1, n ):
    for ki in range( 1, k+1 ):
#        print( ni, ki )
        if ni-ki >= 0:
            costx = cost[ ni-ki ] + max( h[ ni ]-h[ ni-ki ], h[ ni-ki ]-h[ ni ] )
            cost[ ni ] = min( cost[ ni ], costx )

print( cost[ n-1 ] )


### FIXED CODE ###

import numpy as np
N,K = map(int,input().split())
h = np.array(list(map(int,input().split())))

dp = np.zeros(N,dtype=int)
for i in range(1,N):
    dp[i] = (dp[max(0,i-K):i] + np.abs(h[i]-h[max(0,i-K):i])).min()
print(dp[-1])
### BUGGY CODE ###

import math
n,m = map(int,input().split())
s = input()
t = input()
lcm = n*m//math.gcd(n,m)
ans = []
for i in range(0,lcm,lcm//n):
    ans.append(i)
for i in range(0,lcm,lcm//m):
    if ans.count(i) == 1:
        if i == 0:
            if s[0] != t[0]:
                print(-1)
                exit()
        if s[i//(lcm//n)] != t[i//(lcm//m)]:
            print(-1)
            exit()
print(lcm)





### FIXED CODE ###

import math
n,m = map(int,input().split())
s = input()
t = input()
lcm = n*m//math.gcd(n,m)
ans = []
s_ind = lcm//n
t_ind = lcm//m
check_ind = s_ind*t_ind//math.gcd(s_ind,t_ind)
for i in range(0,lcm,check_ind):
    if s[i//s_ind] != t[i//t_ind]:
        print(-1)
        exit()
print(lcm)
### BUGGY CODE ###

N = int(input())
ans = 1
count = 0
S = list(map(int, input().split()))

while count <= N - 1:
    ans *= S[count]
    count += 1

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

### FIXED CODE ###

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

if 0 in S:
    ans = 0
else:
    for i in range(N):
        ans *= S[i-1]
        if ans > 10**18:
            ans = -1
            break
print(ans)
### BUGGY CODE ###

e,a = map(int,input().split())
cnt = 0
while True:
    if e ==0 and a ==0:
        break
    for i in range(1,a+1):
        for j in range(1,a+1):
            if j<=i:
                continue
            
            X = a - (i + j)
            if X > j and X <=a:
                cnt +=1
    print(cnt)


### FIXED CODE ###

while True:
    e,a = map(int,input().split())
    if e ==0 and a ==0:
        break
    cnt = 0
    for i in range(1,e+1):
        for j in range(1,e+1):
            if j<=i:
                continue
            X = a - (i + j)
            if X > j and X <=e:
                cnt +=1
    print(cnt)
### BUGGY CODE ###

n,a=map(int,input().split())
lists=list(map(int,input().split()))
x=max(lists)
dp=[[[0 for i in range(2602)] for j in range(51)] for _ in range(51)]
dp[0][0][0]=1
#dp[i][j][k] で0からi番目のカードまでのうちで　ｊ枚を選択して、その時に選んだ数の合計がsとなるような方法の総数を刺すことにする
for i in range(n+1):
    for j in range(n+1):
        for k in range(n*x+1):
            if i>=j and i>=1 and k<lists[i-1]:
                dp[i][j][k]=dp[i-1][j][k]
            elif i>=j and j>=1and k>=lists[i-1]:
                dp[i][j][k]=dp[i-1][j][k]+dp[i-1][j-1][k-lists[i-1]]
ans=0
for i in range(1,n+1):
    ans+=dp[n][i][a*i]
print(ans)


### FIXED CODE ###

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

for i in range(n):
    lists[i]-=a
answer=0
dp=[[0 for i in range(5001)] for _ in range(51)]
#dp[i][j]で0からi枚目まで好きなように選択してそのそうわがｊ-2500となるような撮り方の総数
#最終的に求めるのはdp[i][0]である

for i in range(n+1):
    for j in range(4951):
        if i>=1 and j>=lists[i-1]:
            dp[i][j]=dp[i-1][j-lists[i-1]]+dp[i-1][j]
        if i>=1 and j<lists[i-1]:
            dp[i][j]=dp[i-1][j]
        else:
            if j==2500 and i==0:
                dp[i][j]=1
            elif j!=2500 and i==0:
                dp[i][j]=0
print(dp[n][2500]-1)
### BUGGY CODE ###

def main():
    N, W = map(int, input().split())
    wi, vi = map(int, input().split())
    dp = [0] * wi + [vi] * (W + 1 - wi)
    for _ in range(1, N):
        wi, vi = map(int, input().split())
        dp[wi:] = [max(i + vi, j) for i, j in zip(dp, dp[wi:])]
    print(dp[-1])


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    N, W = map(int, input().split())
    wi, vi = map(int, input().split())
    dp = [0] * wi + [vi] * (W + 1 - wi)
    for _ in range(1, N):
        wi, vi = map(int, input().split())
        for i in range(W, wi - 1, -1):
            t = dp[i - wi] + vi
            if t > dp[i]:
                dp[i] = t
    print(dp[-1])


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

import math
N = int(input())
P_List = list(map(float,input().split()))
dp = []
for i in range(N):
    Current_List = [1-P_List[i],P_List[i]]
    if i == 0:
        dp.append(Current_List)
    else:
        dp.append([x*y for x in dp[i-1] for y in Current_List])

Standard = math.ceil(N/2)
Ans = 0
for k in range(len(dp[-1])):
    if bin(k).count("1") >= Standard:
       Ans += dp[-1][k]

print(round(Ans,10))

### FIXED CODE ###

#https://atcoder.jp/contests/dp/tasks/dp_i
import math
N = int(input())
P_List = list(map(float,input().split()))
dp = [[0 for j in range(N + 1)] for i in range(N+1)]
std = math.ceil(N/2)
for i in range(N+1):
    if i == 0:
        dp[i][0] = 1
    else:
        Current_P = P_List[i - 1]
        for j in range(i + 1):
            if (N - i + j) < std:
                dp[i][j] = 0
            elif j == 0:
                dp[i][j] = dp[i - 1][j]*(1 - Current_P)
            elif j != i:
                dp[i][j] = (dp[i - 1][j]*(1 - Current_P)) + (dp[i - 1][j - 1]*Current_P)
            else:
                dp[i][j] = dp[i - 1][j - 1]*Current_P
    
print(sum(dp[N][math.ceil(std):]))
### BUGGY CODE ###

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

# 組み合わせ
kaijo = [(tmp := (i * tmp) % mod) for i in range(1, n + 1)]
inv = pow(kaijo[-1], mod - 2, mod)
invs = [inv] + [(inv := (inv * i) % mod) for i in range(n, 0, -1)]
C = [(((kaijo[n - 1] * invs[n - i]) % mod) * invs[i]) % mod for i in range(0, n + 1)]

print(pow(2, n, mod) - 1 - C[a] - C[b])


### FIXED CODE ###

n, a, b = map(int, input().split())
if a > b: a, b = b, a
mod = 10 ** 9 + 7
tmp = 1

C = n
ans = 0
if a == 1: Ca = n
for r in range(1, n + 1):
    C = (((C * (n - r)) % mod )* pow(r + 1, mod - 2, mod)) % mod
    if r == a - 1:
        Ca = C
    if r == b - 1:
        Cb = C
        break

print((pow(2, n, mod) - Ca - Cb - 1) % mod)
### BUGGY CODE ###

from fractions import gcd

def lcm(a):
    x = a[0]
    for i in range(1, len(a)):
        x = (x * a[i]) // gcd(x, a[i])
    return x

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

div = 10**9 + 7
lcm_num = lcm(a)
ans = 0

for i in range(n):
    ans += (lcm_num // a[i]) % div

print(ans%div)

### FIXED CODE ###

from fractions import gcd

def lcm(a):
    x = a[0]
    for i in range(1, len(a)):
        x = (x * a[i]) // gcd(x, a[i])
    return x

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

div = 10**9 + 7
lcm_num = lcm(a)
ans = [lcm_num//ai for ai in a]

print(sum(ans)%div)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
MOD = 10 ** 9 + 7
a = [num % MOD if num >= MOD else num for num in a]

ans = []
for i in range(len(a)):
	for j in range(i + 1, len(a)):
		acc = a[i] * a[j]
		ans.append(acc % MOD if acc >= MOD else acc)
print(sum(ans) % MOD)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
MOD = 10 ** 9 + 7
a = [num % MOD if num >= MOD else num for num in a]

sum_list = [0]
for i in range(n):
	sum_list.append((a[i] + sum_list[i]) % MOD)
# print(sum_list)

ans = 0
for i in range(len(a)):
	ans += a[i] * (sum_list[-1] - sum_list[i + 1])
	ans %= MOD

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

N,W = map(int,input().split())
dp = [0 for _ in range(W+1)]
for i in range(N):
    w,v = map(int,input().split())
    for j in range(W+1):
        if j+w <= W:
            dp[j] = max(dp[j],dp[j+w]+v)
print(max(dp))

### FIXED CODE ###

N, capW = map(int, input().split())
items = [tuple(map(int, input().split())) for _ in range(N)]
 
def knapsack01(items, capW):
    dp = [0] * (capW+1)
    for wi, vi in items:
        for w in reversed(range(wi, capW+1)):
            v0 = dp[w-wi] + vi
            if v0 > dp[w]:
                dp[w] = v0
    return max(dp)
 
print(knapsack01(items, capW))
### BUGGY CODE ###

def floor(x):
    return int(x)

a,b,n=map(int,input().split())
m=0
for i in range(1,n+1):
    tmp=floor(a*i/b)-(floor(i/b)*a)
    if tmp>m:
        m=tmp
print(m)

### FIXED CODE ###

a,b,n=map(int,input().split())
m=min(n,b-1)
tmp=(a*m//b)-((m//b)*a)    
print(tmp)
### BUGGY CODE ###

# 移動Aで探索する方向
d_a = [(-1,0),(0,-1),(1,0),(0,1)]
# 移動Bで探索する方向
d_b = list()
for i in range(-2, 3):
    for j in range(-2, 3):
        if (i,j) not in (d_a+[(0,0)]):
            d_b += [(i,j)]

h, w = list(map(int, input().split()))
si, sj = list(map(int, input().split()))
ti, tj = list(map(int, input().split()))
s = [None] * h
for i in range(h):
    s[i] = input()

# 距離情報を一番遠い値で初期化
#import numpy as np
INF = int(1e9)
#dist = np.full((h+4, w+4), INF)
dist = [[INF for j in range(w+4)] for i in range(h+4)]

# マップ境界を壁で囲む
S = ['##{}##'.format(s_row) for s_row in s]
S = ['##{}##'.format('#' * (w+4))]*2 + S
S = S + ['##{}##'.format('#' * (w+4))]*2

# 01-BFS探索用キュー
from collections import deque
q = deque()

# 開始位置、終了位置を調整
si, sj = si+1, sj+1
ti, tj = ti+1, tj+1
dist[si][sj] = 0
q.append((si,sj))

while (len(q)>0):
    i, j = q[0]
    d = dist[i][j]
    q.popleft()
    close_wall = False
    # 移動Aによるコスト
    for di, dj in d_a:
        di, dj = di+i, dj+j
        if (di, dj) == (ti, tj):
            print(d)
            exit(0)
        if (S[di][dj]=='#'):
            close_wall = True
            continue # 壁
        if (dist[di][dj]<=d):
            continue # 探索済みコスト以上
        dist[di][dj] = d
        q.appendleft((di, dj))
    # 壁際ならば移動Bによるコストを探索
    if close_wall:
        for di, dj in d_b:
            di, dj = di+i, dj+j
            if (S[di][dj]=='#'):
                continue # 壁
            if (dist[di][dj]<=d):
                continue # 探索済みコスト以上
            dist[di][dj] = d+1
            q.append((di, dj))

ans = dist[ti][tj]
if ans == INF:
    ans = -1
print(ans)


### FIXED CODE ###

h, w = list(map(int, input().split()))
si, sj = list(map(int, input().split()))
ti, tj = list(map(int, input().split()))
s = [None] * h
for i in range(h):
    s[i] = input()

# 移動Aで探索する方向
d_a = [(-1,0), (0,-1),(1,0),(0,1)]
# 移動Bで探索する方向
d_b = [ (i, j) for j in range(-2, 3) for i in range(-2, 3)]

# 距離情報を一番遠い値で初期化
#import numpy as np
INF = int(1e9)
#dist = np.full((h+2, w+2), INF)
dist = [[INF for j in range(w+2)] for i in range(h+2)]

# マップ境界と壁を距離0にして探索させない
for i in range(h+2):
    dist[i][0] = 0
    dist[i][-1] = 0
for j in range(w+2):
    dist[0][j] = 0
    dist[-1][j] = 0
for i in range(h):
    for j in range(w):
        if s[i][j]=='#': dist[i+1][j+1] = 0
#dist = [[INF for j in range(w)] for i in range(h)]

# 01-BFS探索用キュー
from collections import deque
q = deque()

# 開始位置
dist[si][sj] = 0
q.append((si,sj))

while (len(q)>0):
    i, j = q[0]
    d = dist[i][j]
    q.popleft()
    # 移動Aによるコスト
    for v in range(len(d_a)):
        di, dj = d_a[v][0]+i, d_a[v][1]+j
        if (di, dj) == (ti, tj):
            print(d)
            exit(0)
        if (dist[di][dj]<=d):
            continue # 探索済みコスト以上
        dist[di][dj] = d
        q.appendleft((di, dj))
    # 移動Bによるコスト
    for v in range(len(d_b)):
        # マップ境界で2以上移動したときに、反対の境界に向かうように剰余を取る
        di, dj = (d_b[v][0]+i)%(h+2), (d_b[v][1]+j)%(w+2)
        if (dist[di][dj]<=d):
            continue # 探索済みコスト以上
        dist[di][dj] = d+1
        q.append((di, dj))

ans = dist[ti][tj]
if ans == INF:
    ans = -1
print(ans)
### BUGGY CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
for _ in range(m):
    maxid = a.index(max(a))
    a[maxid] = a[maxid] // 2
print(sum(a))

### FIXED CODE ###

from heapq import heapify, heappop, heappush
import math
n, m = map(int, input().split())
a = list(map(int, input().split()))
for i in range(n):
    a[i] = a[i] * -1
heapify(a)
for _ in range(m):
    minval = heappop(a)
    heappush(a, math.ceil(minval / 2))
ans = 0
for i in range(n):
    ans += int(a[i])
print(-ans)
### BUGGY CODE ###

n = int(input())
ls = list(map(int,input().split()))
a = 0
for i in range(n):
    for j in range(i):
        if ls[i] > ls[j]:
            a += 1
            break
        else:
            continue
print(n - a)


### FIXED CODE ###

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

import collections
a=int(input())
ai=[int(i) for i in input().split()]
c = collections.Counter(ai)
val=0
for i in c.values():
    val+=i*(i-1)//2
for i in ai:
    b=ai.count(i)
    print(val-b+1)

### FIXED CODE ###

import collections
a=int(input())
ai = list(map(int, input().split()))
c = collections.Counter(ai)
val=0
for i in c.values():
    val+=i*(i-1)//2
for i in range(len(ai)):
    b=c[ai[i]]
    print(val-b+1)
### BUGGY CODE ###

N, K = map(int, input().split())
h = list(map(int, input().split()))
INF = 10 ** 12

dp = [0] + [INF for _ in range(N - 1)]
for i in range(1, N):
    for j in range(1, K + 1):
        if i - j >= 0:
            dp[i] = min(dp[i], dp[i - j] + abs(h[i] - h[i - j]))

print(dp[N - 1])

### FIXED CODE ###

import numpy as np

N, K = map(int, input().split())
h = np.array(list(map(int, input().split())))
INF = 10 ** 12

dp = np.array([0] + [INF for _ in range(N - 1)], dtype=np.int64)
for i in range(1, N):
    dp[i] = np.min(dp[max(0, i-K):i] + np.abs(h[i] - h[max(0, i-K):i]))

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

S = input()

P = 10**9+7
LENGTH = len(S)

"""dp[i][j] -> あり得る全ての上からi+1桁目までの数を13で割った余りが j となる状態数"""
dp = [[0 for i in range(13)] for j in range(LENGTH)]

if S[0]=='?':
    for j in range(10):
        dp[0][j]+=1
else:
    dp[0][int(S[0])]+=1

for i in range(LENGTH-1):
    for j in range(13):
        if S[i+1]=='?':
            for k in range(10):
                dp[i+1][(10*j+k)%13]+=dp[i][j]%P
        else:
            dp[i+1][(10*j+int(S[i+1]))%13]+=dp[i][j]%P

print(dp[LENGTH-1][5]%P)

### FIXED CODE ###

S = input()

P = 10**9+7
LENGTH = len(S)

"""dp[i][j] -> あり得る全ての上からi+1桁目までの数を13で割った余りが j となる状態数"""
dp = [[0 for i in range(13)] for j in range(LENGTH)]

if S[0]=='?':
    for j in range(10):
        dp[0][j]+=1
else:
    dp[0][int(S[0])]+=1

for i in range(LENGTH-1):
    for j in range(13):
        if S[i+1]=='?':
            for k in range(10):
                dp[i+1][(10*j+k)%13]+=dp[i][j]%P
        else:
            dp[i+1][(10*j+int(S[i+1]))%13]+=dp[i][j]%P

print(dp[LENGTH-1][5]%P)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
dp=[[0 for i in range(n+1)] for j in range(n+1)]

for len in range(1,n+1):
  for i in range(n+1):
    if i+len>n:
      break
    j=i+len
    if (n - len) % 2 == 0:
      dp[i][j] = max(dp[i + 1][j] + a[i], dp[i][j - 1] + a[j - 1])
      #print(len,dp)
    else:
      dp[i][j] = min(dp[i + 1][j] - a[i], dp[i][j - 1] - a[j - 1])
      #print(len,dp)
print(dp[0][n])

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
dp=[[0 for i in range(n+1)] for j in range(n+1)]

for len in range(1,n+1):
  for i in range(n+1):
    if i+len>n:
      break
    j=i+len
    if (n - len) % 2 == 0:
      dp[i][j] = max(dp[i + 1][j] + a[i], dp[i][j - 1] + a[j - 1])
      #print(len,dp)
    else:
      dp[i][j] = min(dp[i + 1][j] - a[i], dp[i][j - 1] - a[j - 1])
      #print(len,dp)
print(dp[0][n])
### BUGGY CODE ###

import numpy as np

def one_game(i, D, A, start, end):
    current = np.array([])
    count = 0
    for X in range(start, end+1, D):
        old = np.copy(current)
        current = np.where(A==X)
        if X == start:
            continue
        count += abs(current[0][0] - old[0][0]) + abs(current[1][0] - old[1][0])
    return count

def f(H, W, D, A, Q, ST):
    A = np.array(A)
    counts = []
    for i in range(Q):
        start = ST[i][0]
        end = ST[i][1]
        count = one_game(i, D, A, start, end)
        counts.append(count)
    return counts

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

    counts = f(H, W, D, A, Q, ST)
    for i in range(Q):
        print(counts[i])

if __name__ == '__main__':
    main()


### FIXED CODE ###

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

    pos = [0] * (H * W + 1)
    for i, row in enumerate(A):
        for j, value in enumerate(row):
            pos[value] = (i, j)

    d = [0] * (H * W + 1)
    for x in range(D + 1, H * W + 1):
        y = x - D
        p1, p2 = pos[x], pos[y]
        d[x] = d[y] + abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])

    for l, r in ST:
        print(d[r] - d[l])


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

S = input()
T = input()
memo_ls = [[] for i in range(len(S)+1)]
res = ""
for i in range(len(T) + 1):
    memo_ls[0].append(0)
path = dict()
for i in range(len(S)):
    memo_ls[i+1].append(0)
    for j in range(len(T)):
        if S[i] == T[j]:
            cost = max(memo_ls[i][j] + 1, memo_ls[i][j+1], memo_ls[i+1][j])
            memo_ls[i+1].append(cost)
        else:
            memo_ls[i+1].append(max(memo_ls[i][j+1], memo_ls[i+1][j]))

x_ind = len(T)
y_ind = len(S)
while x_ind * y_ind > 0:
    if memo_ls[y_ind][x_ind] == memo_ls[y_ind-1][x_ind]:
        y_ind -= 1
    elif memo_ls[y_ind][x_ind] == memo_ls[y_ind][x_ind-1]:
        x_ind -= 1
    else:
        res += T[x_ind-1]
        x_ind -= 1
        y_ind -= 1
print(res[::-1])

### FIXED CODE ###

S = input()
T = input()
memo_ls = [[] for i in range(len(S)+1)]
res = ""
for i in range(len(T) + 1):
    memo_ls[0].append(0)
path = dict()
for i in range(len(S)):
    memo_ls[i+1].append(0)
    for j in range(len(T)):
        if S[i] == T[j]:
            cost = max(memo_ls[i][j] + 1, memo_ls[i][j+1], memo_ls[i+1][j])
            memo_ls[i+1].append(cost)
        else:
            memo_ls[i+1].append(max(memo_ls[i][j+1], memo_ls[i+1][j]))

x_ind = len(T)
y_ind = len(S)
while x_ind * y_ind > 0:
    if memo_ls[y_ind][x_ind] == memo_ls[y_ind-1][x_ind]:
        y_ind -= 1
    elif memo_ls[y_ind][x_ind] == memo_ls[y_ind][x_ind-1]:
        x_ind -= 1
    else:
        res += T[x_ind-1]
        x_ind -= 1
        y_ind -= 1
print(res[::-1])
### BUGGY CODE ###

h,w,m=map(int,input().split())
hlist=[0]*(h+1)
wlist=[0]*(w+1)
cnt=[]


for i in range(m):
  a,b=map(int,input().split())
  hlist[a]+=1
  wlist[b]+=1
  cnt.append([a,b])


hcnt,wcnt=max(hlist),max(wlist)


hhh=[i for i,v in enumerate(hlist) if v==hcnt]
www=[i for i,v in enumerate(wlist) if v==wcnt]


for i in hhh:
  for j in www:
    if [i,j] not in cnt:
      print(hcnt+wcnt)
      exit()


print(hcnt+wcnt-1)

### FIXED CODE ###

h,w,m=map(int,input().split())
hlist=[0]*(h+1)
wlist=[0]*(w+1)
cnt=set()


for i in range(m):
  a,b=map(int,input().split())
  hlist[a]+=1
  wlist[b]+=1
  cnt.add((a,b))


hcnt,wcnt=max(hlist),max(wlist)


hhh=[i for i,v in enumerate(hlist) if v==hcnt]
www=[i for i,v in enumerate(wlist) if v==wcnt]


for i in hhh:
  for j in www:
    if not (i,j) in cnt:
      print(hcnt+wcnt)
      exit()


print(hcnt+wcnt-1)
### BUGGY CODE ###

# coding: utf-8
N = int(input())
A = input().split()
for k in range(N):
  A_ = A.copy()
  del A_[k]
  dic = set(A_)
  ans = 0
  for i in dic:
    tmp = A_.count(i)
    ans += int(tmp * (tmp - 1) / 2)

  print('{}'.format(ans))

### FIXED CODE ###

# coding: utf-8
N = int(input())
A = list(map(int, input().split()))

dict = {}
for i in range(N):
  if A[i] in dict.keys():
    dict[A[i]] += 1
  else:
    dict[A[i]] = 1

def comb(n):
  if n<2:
    return 0
  return int(n * (n - 1) / 2)

# all
ret = 0
for key in dict.keys():
  val = dict[key]
  ret += comb(val)

# i >= 0
for i in range(N):
  val_n = dict[A[i]]
  next_ret = ret - comb(val_n) + comb(val_n - 1)
  print(next_ret)
### BUGGY CODE ###

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

all_mount = sum(A)
mounts = []
for i in range(N):
  mount = all_mount
  for j in range(0, N, 2):
    mount -= 2 * A[(i+j)%N]
  mounts.append(abs(mount))
    
print(" ".join(map(str,mounts)))

### FIXED CODE ###

N = int(input())
A = list(map(lambda x: 2 * int(x), input().split()))

all_mount = sum(A) // 2
A_1 = all_mount
for i in range(1, N, 2):
  A_1 -= A[i]
  
mounts = [A_1]
for i in range(N-1):
  mounts.append(A[i] - mounts[i])
  
print(" ".join(map(str, mounts)))