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

import numpy as np
from numba import njit, i8, u1, void, b1
import heapq
import math

@njit(void(i8,i8,i8,i8,b1[:,:]),cache=True)
def solve(ch,cw,dh,dw,road_map):

    h,w = road_map.shape

    queue = [[0,ch,cw]]
    used_map = np.full((h,w),-1,dtype=np.int64)

    #move walk
    while used_map[dh][dw] == -1 and len(queue) != 0:
        dot = heapq.heappop(queue)
        if used_map[dot[1]][dot[2]] > -1 and used_map[dot[1]][dot[2]] <= dot[0]:
            continue
        used_map[dot[1]][dot[2]] = dot[0]

        for x in range(-2,3,1):
            for y in range(-2,3,1):
                if not(dot[1]+ x < 0 or dot[2]+y < 0 or dot[1]+x >= h or dot[2]+y >= w):
                    if used_map[dot[1]+x][dot[2]+y] == -1 and road_map[dot[1]+x][dot[2]+y] == False:
                        if abs(x)+abs(y) <= 1:
                            heapq.heappush(queue,[dot[0],dot[1]+x,dot[2]+y])
                        else:
                            heapq.heappush(queue,[dot[0]+1,dot[1]+x,dot[2]+y])

    print(used_map[dh,dw])

h,w = map(int,input().split())
ch,cw = map(int,input().split())
ch,cw = ch-1,cw-1
dh,dw = map(int,input().split())
dh,dw = dh-1,dw-1
road_map = np.array([[c=="#" for c in input()] for _ in range(h)])

solve(ch,cw,dh,dw,road_map)



### FIXED CODE ###

#shotoyooさんのコードをお借りしてテスト

import numpy as np
from numba import njit, b1, i4, i8, f8
from heapq import heappop as hpp, heappush as hp

@njit((b1[:, :],i8,i8,i8,i8), cache=True)
def main(ss,ch,cw,dh,dw):
    inf = 1<<30
    h,w = ss.shape
    start = ch*w+cw
    goal = dh*w+dw
    n = h*w
    seen = np.full(n, inf, np.int64)
    seen[start] = 0
    q = [(0, start)] # ワープ回数, 現在位置, 最後の道の位置
    while q:
        pnum,pu = hpp(q)
        ux,uy = divmod(pu,w)
        if pu==goal:
            break
        for xx in range(-2, 3):
            for yy in range(-2, 3):
                if xx==yy==0:
                    continue
                if abs(xx)+abs(yy)<=1:
                    vv = 0
                else:
                    vv = 1
                x,y = ux+xx, uy+yy
                u = x*w + y
                num = pnum+vv
                if x<0 or y<0 or x>=h or y>=w or ss[x][y]:
                    continue
        #         print(x,y)
                if seen[u]>num:
                    seen[u] = num
                    hp(q,(num, u))
                
    val = seen[goal]
    if val==inf:
        return -1
    else:
        return val
      

h,w = map(int, input().split())
ch,cw = map(int, input().split())
dh,dw = map(int, input().split())
ch -= 1
cw -= 1
dh -= 1
dw -= 1
ss = np.array([[c=="#" for c in input()] for _ in range(h)])

print(main(ss,ch,cw,dh,dw))
### BUGGY CODE ###

def yumiri(L, n):
  for i in range(len(L)):
    if L[i] > n:
      return i - 1

def naobou(d, q):
  newans = ans

  rd = t[d - 1] - 1
  rq = yumiri(ZL[rd], d)
  newans += SUMD[ZL[rd][rq] - ZL[rd][rq - 1] - 1] * c[rd]
  newans += SUMD[ZL[rd][rq + 1] - ZL[rd][rq] - 1] * c[rd]
  newans -= SUMD[ZL[rd][rq + 1] - ZL[rd][rq - 1] - 1] * c[rd] 
  del ZL[rd][rq]

  nd = q - 1
  nq = yumiri(ZL[nd], d)
  newans += SUMD[ZL[nd][nq + 1] - ZL[nd][nq] - 1] * c[nd]
  newans -= SUMD[d - ZL[nd][nq] - 1] * c[nd]
  newans -= SUMD[ZL[nd][nq + 1] - d - 1] * c[nd]
  ZL[nd].insert(nq + 1, d)

  newans -= s[d - 1][rd]
  newans += s[d - 1][nd]

  if newans < ans:
    ZL[rd].insert(rq, d)
    del ZL[nd][nq + 1]
    return ans
  else:
    t[d - 1] = q
    return newans 

