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

import sys,bisect
input=sys.stdin.readline

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

dp=[[0 for i in range(100001)] for i in range(2**10)]
for i in range(vw[1][1],100001):
    dp[1][i]=vw[1][0]
MAX=min(2**10,N+1)
for i in range(2,MAX):
    v,w=vw[i]
    for j in range(w):
        dp[i][j]=dp[i//2][j]
    for j in range(w,100001):
        dp[i][j]=max(dp[i//2][j],dp[i//2][j-w]+v)

temp=[[0,0] for i in range(2**10)]
for i in range(int(input())):
    v,L=map(int,input().split())
    if 2**10>v:
        print(dp[v][L])
    else:
        t=[]
        while v>=2**10:
            t.append(vw[v])
            v//=2
        n=len(t)
        temp[0][0]=0
        temp[0][0]=0
        for i in range(1,2**n):
            m=i.bit_length()
            temp[i][0]=temp[i-2**(m-1)][0]+t[m-1][0]
            temp[i][1]=temp[i-2**(m-1)][1]+t[m-1][1]
        ans=0
        for i in range(2**n):
            if L>=temp[i][1]:
                ans=max(ans,temp[i][0]+dp[v][L-temp[i][1]])
        print(ans)


### FIXED CODE ###

import sys,random,time,bisect
input=sys.stdin.buffer.readline

start=time.time()
N=int(input())
vw=[(-1,-1)]
for i in range(N):
    vw.append(tuple(map(int,input().split())))

dp=[[] for i in range(2**9)]
def make_dp(v):
    t=[[0,0] for i in range(15)]
    V=v
    id=0
    while v>=1:
        t[id]=vw[v]
        id+=1
        v//=2
    n=id
    temp=[[0,0] for i in range(2**n)]
    for i in range(n):
        for j in range(2**i,2**(i+1)):
            temp[j][0]=temp[j-2**i][0]+t[i][0]
            temp[j][1]=temp[j-2**i][1]+t[i][1]
    temp.sort(key=lambda x:x[1])
    for i in range(1,2**n):
        temp[i][0]=max(temp[i][0],temp[i-1][0])

    dp[V]=[0]*(10**5+1)
    for i in range(2**n-1):
        L=temp[i][1]
        R=temp[i+1][1]
        if L>10**5:
            break
        elif R>10**5:
            R=10**5+1
        for j in range(L,R):
            dp[V][j]=temp[i][0]
    else:
        L=temp[-1][1]
        if L<=10**5:
            for j in range(L,10**5+1):
                dp[V][j]=temp[-1][0]

MAX=min(2**9,N+1)
for i in range(1,MAX):
    make_dp(i)

Q=int(input())
query=[[] for i in range(N+1)]
for i in range(Q):
    v,L=map(int,input().split())
    query[v].append((L,i))

ans=[0]*Q
temp=[[0,0] for i in range(2**9)]
t=[[0,0] for i in range(15)]
def solve(v):
    V=v
    id=0
    while v>=2**9:
        t[id]=vw[v]
        id+=1
        v//=2
    n=id
    for i in range(n):
        for j in range(2**i,2**(i+1)):
            temp[j][0]=temp[j-2**i][0]+t[i][0]
            temp[j][1]=temp[j-2**i][1]+t[i][1]

    for L,ID in query[V]:
        res=0
        for i in range(2**n):
            if L>=temp[i][1]:
                res=max(res,temp[i][0]+dp[v][L-temp[i][1]])
        ans[ID]=res

for i in range(1,N+1):
    if query[i]:
        solve(i)

for i in range(Q):
    print(ans[i])
### BUGGY CODE ###

import sys
input = sys.stdin.readline

import bisect

def main():
  n, k = map(int, input().split())
  minus = []
  zero = 0
  plus = []
  lm = 0
  lp = 0
  for i in map(int, input().split()):
    if i < 0:
      minus.append(-i)
      lm += 1
    elif i == 0:
      zero += 1
    else:
      plus.append(i)
      lp += 1
  
  J = lm*lp + zero*(n-zero) + zero*(zero-1)//2

  minus.sort()
  plus.sort()

  def test(x):
    count = 0
    if x < 0:
      x = -x
      for i in minus:
        count += lp - bisect.bisect_left(plus, -(-x//i))
      return count >= k

    if x == 0:
      return J >= k

    count = J
    for i in range(lm-1):
      t = minus[i]
      count += bisect.bisect_right(minus[i+1:], x//t)
    for i in range(lp-1):
      t = plus[i]
      count += bisect.bisect_right(plus[i+1:], x//t)
    return count >= k

  if J < k:
    ng = 0
    ok = 10**18
  else:
    ng = -(10**18)
    ok = 0
  
  while ok-ng > 1:
    mid = (ok+ng)//2
    if test(mid):
      ok = mid
    else:
      ng = mid
  print(ok)
  
if __name__ == "__main__":
  main()

### FIXED CODE ###

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
a, b, c = 0, 0, 0
L, R = [], []
for p in map(int, input().split()):
  if p < 0:
    a += 1
    L.append(p)
  elif p == 0:
    b += 1
  else:
    c += 1
    R.append(p)
L.sort()
R.sort()
s = a*c
t = b*(b-1)//2 + (a+c)*b
if s < k <= s+t:
  ans = 0
else:
  if k <= s:
    ok = -1
    ng = -(10**18+1)
    while ok - ng > 1:
      mid = (ok+ng)//2
      now = 0
      temp = 0
      for l in L:
        while now < c and l*R[now] > mid:
          now += 1
        temp += c - now
      if temp >= k:
        ok = mid
      else:
        ng = mid
  else:
    ok = 10**18
    ng = 0
    while ok - ng > 1:
      mid = (ok+ng)//2
      now = c - 1
      temp = s+t
      for i, r in enumerate(R):
        if now <= i:
          break
        while now > i and r*R[now] > mid:
          now -= 1
        temp += now - i
      now = 0
      for i in range(a-1, -1, -1):
        l = L[i]
        if now >= i:
          break
        while now < i and l*L[now] > mid:
          now += 1
        temp += i - now
      if temp >= k:
        ok = mid
      else:
        ng = mid
  ans = ok
print(ans)
### BUGGY CODE ###

n = int(input())
p = list(map(int,input().split()))
a = []
ans = 0
for i in p:
    a.append(i)
    if min(a) == i:
        ans += 1
print(ans)

### FIXED CODE ###

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

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

ab = []
for i in range(n):
    a, b = map(int, input().split())
    ab.append([a, b])

INF = 1 << 60
dp = [INF for _ in range(h+10001)]

dp[0] = 0

for i in range(1, h+10001):
    for j in range(n):
        if(i<ab[j][0]): continue
        dp[i] = min(dp[i-ab[j][0]] + ab[j][1], dp[i])

res = INF
for i in range(h, h+10001):
    res = min(res, dp[i])
print(res)

### FIXED CODE ###

h, n = map(int, input().split())
 
ab = []
for i in range(n):
    a, b = map(int, input().split())
    ab.append([a, b])
 
INF = 1 << 60
dp = [INF for _ in range(h+10001)]
 
dp[0] = 0
 
for i in range(1, h+10001):
    for j in range(n):
        if(i<ab[j][0]): continue
        dp[i] = min(dp[i-ab[j][0]] + ab[j][1], dp[i])
 
res = INF
for i in range(h, h+10001):
    res = min(res, dp[i])
print(res)
### BUGGY CODE ###

s=input()
q= int(input())

iturn=0
for iq in range(1,q+1):
	t=input().split()
	if t[0]=='1':
		iturn=iturn+1   	
	else:
		if t[1]=='1':
#			s=t[2]+s
			if iturn%2==0:
				s=t[2]+s
			else:
				s=s+t[2]
		else:
#			s=s+t[2]
			if iturn%2==1:
				s=t[2]+s
			else:
				s=s+t[2]

if iturn%2==1:
	s=s[::-1]
print (s)

### FIXED CODE ###

s=input()
q= int(input())

top=""
btm=""

iturn=0
for iq in range(1,q+1):
	t=input().split()
	if t[0]=='1':
		iturn=iturn+1   	
	else:
		iturn2=iturn%2
		if (t[1]=='1' and iturn2==0) or (t[1]=='2' and iturn2==1):
#			s=t[2]+s
#			s='{}{}'.format(t[2],s)
			top=t[2]+top
		else:
#			s=s+t[2]
#			s='{}{}'.format(s,t[2])
			btm=btm+t[2]

if iturn%2==0:
	s=top+s+btm
else:
	s=btm[::-1]+s[::-1]+top[::-1]
print (s)
### BUGGY CODE ###

n=int(input())
a=[int(input()) for i in range(n)]
for i in a:
    l=a.copy()
    l.remove(i)
    print(max(l))

### FIXED CODE ###

n=int(input())
a=[int(input()) for i in range(n)]
l=sorted(a)
m=l[-1]
n=l[-2]
for i,value in enumerate(a):
    if value!=m:
        print(m)
    else:
        print(n)
### BUGGY CODE ###

INF = 10**18

N, Ma, Mb = map(int, input().split())
sol = [tuple(map(int, input().split())) for _ in range(N)]

if N % 2 == 1:
    sol.append((0, 0, 0))
    N += 1

M = N // 2

sol1 = sol[:M]
sol2 = sol[M:]

S1 = []
S2 = []

for i in range(2**M):
    A1, B1, C1 = 0, 0, 0
    A2, B2, C2 = 0, 0, 0
    for j in range(M):
        if (i >> j) & 1:
            a1, b1, c1 = sol1[j]
            a2, b2, c2 = sol2[j]
            A1 += a1
            B1 += b1
            C1 += c1
            A2 += a2
            B2 += b2
            C2 += c2
    S1.append((A1, B1, C1))
    S2.append((A2, B2, C2))

D = dict()
S2.sort(key=lambda x: x[2], reverse=True)

res = INF

for i in range(2**M):
    a, b, c = S2[i]
    x = Mb * a - Ma * b
    if x == 0 and c > 0:
        res = min(res, c)
    if not x in D or c > 0:
        D[x] = c



for i in range(2**M):
    a, b, c = S1[i]
    x = Ma * b - Mb * a
    if x == 0 and c > 0:
        res = min(res, c)
    if x in D and D[x] + c > 0:
        res = min(res, D[x] + c)

print(res if res != INF else -1)

### FIXED CODE ###

INF = 10**18

def solve(N, Ma, Mb, sol):
    if N % 2 == 1:
        sol.append((0, 0, 0))
        N += 1

    M = N // 2

    sol1 = sol[:M]
    sol2 = sol[M:]

    S1 = []
    D = dict()
    res = INF

    for i in range(2**M):
        A1, B1, C1 = 0, 0, 0
        A2, B2, C2 = 0, 0, 0
        for j in range(M):
            if (i >> j) & 1:
                a1, b1, c1 = sol1[j]
                a2, b2, c2 = sol2[j]
                A1 += a1
                B1 += b1
                C1 += c1
                A2 += a2
                B2 += b2
                C2 += c2
        S1.append((A1, B1, C1))
        x = Mb * A2 - Ma * B2
        if x == 0 and C2 > 0:
            res = min(res, C2)
        if not x in D or 0 < C2 < D[x]:
            D[x] = C2

    for i in range(2**M):
        a, b, c = S1[i]
        x = Ma * b - Mb * a
        if x == 0 and c > 0:
            res = min(res, c)
        if x in D and D[x] + c > 0:
            res = min(res, D[x] + c)

    return res

N, Ma, Mb = map(int, input().split())
sol = [tuple(map(int, input().split())) for _ in range(N)]

res = solve(N, Ma, Mb, sol)

print(res if res != INF else -1)
### BUGGY CODE ###

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

def check(X):
  idx = [0]
  ltr = [0]
  for a in A:
    if idx[-1] < a:
      idx += [a]
      ltr += [0]
    else:
      while True:
        while idx[-1] > a:
          idx.pop()
          ltr.pop()
        if idx[-1] != a:
          idx += [a]
          ltr += [0]
        if idx[-1] == 0:
          return False
        ltr[-1] += 1
        if ltr[-1] < X:
          break
        a -= 1
        idx.pop()
        ltr.pop()
  return ltr[0] == 0

t = [0, N]
while t[1] - t[0] > 1:
  mid = (t[0] + t[1]) // 2
  t[check(mid)] = mid
print(t[1])

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
if A == sorted(A) and len(A) == len(set(A)):
  print(1)
  exit(0)

def check(X):
  idx = [0]
  ltr = [0]
  for a in A:
    if idx[-1] < a:
      idx.append(a)
      ltr.append(0)
    else:
      while True:
        while idx[-1] > a:
          idx.pop()
          ltr.pop()
        if idx[-1] != a:
          idx.append(a)
          ltr.append(0)
        if idx[-1] == 0:
          return False
        ltr[-1] += 1
        if ltr[-1] < X:
          break
        a = idx[-1] - 1
        idx.pop()
        ltr.pop()
  return ltr[0] == 0

t = [1, N]
while t[1] - t[0] > 1:
  mid = (t[0] + t[1]) // 2
  t[check(mid)] = mid
print(t[1])
### BUGGY CODE ###

def solve(n,x,k):
  ans=-10**20
  s=0
  sx=sum(x)
  for i in range(n):
    if (i+1)>k:break
    s+=x[i]
    d=((k-i-1)//n)*sx
    ans=max(ans,s+d,s)
  return ans

n,k=map(int,input().split())
p=list(map(lambda x:int(x)-1,input().split()))
c=list(map(int,input().split()))
ans=-10**20
for i in range(n):
  x=[c[i]]
  j=p[i]
  while i!=j:
    x.append(c[j])
    j=p[j]
  x=x[1:]+[x[0]]
  ans=max(ans,solve(len(x),x,k))
print(ans)


### FIXED CODE ###

def solve(n,x,k):
  ans=-10**20
  s=0
  sx=sum(x)
  for i in range(n):
    if (i+1)>k:break
    s+=x[i]
    d=((k-i-1)//n)*sx
    ans=max(ans,s+d,s)
  return ans

n,k=map(int,input().split())
p=list(map(lambda x:int(x)-1,input().split()))
c=list(map(int,input().split()))
ans=-10**20
for i in range(n):
  x=[c[i]]
  j=p[i]
  while i!=j:
    x.append(c[j])
    j=p[j]
  x=x[1:]+[x[0]]
  ans=max(ans,solve(len(x),x,k))
print(ans)
### BUGGY CODE ###

import copy
import sys

def main():
    n, k = map(int, input().split())
    A = list(map(int, input().split()))

    for m in range(k):
        B = [1] * n
        for i in range(n):
            for j in range(A[i]):
                if (i+1)+(j+1) < n+1:
                    B[(i+1)+(j+1)-1] += 1
                if (i+1)-(j+1) > 0:
                    B[(i+1)-(j+1)-1] += 1

        A = copy.deepcopy(B)

    print(*A)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import copy
import sys
import math

def main():
    n, k = map(int, input().split())
    A = list(map(int, input().split()))
    B = [0] * n

    # k_max = 1 + math.ceil(math.log10(n))

    for i in range(min(k, 41)):
        for j in range(n):
            l = max(0, j-A[j]) #座標iの電球が照らす範囲の左端
            r = min(n-1, j+A[j]) #座標iの電球が照らす範囲の右端
            B[l] += 1
            if (r+1 < n):
                B[r+1] -= 1 # 後ほど累積和にしたときに、照らす範囲の右端より外には影響が及ばないようにあらかじめ1引いておく

        for j in range(n-1):
            B[j+1] += B[j]

        A = copy.deepcopy(B)
        B = [0] * n

    print(*A)

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

n = int(input())
li = list(map(int,input().split()))
ans = 0

import math
import bisect
import collections
c = collections.Counter(li)
li = list(set(li))
li.sort()
while len(li)>0:
    ba = li.pop(-1)
    if c[ba]>1:
        continue
    #s_ba = math.ceil(math.sqrt(ba))+1
    #index = bisect.bisect_right(li, s_ba)
    tmp_li = li
    #print(ba,tmp_li)
    for tt in tmp_li:
        if ba%tt == 0:
            break
    else:
        ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
li = list(map(int,input().split()))
ans = 0
cnt_li = [0]*(10**6+1)

import math
import bisect
import collections
c = collections.Counter(li)
li = list(set(li))
li.sort()

for l in li:
    for x in range(2,10**7):
        if x*l > (10**6):
            break
        else:
            cnt_li[x*l] += 1


while len(li)>0:
    ba = li.pop(-1)
    if c[ba]>1:
        continue
    if cnt_li[ba] == 0:
        ans += 1
print(ans)
### BUGGY CODE ###

def lcs(a, b):
    n = len(a)
    m = len(b)
    dp = [[0] * (m + 1) for _ in range(n + 1)]

    for i in range(n):
        for j in range(m):
            if a[i] == b[j]:
                dp[i + 1][j + 1] = dp[i][j] + 1
            else:
                dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])

    lcs_str = ''
    i, j = n, m
    while i >= 1 and j >= 1:
        if a[i - 1] == b[j - 1]:
            lcs_str += a[i - 1] #or b[j - 1]
            i -= 1
            j -= 1
        else:
            if dp[i - 1][j] > dp[i][j - 1]:
                i -= 1
            else:
                j -= 1

    return lcs_str[::-1]


s = input()
t = input()
print(lcs(s, t))

### FIXED CODE ###

def lcs(a, b):
    n = len(a)
    m = len(b)
    dp = [[0] * (m + 1) for _ in range(n + 1)]
 
    for i in range(n):
        for j in range(m):
            if a[i] == b[j]:
                dp[i + 1][j + 1] = dp[i][j] + 1
            else:
                dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])
 
    lcs_str = ''
    i, j = n, m
    while i >= 1 and j >= 1:
        if a[i - 1] == b[j - 1]:
            lcs_str += a[i - 1] #or b[j - 1]
            i -= 1
            j -= 1
        else:
            if dp[i - 1][j] > dp[i][j - 1]:
                i -= 1
            else:
                j -= 1
 
    return lcs_str[::-1]
 
 
s = input()
t = input()
print(lcs(s, t))
### BUGGY CODE ###

# writer解(c++)を写経した．answerのfor文のところ何やってるかさっぱりわかりませんが…
# https://atcoder.jp/contests/m-solutions2020/submissions/15122924
import sys
input = sys.stdin.readline
INF = 10**13


def main():
    N = int(input())
    T = [[int(i) for i in input().split()] for j in range(N)]
    X_dist = [[0]*N for _ in range(1 << N)]
    Y_dist = [[0]*N for _ in range(1 << N)]

    # bitという道路群を建設したときの，各集落の評価距離
    # bit 001001 とかの1が立っている集落に道を作る
    for bit in range(1 << N):
        cur_x = [0]
        cur_y = [0]
        for i in range(N):
            if bit & (1 << i):
                cur_x.append(T[i][0])
                cur_y.append(T[i][1])
        for i, (x, y, p) in enumerate(T):
            X_dist[bit][i] = p*min(abs(cx - x) for cx in cur_x)
            Y_dist[bit][i] = p*min(abs(cy - y) for cy in cur_y)

    # これはなに？
    answer = [INF] * (N+1)
    for i in range(1 << N):
        cnt = 0
        for j in range(N):
            if (i >> j) & 1:
                cnt += 1
        for j in range(i+1)[::-1]:
            j &= i
            cost = 0
            for k in range(N):
                if not((i >> k) & 1):
                    cost += min(X_dist[j][k], Y_dist[i - j][k])
            answer[cnt] = min(answer[cnt], cost)

    for ans in answer:
        print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

# writer解(c++)を写経した．answerのfor文のところ何やってるかさっぱりわかりませんが…
# https://atcoder.jp/contests/m-solutions2020/submissions/15122924
import sys
input = sys.stdin.readline
INF = 10**13


def main():
    N = int(input())
    X = []
    Y = []
    P = []
    for _ in range(N):
        a, b, c = (int(i) for i in input().split())
        X.append(a)
        Y.append(b)
        P.append(c)
    X_dist = [[0]*N for _ in range(1 << N)]
    Y_dist = [[0]*N for _ in range(1 << N)]

    # bitという道路群を建設したときの，各集落の評価距離
    # bit 001001 とかの1が立っている集落に道を作る
    for bit in range(1 << N):
        for i in range(N):
            X_dist[bit][i] = P[i]*abs(X[i])
            Y_dist[bit][i] = P[i]*abs(Y[i])
            for k in range(N):
                if bit & (1 << k):
                    X_dist[bit][i] = \
                        min(X_dist[bit][i], P[i]*abs(X[i] - X[k]))
                    Y_dist[bit][i] = \
                        min(Y_dist[bit][i], P[i]*abs(Y[i] - Y[k]))

    # これはなに？
    answer = [INF] * (N+1)
    for i in range(1 << N):
        cnt = 0
        for j in range(N):
            if (i >> j) & 1:
                cnt += 1
        j = i
        while j >= 0:
            j &= i
            cost = 0
            for k in range(N):
                if not((i >> k) & 1):
                    cost += min(X_dist[j][k], Y_dist[i - j][k])
            answer[cnt] = min(answer[cnt], cost)
            j -= 1

    for ans in answer:
        print(ans)


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

max = 10**18
n = int(input())
A = list(map(int,input().split()))
ans = A[0]
for i in A[1:]:
    ans *= i

if ans > max:
    print('-1')
else:
    print(ans)


### FIXED CODE ###

MAX = pow(10,18)
def main():
    N = int(input())
    A = list(map(int,input().split()))

    if 0 in A:
        print(0)
        return

    ans = 1
    for a in A:
        ans *= a
        if ans > MAX:
            print(-1)
            return

    print(ans)

main()
### BUGGY CODE ###

N, M = [int(c) for c in input().split()]
a = [int(input()) for _ in range(M)]

dp = [0, 1]

for i in range(N):
    if i+1 in a:
        dp.append(0)
    else:
        dp.append(dp[i]+dp[i+1])

print(dp[-1] % 1000000007)

### FIXED CODE ###

N, M = [int(c) for c in input().split()]
a = [int(input()) for _ in range(M)]+[-1]
j=0

dp = [0, 1]

for i in range(N):
    if i+1 == a[j]:
        dp.append(0)
        while i+1==a[j]:
            j+=1
    else:
        dp.append((dp[i]+dp[i+1]) % 1000000007)

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

s=list(input())
t=["","",""]
s=t+s+t

c=0
i=0
while(len(s)>i):
    if s[i]=="A" and s[i+1]=="B" and s[i+2]=="C" :
        s[i]="B"
        s[i+1]="C"
        s[i+2]="A"
        i-=2
        c+=1
    i+=1

print(c)

### FIXED CODE ###

s = input().replace('BC', 'D')
 
acc = 0
ans = 0
for c in s:
    if c == 'B' or c == 'C':
        acc = 0
        continue
    elif c == 'A':
        acc += 1
    else:
        ans += acc
print(ans)
### BUGGY CODE ###

from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall
n,x,y = list(map(int, input().split()))

graph = []
for i in range(n):
    g1 = [0]*n
    if i-1 >= 0:
        g1[i-1] = 1
    if i+1 <= n-1:
        g1[i+1] = 1
    graph.append(g1)

graph[x-1][y-1] = 1
graph[y-1][x-1] = 1

graph = csr_matrix(graph)
dist_matrix, predecessors = floyd_warshall(csgraph=graph, directed=False, return_predecessors=True)

ans = [0]*(n)
for i in range(n):
    for j in range(i+1, n):
        ans[int(dist_matrix[i][j])] += 1

for i in ans[1:]:
    print(i)

### FIXED CODE ###

n,x,y = list(map(int, input().split()))

ans = [0]*(n)
for i in range(n-1):
    for j in range(i+1, n):
        r1 = min(j-i, (abs(x-i-1) + 1 +  abs(y-j-1) ), (abs(y-i-1) + 1 +  abs(x-j-1) ) )
        ans[r1] += 1

for i in ans[1:]:
    print(i)
### BUGGY CODE ###

class UnionFind:
    def __init__(self, n):
        self.par = [-1 for i in range(n+1)]
        self.size = [1 for i in range(n+1)]
    # 検索
    def find(self, x):
        path = []
        curr = x
        # 親ノードの手前で止まる(どの根に紐づくかの情報を持ちながら)
        while self.par[curr] != -1:
            # 自分自身じゃない場合は、上にさかのぼって検索(再帰的に)
            path.append(curr)
            curr = self.par[curr]
        for p in path:
            self.par[p] = curr
        return curr

    # 結合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        self.par[y] = x
        self.size[x] += self.size[y]
        self.size[y] = 0

    # 判定
    def judge(self,x,y):
        return self.find(x) == self.find(y)

N, M = map(int,input().split())
pairs = [tuple(map(int,input().split())) for _ in range(M)]
uf = UnionFind(N)
ans = [N*(N-1)//2]
for a,b in reversed(pairs):
    cnt = 0
    if not uf.judge(a,b):
        uf.union(a,b)
    for s in uf.size:
        if s > 1:
            cnt += s*(s-1)//2
    ans.append(ans[0]-cnt)
for a in reversed(ans[:-1]):
    print(a)


### FIXED CODE ###

class UnionFind:
    def __init__(self, n):
        self.par = [-1 for i in range(n+1)]
        self.size = [1 for i in range(n+1)]
    # 検索
    def find(self, x):
        path = []
        curr = x
        # 親ノードの手前で止まる(どの根に紐づくかの情報を持ちながら)
        while self.par[curr] != -1:
            # 自分自身じゃない場合は、上にさかのぼって検索(再帰的に)
            path.append(curr)
            curr = self.par[curr]
        for p in path:
            self.par[p] = curr
        return curr

    # 結合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        self.par[y] = x
        self.size[x] += self.size[y]
        self.size[y] = 1

    # 判定
    def judge(self,x,y):
        return self.find(x) == self.find(y)

N, M = map(int,input().split())
pairs = [tuple(map(int,input().split())) for _ in range(M)]
uf = UnionFind(N)
p = N*(N-1)//2
ans = [p]
for a,b in reversed(pairs[1:]):
    if not uf.judge(a,b):
        size_a = uf.size[uf.find(a)]
        size_b = uf.size[uf.find(b)]
        uf.union(a,b)
        size_a_update = uf.size[uf.find(a)]
        p = p + size_a*(size_a-1)//2 + size_b*(size_b-1)//2 - size_a_update*(size_a_update-1)//2

    ans.append(p)
for a in reversed(ans):
    print(a)
### BUGGY CODE ###

#一時間以上かかった
#一つだけTLE

import math
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r)*math.factorial(r))

n,m=[int(i) for i in input().split()]
a1=[int(input()) for i in range(m)]
a1.append(n+1)
c1=1
a2=0
for i in range(m+1):
    a3=a1[i]-1-a2
    c2=0
    for j in range(0,a3//2+1):
        c2+=combinations_count(a3-j,j)
    c1=(c1*c2)%(1000000007)
    a2=a1[i]+1
    if c1==0:
        break



print(c1)


### FIXED CODE ###

#フィボナッチ数列か…
#c問題も解けないのか…
#典型問題なんだろうな
#踏めない段の分は除いて考えれば良い
n,m=input().split()
n,m=int(n),int(m)
ax=[1]*(n+1)
for i in range(m):
    ax[int(input())]=0
bx=[1,1]
for i in range(2,n+1):
    if ax[i-1]==1:
        f1=bx[i-1]
    else:
        f1=0
    if ax[i-2]==1:
        f2=bx[i-2]
    else:
        f2=0
    bx.append((f1+f2)%(10**9+7))

print(bx[n])
### BUGGY CODE ###

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

ans = []
if not n % 2:
    ans.append(a[0])
    a = a[1:]

while len(a) > 1:
    ans.insert(0, a[0])
    ans.append(a[1])
    a = a[2:]

if len(a):
    ans.insert(0, a[0])

print(*ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = []
if n % 2:
    ans += a[:1]
    a = a[1:]
ans += a[1::2]
ans.reverse()
ans += a[::2]
print(*ans)