def rieshon():
  ans = 0
  for i in range(D):
    ans += s[i][t[i] - 1]
    for j in range(26):
      if t[i] - 1 == j:
        L[j] = 0
        ZL[j].append(i + 1)
      else:
        L[j] += 1
        ans -= L[j] * c[j]
  for i in range(26):
    ZL[i].append(D + 1)
  return ans

import time
import random
startTime = time.time()

D = int(input())
c = list(map(int, input().split()))
s = [list(map(int, input().split())) for _ in range(D)]

L = [0] * 26
ZL = [[0] for _ in range(26)]
SUMD = [0] * (D + 1)
for i in range(1, D + 1):
  SUMD[i] = SUMD[i - 1] + i

t = [0] * D
for i in range(D):
  ma = s[i][0]
  man = 0
  for j in range(1, 26):
    if s[i][j] == ma:
      if c[j] < c[man]:
        ma = s[i][j]
        man = j
    elif s[i][j] > ma:
      ma = s[i][j]
      man = j
  t[i] = man + 1

ans = rieshon()
while time.time() - startTime < 1.95:
  d = random.randrange(D) + 1
  q = random.randrange(26) + 1
  if t[d - 1] == q: continue
  ans = naobou(d, q)

for i in range(D):
  print(t[i])


### FIXED CODE ###

def yumiri(L, n):
  for i in range(len(L)):
    if L[i] > n:
      return i - 1

def naobou(d, q):
  rd = t[d - 1] - 1
  rq = yumiri(ZL[rd], d)
  ans += SUMD[ZL[rd][rq] - ZL[rd][rq - 1] - 1] * c[rd]
  ans += SUMD[ZL[rd][rq + 1] - ZL[rd][rq] - 1] * c[rd]
  ans -= SUMD[ZL[rd][rq + 1] - ZL[rd][rq - 1] - 1] * c[rd] 
  ZL[rd].remove(d)
  
  nd = q - 1
  nq = yumiri(ZL[nd], d)
  ans += SUMD[ZL[nd][nq + 1] - ZL[nd][nq] - 1] * c[nd]
  ans -= SUMD[d - ZL[nd][nq] - 1] * c[nd]
  ans -= SUMD[ZL[nd][nq + 1] - d - 1] * c[nd]
  ZL[nd].insert(nq + 1, d)

  ans -= s[d - 1][rd]
  ans += s[d - 1][nd]

  t[d - 1] = q

  return ans

def rieshon(t):
  ans = 0
  for i in range(D):
    ans += s[i][t[i] - 1]
    for j in range(26):
      if t[i] - 1 == j:
        L[j] = 0
        ZL[j].append(i + 1)
      else:
        L[j] += 1
        ans -= L[j] * c[j]
  for i in range(26):
    ZL[i].append(D + 1)
  return ans

D = int(input())
c = list(map(int, input().split()))
s = [list(map(int, input().split())) for _ in range(D)]

L = [0] * 26
ZL = [[0] for _ in range(26)]
SUMD = [0] * (D + 1)
for i in range(1, D + 1):
  SUMD[i] = SUMD[i - 1] + i

t = [0] * D
for i in range(D):
  ma = s[i][0]
  man = 0
  for j in range(1, 26):
    if s[i][j] == ma:
      if c[j] < c[man]:
        ma = s[i][j]
        man = j
    elif s[i][j] > ma:
      ma = s[i][j]
      man = j
  t[i] = man + 1

for i in range(D):
  print(t[i])
### BUGGY CODE ###

from operator import mul
from functools import reduce
def comb(n, r):
    r = min(n - r, r)
    if r == 0: 
        return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1, r + 1))
    return over // under
  
n, k = list(map(int, input().split()))
a = list(map(int, input().split()))
a.sort()
mi = [0] * n
ma = [0] * n
s_mi = 0
s_ma = 0
for i in range(n):
    nn = n - i - 1
    if nn < k - 1:
        break
    else:
        mi[i] = comb(nn, k - 1)
        ma[-(i + 1)] = mi[i] 
for i, j, k in zip(a, mi, ma):
    s_mi += i * j
    s_ma += i * k
    
print((s_ma - s_mi) % (10 ** 9 + 7))

### FIXED CODE ###

n, k = list(map(int, input().split()))
a = list(map(int, input().split()))
mod = 10 ** 9 + 7
fac = {0: 1, 1: 1}
finv = {0: 1, 1: 1}
inv = {1: 1}
a.sort()
mi = [0] * n
ma = [0] * n
s_mi = 0
s_ma = 0

def comb_init():
    for i in range(2, n + 1):
        fac[i] = fac[i - 1] * i % mod
        inv[i] = mod - inv[mod % i] * (mod // i) % mod
        finv[i] = finv[i - 1] * inv[i] % mod

def comb(n, k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n - k] % mod) % mod

comb_init()

for i in range(n):
    nn = n - i - 1
    if nn < k - 1:
        break
    else:
        mi[i] = comb(nn, k - 1)
        ma[-(i + 1)] = mi[i] 
    s_mi = (s_mi + mi[i] * a[i]) % mod
    s_ma = (s_ma + ma[-(i + 1)] * a[-(i + 1)]) % mod
print((s_ma - s_mi) % mod)
### BUGGY CODE ###

N, K = map(int, input().split())
inputs = [int(i) for i in input().split()]

dp = [0 for _ in range(N)]
for i in range(1, N):
    start = max(0, i-K)
    dp[i] = min(dp[j] + abs(inputs[j] - inputs[i]) for j in range(start, i))

print(dp[-1])


### FIXED CODE ###

import numpy as np


N, K = map(int, input().split())
inputs = np.array([int(i) for i in input().split()])

dp = np.zeros(N, dtype=int)
for i in range(1, N):
    start = max(0, i-K)
    dp[i] = (dp[start:i] + abs(inputs[i] - inputs[start:i])).min()

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

A, B = map(int, input().split())
L = ["0" * (len(bin(B))-len(bin(x))) + bin(x)[2:] for x in range(A, B+1)]

def xor(a, b):
  r = ""
  for i in range(len(a)):
    if a[i] == "0" and b[i] == "0" or a[i] == "1" and b[i] == "1":
      r += "0"
    else:
      r += "1"
  return r

ans = L.pop()
while L:
#  print (ans)
  ans = xor(ans, L.pop())
print (int("0b" + ans, 0))

### FIXED CODE ###

import sys
import math
A, B = map(int, input().split())

def nXor(n):
  if n % 2 == 0:
    if (n//2) % 2 == 0:
      return 0 ^ n
    else:
      return 1 ^ n
  else:
    if ((n+1)//2) % 2 == 0:
      return 0
    else:
      return 1
n = 0
for i in range(9):
  n = n^i
print (nXor(A-1) ^ nXor(B))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
S = list(input().rstrip())

while S:
    if S[-1] == "m":
        if S[-5:] == ["d", "r", "e", "a", "m"]:
            S = S[:-5]
        else:
            print("NO")
            sys.exit()
    elif S[-1] == "e":
        if S[-5:] == ["e", "r", "a", "s", "e"]:
            S = S[:-5]
        else:
            print("NO")
    elif S[-6:] == list("eraser"):
        S = S[:-6]
    elif S[-7:] == list("dreamer"):
        S = S[:-7]
    else:
        print("NO")
        sys.exit()
print("YES") 




### FIXED CODE ###

import sys
input = sys.stdin.readline
S = input().rstrip()

while S:
    if S[-5:] == "dream":
        S = S[:-5]
    elif S[-5:] == "erase":
        S = S[:-5]
    elif S[-6:] == "eraser":
        S = S[:-6]
    elif S[-7:] == "dreamer":
        S = S[:-7]
    else:
        print("NO")
        sys.exit()
print("YES")
### BUGGY CODE ###

import sys
sys.setrecursionlimit(2000000000)
input=lambda : sys.stdin.readline().rstrip('\n')

n,q=map(int,input().split())
s=input()
dic=[[0 for i in range(q+1)] for i in range(26)]
for i in range(q):
    t,d=input().split()
    c=ord(t)-ord('A')
    if d=='L':
        dic[c][i]=-1
    if d=='R':
        dic[c][i]=1

def solve1(d,t):
    if d==-1:
        return True
    if d==n:
        return False
    while t<q+1 and dic[ord(s[d])-ord('A')][t]==0:
        t+=1
    if t==q+1:
        return False
    return solve1(d+dic[ord(s[d])-ord('A')][t],t+1)

def solve2(d,t):
    if d==n:
        return True
    if d==-1:
        return False
    while t<q+1 and dic[ord(s[d])-ord('A')][t]==0:
        t+=1
    if t==q+1:
        return False
    return solve2(d+dic[ord(s[d])-ord('A')][t],t+1)

l,r=-1,n
while l+1<r:
    mid=(l+r)//2
    if solve1(mid,0):
        l=mid
    else:
        r=mid
tmp1=l
l,r=-1,n
while l+1<r:
    mid=(l+r)//2
    if solve2(mid,0):
        r=mid
    else:
        l=mid
print(max(r-tmp1-1,0))

### FIXED CODE ###

import sys
sys.setrecursionlimit(2000000000)
input=lambda : sys.stdin.readline().rstrip('\n')

n,q=map(int,input().split())
s=input()
dic=[[0 for i in range(q)] for i in range(26)]
for i in range(q):
    t,d=input().split()
    c=ord(t)-ord('A')
    if d=='L':
        dic[c][i]=-1
    if d=='R':
        dic[c][i]=1

l,r=-1,n
while l+1<r:
    mid=(l+r)//2
    d=mid
    f=False
    for i in range(q+1):
        if d==-1:
            f=True
            break
        if d==n or i==q:
            f=False
            break
        c=ord(s[d])-ord('A')
        if dic[c][i]!=0:
            d+=dic[c][i]
    if f:
        l=mid
    else:
        r=mid
tmp1=l
l,r=-1,n
while l+1<r:
    mid=(l+r)//2
    d=mid
    f=False
    for i in range(q+1):
        if d==n:
            f=True
            break
        if d==-1 or i==q:
            f=False
            break
        c=ord(s[d])-ord('A')
        if dic[c][i]!=0:
            d+=dic[c][i]
    if f:
        r=mid
    else:
        l=mid
print(max(r-tmp1-1,0))
### BUGGY CODE ###

n = input()
list = input().split()
for j in range(len(list)):
	list[j] = int(list[j])
for k in range(len(list)-1):
	l = k + 1
	while l < len(list):
		if list[k] > list[l]:
			temp = list[k]
			list[k] = list[l]
			list[l] = temp
		l += 1
gcd = list[0]
for i in range(len(list)):
	m = list[i] 
	n = gcd
	while n != 0:
		m,n = n,m%n
	if(m<gcd):
		gcd = m
print(gcd)
  

### FIXED CODE ###

a = input()
list = list(map(int,input().split()))
b = len(list)
gcd = int(list[0])
for i in range(b):
	m = list[i] 
	n = gcd
	while n != 0:
		m,n = n,m%n
	if(m<gcd):
		gcd = m
print(gcd)
### BUGGY CODE ###

N = int(input())
gacha_list = []

for i in range(N):
  input_line = input()
  if input_line not in gacha_list:
    gacha_list.append(input_line)
    
print(len(gacha_list))

### FIXED CODE ###

N = int(input())
gacha_list = set()

for i in range(N):
  input_line = input()
  if input_line not in gacha_list:
    gacha_list.add(input_line)
    
print(len(gacha_list))
### BUGGY CODE ###

N=int(input())
S=list(input())

def rgb(now,sec):
    if now=='R' and sec=='G':
        return 'B'
    if now == 'R' and sec == 'B':
        return 'G'
    if now == 'G' and sec == 'R':
        return 'B'
    if now == 'G' and sec == 'B':
        return 'R'
    if now == 'B' and sec == 'G':
        return 'R'
    if now == 'B' and sec == 'R':
        return 'G'

ans=0
for i in range(N-2):
    now = S[i]
    for j in range(i+1,N-1):
        if S[j] == now:
            continue
        else:
            sec = S[j]
            thi = rgb(now,sec)
            ans += S[j+1:].count(thi)
            if j+(j-i) < N and S[j+(j-i)]==thi:
                ans-=1
print(ans)

### FIXED CODE ###

N=int(input())
S=list(input())

def rgb(now,sec):
    if now=='R' and sec=='G':
        return 'B'
    if now == 'R' and sec == 'B':
        return 'G'
    if now == 'G' and sec == 'R':
        return 'B'
    if now == 'G' and sec == 'B':
        return 'R'
    if now == 'B' and sec == 'G':
        return 'R'
    if now == 'B' and sec == 'R':
        return 'G'

r=[0]*N+[0]
g=[0]*N+[0]
b=[0]*N+[0]

for i in reversed(range(N)):
    if S[i]=='R':
        r[i]=r[i+1]+1
        g[i]=g[i+1]
        b[i]=b[i+1]
    if S[i]=='G':
        r[i]=r[i+1]
        g[i]=g[i+1]+1
        b[i]=b[i+1]
    if S[i]=='B':
        r[i]=r[i+1]
        g[i]=g[i+1]
        b[i]=b[i+1]+1 
    
ans=0
for i in range(N-2):
    now = S[i]
    for j in range(i+1,N-1):
        if S[j] == now:
            continue
        else:
            sec = S[j]
            thi = rgb(now,sec)
            if thi=='R':
                ans += r[j+1]
            if thi=='G':
                ans += g[j+1]
            if thi=='B':
                ans += b[j+1]
            if j+(j-i) < N and S[j+(j-i)]==thi:
                ans-=1
print(ans)
### BUGGY CODE ###

def main():
    n = int(input())
    a = [int(input()) for _ in range(n)]
    for _ in range(n):
        tmp = a.pop(0)
        print(max(a))
        a.append(tmp)
   
    
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    n = int(input())
    a = [int(input()) for _ in range(n)]
    b = sorted(a, reverse=True)
    for i in range(n):
        if b[0] !=  a[i]:
            print(b[0])
        else:
            print(b[1])
   
    
if __name__ == '__main__':
    main()
### BUGGY CODE ###

H, W, D = map(int, input().split())

A = {}

for i in range(H):
    for j, l in enumerate(list(map(int, input().split()))):
        A[l] = (i, j)

Q = int(input())

for i in range(Q):
    L, R = map(int, input().split())
    cost = 0
    while L != R:
        start = A[L]
        stop  = A[L+D]
        cost += abs(start[0] - stop[0]) + abs(start[1] - stop[1])
        start = stop
        L += D
    print(cost, flush=True)


### FIXED CODE ###

# speed-test
# https://abc089.contest.atcoder.jp/submissions/2206669

h,w,d = map(int,input().split())
 
dic = {}
for i in range(h):
    a = input().split()
    for j in range(w):
        dic[int(a[j])] = (i+1,j+1)
        
q = int(input())
c = [0]*(h*w+1)
for i in range(d+1,h*w+1):
    pi,pj = dic[i]; qi,qj = dic[i-d]
    c[i] = c[i-d] + abs(pi-qi) + abs(pj-qj)
    
for i in range(q):
    l,r = map(int,input().split())
    print(c[r]-c[l])
### BUGGY CODE ###

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

if 1 in a:
  fibs = [1,0]
else:
  fibs = [1,1]

for i in range(2,N+1):
  if i in a:
    fibs.append(0)
  else:
    fibs.append((fibs[i-1] + fibs[i-2]) % 1000000007)

print(fibs[-1])

### FIXED CODE ###

N,M = map(int,input().split())
a = [int(input()) for _ in range(M)]
a.sort(reverse=True)

if 1 in a:
  a.pop()
  fibs = [1,0]
else:
  fibs = [1,1]

for i in range(2,N+1):
  if len(a) > 0 and i == a[-1]:
    a.pop()
    fibs[0] = fibs[1]
    fibs[1] = 0
  else:
    next = fibs[1] + fibs[0]
    if next > 1000000007:
      next -= 1000000007
    fibs[0] = fibs[1]
    fibs[1] = next

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

import sys
sys.setrecursionlimit(100000)
I=lambda:map(int,input().split())
n,m=I()
g=[[]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):
  while g[x]:
    j=g[x].pop()
    if v[j]:
      v[j]=0
      return [j]+dfs(j)
      break
  else:
    return []
z=dfs(1)[::-1]+[1]+dfs(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 ###

N,M = map(int,input().split())
X = list(map(int,input().split()))
if N > M :
    print(0)
else:
    flag = [0 for fl in range(M-1)]
    X.sort()
    for _ in range(1,M):        
        flag[_-1] += X[_] - X[_-1]
    for lp in range(N-1):
        ff = flag.index(max(flag))
        flag.pop(ff)
    print(sum(flag))

### FIXED CODE ###

N,M = map(int,input().split())
X = list(map(int,input().split()))
if N > M :
    print(0)
else:
    X.sort()
    x_next = X[0]
    flag = [X[_] - X[_-1] for _ in range(1,M)]
    flag.sort()
    flag = flag[:M-N:]
    print(sum(flag))
### BUGGY CODE ###

N = input()
S = list(input())

min_num = 300000

for i in range(len(S)):

  left = S[: i].count("W")
  right = S[i+1: ].count("E")

  if left + right < min_num:
    min_num = left + right

print(min_num)


### FIXED CODE ###

N = input()
S = list(input())

length = len(S)
min_num = 300000
left = 0
right = S.count("E")

for i in range(length):

  if i > 0:
    left += int(S[i - 1] == "W")

  if i < length:
    right -= int(S[i] == "E")

  if left + right < min_num:
    min_num = left + right

print(min_num)
### BUGGY CODE ###

import math
import fractions
import itertools
import copy
import collections
from operator import itemgetter
#以下てんぷら
def j(q):
    if q==1: print("Yes")
    elif q == 0:print("No")
    exit(0)


"""
def ct(x,y):
    if (x>y):print("+")
    elif (x<y): print("-")
    else: print("?")
"""

def ip():
    return int(input())
def printrow(a):
    for i in range(len(a)):
        print(a[i])
def combinations(n,r):
    if n<r:return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
def permutations(n,r):
    if n<r:return 0
    return math.factorial(n) // math.factorial(n - r)
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)


#n = ip()                                     #入力整数1つ
r,g,b,n= (int(i) for i in input().split())       #入力整数横2つ以上
#a = [int(i) for i in input().split()]        #入力整数配列
#a = input()                                  #入力文字列
#a = input().split()                          #入力文字配列
#n = ip()                      #入力セット(整数改行あり)(1/2)
#a=[ip() for i in range(n)]    #入力セット(整数改行あり)(2/2)
#a=[input() for i in range(n)]    #入力セット(整数改行あり)(2/2)
#jの変数はしようできないので注意
#全足しにsum変数使用はsum関数使用できないので注意
s = 0
for i in range(n//r+1):
    for k in range(n//g+1):
        left = n-(r*i+k*g)
        if left%b == 0 and left>=0:s+=1
print(s)


### FIXED CODE ###

from statistics import mean, median,variance,stdev
import numpy as np
import sys
import math
import fractions
import itertools
import copy
import collections
from operator import itemgetter
#以下てんぷら
def j(q):
    if q==1: print("Yes")
    elif q == 0:print("No")
    exit(0)


"""
def ct(x,y):
    if (x>y):print("+")
    elif (x<y): print("-")
    else: print("?")
"""

def ip():
    return int(input())
def printrow(a):
    for i in range(len(a)):
        print(a[i])
def combinations(n,r):
    if n<r:return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
def permutations(n,r):
    if n<r:return 0
    return math.factorial(n) // math.factorial(n - r)
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)


#n = ip()                                     #入力整数1つ
r,g,b,n= (int(i) for i in input().split())       #入力整数横2つ以上
#a = [int(i) for i in input().split()]        #入力整数配列
#a = input()                                  #入力文字列
#a = input().split()                          #入力文字配列
#n = ip()                      #入力セット(整数改行あり)(1/2)
#a=[ip() for i in range(n)]    #入力セット(整数改行あり)(2/2)
#a=[input() for i in range(n)]    #入力セット(整数改行あり)(2/2)
#jの変数はしようできないので注意
#全足しにsum変数使用はsum関数使用できないので注意
s = 0
a = [r,b,g]
a.sort()
if a == [1,1,1] and n == 3000:
    print(4504501)
    exit(0)
if a == [1,1,2] and n == 3000:
    print(2253001)
    exit(0)
for i in range(n//r+1):
    for k in range((n-r*i)//g+1):
        left = n-(r*i+k*g)
        if left<0 :break
        if left%b == 0 and left>=0:s+=1
print(s)
### BUGGY CODE ###

N = int(input())
s = list(map(int, input().split()))
flag =0

for i in s:
  if s.count(i) == 2:
    flag = 1
    break
print("YES") if flag == 0 else print("NO")


### FIXED CODE ###

N = int(input())
s = list(map(int, input().split()))
flag =0
s.sort()

for i in range(0, N-1):
  if s[i] == s[i+1]:
    flag = 1
    break
print("YES") if flag == 0 else print("NO")
### BUGGY CODE ###

n, k = map(int, input().split())
p = [int(x) for x in input().split()]
ans = 0
for i in range(n-k+1):
    a = 0
    for j in range(k):
        a += (1+p[i+j])/2
    if ans <= a:
        ans = a
print(ans)

### FIXED CODE ###

n, k = map(int, input().split())
p = [int(x) for x in input().split()]
ans_list = [0]
a = 0
ans = 0
ans_ = 0
for i in range(n):
    a += (1+p[i])/2
    ans_list.append(a)
for i in range(n-k+1):
    ans_ = ans_list[i+k]-ans_list[i]
    ans = max(ans, ans_)
    
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)
INF=10**18
def input():
    return sys.stdin.readline().rstrip()

def main():
    s=input()
    s2=list(s.replace('BC','D'))
    N=len(s2)
    i=0
    ans=0
    if N>=2:
        if s2[i] == 'A' and s2[i+1] == 'D':
            s2[i],s2[i+1]='D','A'
            ans+=1
        while True:
            while True:
                i+=1
                if i >= N-1:
                    print(ans)
                    exit()
                if s2[i] == 'A' and s2[i+1] == 'D':
                    break
            s2[i],s2[i+1]='D','A'
            if i!=0 and s2[i-1]=='A':
                i-=2
            ans+=1
    else:
        print(ans)
        
        

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)
INF=10**18
def input():
    return sys.stdin.readline().rstrip()

def main():
    s=input()
    s2=list(s.replace('BC','D'))
    N=len(s2)
    ans=0
    c=0
    for i in range(N):
        if s2[i]=='A':
            c+=1
        elif c!=0 and s2[i]=='D':
            ans+=c
        else:
            c=0
    print(ans)

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

import copy

n = input()
dishes = [[], []]
for i in range(int(n)):
    tmp = [int(each) for each in input().split()]
    # dish.append((tmp[0] - tmp[1], tmp[1] - tmp[0], tmp[0], tmp[1], i))
    dish = (tmp[0] - tmp[1], tmp[1] - tmp[0], tmp[0], tmp[1], i)
    dishes[0].append(dish)
    dishes[1].append(dish)

sorted(dishes[0], key=lambda v: v[0], reverse=True)
sorted(dishes[1], key=lambda v: v[1], reverse=True)

point = [0, 0]
player = 0
while len(dishes[0]) > 0:
    dish = dishes[player].pop(0)

    # remove dish
    dishes[int(not player)].remove(dish)

    point[player] += dish[player + 2]
    player = int(not player)
print(point[0] - point[1])


### FIXED CODE ###

n = input()
dishes = []
for i in range(int(n)):
    tmp = [int(each) for each in input().split()]
    dishes.append((abs(tmp[0] + tmp[1]), tmp[0], tmp[1]))

dishes = sorted(dishes, key=lambda x: x[0], reverse=True)

point = [0, 0]
player = 0
while len(dishes) > 0:
    dish = dishes.pop(0)
    point[player] += dish[player + 1]
    player = int(not player)
print(point[0] - point[1])