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

from itertools import accumulate
from bisect import bisect

def half(T, h):
    b = bisect(T,h)
    if abs(T[b-1]*2 - T[-1] - T[0]) <= abs(T[b]*2 - T[-1] - T[0]):
        return T[b-1] - T[0], T[-1]-T[b-1]
    return T[b] - T[0], T[-1]-T[b]
N = int( input())
A = list( map( int, input().split()))
S = [0] + list( accumulate(A))
ans = 10**9+1
for i in range(2, N-1):
    x, y = half(S[:i+1], S[i]//2)
    z, w = half(S[i:], (S[i] + S[-1])//2)
    m = min(x,y,z,w)
    M = max(x,y,z,w)
    if M-m < ans:
        ans = M-m
print(ans)


### FIXED CODE ###

from itertools import accumulate

N = int( input())
A = list( map( int, input().split()))
a, b = 0, 2
ans = 10**9 + 1
S = list(accumulate(A))
for i in range(1,N-2):
    while S[a] < S[i] - S[a+1]:
        a += 1
    b = max(b,i+1)
    while S[b] - S[i] < S[-1] - S[b+1]:
        b += 1
    ans = min( ans, max(S[a], S[i] - S[a], S[b] - S[i], S[-1] - S[b]) - min(S[a], S[i] - S[a], S[b] - S[i], S[-1] - S[b]))
print(ans)
### BUGGY CODE ###

import numpy
N, K = map(int, input().split())
p = numpy.array(list(map(int, input().split())))
max = 0
for i in range(N-K+1):
    temp = numpy.sum(p[i:i+K])
    if max < temp:
        max = temp
        maxno = i

exsum = 0

for i in range(K):
    temp = p[i+maxno]
    exsum += (0.5*temp*(temp+1))/temp
print(exsum)

### FIXED CODE ###

import numpy
N, K = map(int, input().split())
p = numpy.array(list(map(int, input().split())))
max = 0
nowsum = 0
for i in range(N-K+1):
    if i == 0:
        nowsum = numpy.sum(p[i:i+K])
    else:
        nowsum = nowsum - p[i-1] + p[i+K-1]
    if max < nowsum:
        max = nowsum
        maxno = i

exsum = 0

for i in range(K):
    temp = p[i+maxno]
    exsum += (0.5*temp*(temp+1))/temp
print(exsum)
### BUGGY CODE ###

# coding:utf-8
n = int(input())
a = list(map(int, input().split()))
count = [0 for _ in range(max(a) + 1)]
ans = 0

for i in a:
    if count[i] != 0:
        count[i] = 1
        continue
    for j in range(2 * i, max(a) + 1, i):
        count[j] = 1
    count[i] = 2

for i in a:
    if count[i] != 1:
        ans += 1

print(ans)


### FIXED CODE ###

# coding:utf-8
n = int(input())
a = list(map(int, input().split()))
m = max(a)
count = [0 for _ in range(m + 1)]
ans = 0

for i in a:
    if count[i] != 0:
        count[i] = 1
        continue
    for j in range(2 * i, m + 1, i):
        count[j] = 1
    count[i] = 2

for i in a:
    if count[i] != 1:
        ans += 1

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

data = input().split(" ")
data = list(map(int, data))

count=0

for x in range(data[0]+1):
    for y in range(data[0]+1):
        for z in range(data[0]+1):
            if x + y + z == data[1]:
                count+=1
print(count)

### FIXED CODE ###

data = input().split(" ")
data = list(map(int, data))

count=0

for x in range(data[0]+1):
    for y in range(data[0]+1):
        if data[0] >= (data[1]-(x+y)) >= 0:
            z = data[1]-(x+y)
            
            if x + y + z == data[1]:
                count+=1
print(count)
### BUGGY CODE ###

# D - Digits Parade

# dp[i][j] 末尾からi桁の数で、あり得るもののうち、13で割った余りがjになるものの個数。0桁スタート

S = input()

MOD = 10**9 + 7
dp = [[0]*13 for _ in range(len(S))]

if S[-1] == "?":
    for j in range(10):
        dp[0][j] = 1
else:
    for j in range(13):
        if j == int(S[-1]):
            dp[0][j] = 1

for i in range(2, len(S)+1):
    if S[-i] == "?":
        for q_number in range(10): # ?の中身としてあり得る数字
            tmp = (q_number * 10**(i-1)) % 13
            for back_number in range(13):
                dp[i-1][(tmp + back_number) % 13] += dp[i-2][back_number]
                dp[i-1][(tmp + back_number) % 13] %= MOD
    else:
        for back_number in range(13):
            tmp = (int(S[-i]) * 10**(i-1)) % 13
            dp[i-1][(tmp + back_number) % 13] += dp[i-2][back_number]
            dp[i-1][(tmp + back_number) % 13] %= MOD

print(dp[len(S)-1][5] % MOD)

### FIXED CODE ###

# D - Digits Parade

# dp[i][j] Sの大きい位からi桁の数で、あり得るもののうち、13で割った余りがjになるものの個数。0桁スタート
# 大きい位から順に始めないと13で割ったときの余りを求める計算量が大きくなる

S = input()

MOD = 10**9 + 7
dp = [[0]*13 for _ in range(len(S))]

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

for i in range(1, len(S)):
    if S[i] == "?":
        for q_number in range(10): # ?の中身としてあり得る数字
            for front_number in range(13):
                dp[i][(10 * front_number + q_number) % 13] += dp[i-1][front_number]
                dp[i][(10 * front_number + q_number) % 13] %= MOD
    else:
        for front_number in range(13):
            dp[i][(10 * front_number + int(S[i])) % 13] += dp[i-1][front_number]
            dp[i][(10 * front_number + int(S[i])) % 13] %= MOD

print(dp[len(S)-1][5] % MOD)
### BUGGY CODE ###

from heapq import heappop, heappush
from bisect import bisect_right

n, q = map(int, input().split())
stx = [list(map(int, input().split())) for _ in range(n)]
ds = [int(input()) for _ in range(q)]
INF = 10 ** 18
START = 1
END = 0

tfdi = []
for i, (s, t, x) in enumerate(stx):
    t_start = max(0, s - x)
    t_end = max(0, t - x)
    if t_end == 0:
        continue

    tfdi.append([t_start, START, x, i])
    tfdi.append([t_end, END, x, i])

tfdi.append([INF, START, INF, -1])
tfdi.sort()

hp = [[INF, -1]]
ts = []
dists = []
t_prev = -1
passed = set()
for t, f, d, i in tfdi:
    if t != t_prev:
        ts.append(t_prev)
        while hp[0][1] in passed:
            heappop(hp)

        dists.append(hp[0][0])

    if f == START:
        heappush(hp, [d, i])
    else:
        passed.add(i)

    t_prev = t

for d in ds:
    i = bisect_right(ts, d) - 1
    ans = dists[i]
    if ans == INF:
        ans = -1
    print(ans)


### FIXED CODE ###

from bisect import bisect_left

n, q = map(int, input().split())
stx = [list(map(int, input().split())) for _ in range(n)]
d = [int(input()) for _ in range(q)]

INF = 10 ** 9 + 1

stx.sort(key=lambda x: x[2])

nxt = [-1] * q
ans = [-1] * q

for s, t, x in stx:
    l = bisect_left(d, s - x)
    r = bisect_left(d, t - x)

    while l < r:
        if nxt[l] == -1:
            ans[l] = x
            nxt[l] = r
            l += 1
        else:
            l = nxt[l]

print(*ans, sep="\n")
### BUGGY CODE ###

import math
import numpy as np
import queue
from collections import deque,defaultdict
import heapq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n = int(ipt())
    a = [int(i) for i in ipt().split()]
    sa = np.zeros(n)
    for i,ai in enumerate(a):
        sa[i] = sa[i-1]+ai
    ans = np.count_nonzero(sa == 0)
    for i,ai in enumerate(a):
        sa = sa[1::]-ai
        ans += np.count_nonzero(sa == 0)
    print(ans)

    return

if __name__ == '__main__':
    main()


### FIXED CODE ###

import math
import numpy as np
import queue
from collections import deque,defaultdict
import heapq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n = int(ipt())
    a = [int(i) for i in ipt().split()]
    d = defaultdict(int)
    sa = 0
    for i in a:
        sa += i
        d[sa] += 1
    ans = 0
    for iv in d.values():
        ans += iv*(iv-1)//2
    print(ans+d[0])
    return

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

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

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

dp = [[0] * (W+1) for _ in range(N+1)]

for i, (w, v) in enumerate(wvs):
    i += 1
    for j in range(W+1):
        if j < w:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j - w] + v, dp[i-1][j])

print(dp[N][W])


### FIXED CODE ###

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

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

dp = [[0] * (W+1) for _ in range(N+1)]

for i, (w, v) in enumerate(wvs):
    i += 1
    for j in range(W+1):
        if j < w:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j - w] + v, dp[i-1][j])

print(dp[N][W])
### BUGGY CODE ###

import math
a,b=map(int,input().split())
c=[list(map(int,input().split())) for i in range(a-1)]
d=[[]for i in range(a)]
for i in range(a-1):
  ca=c[i][0]
  cb=c[i][1]
  d[ca-1].append(cb-1)
  d[cb-1].append(ca-1)
g=[0 for i in range(a)]
q=[0]
e=b
while not q==[]:
  i=q.pop()
  f=1
  h=len(d[i])
  if g[i]==0:
    if i==0:
      for j in range(h):
        f=f*(b-1-j)
    else:
      if h>0:
        for j in range(h-1):
          f=f*(b-2-j)
  e=(e*f)%1000000007
  g[i]=1
  for j in range(h):
    if g[d[i][j]]==0:
      q.append(d[i][j])


print(e%1000000007)
  

### FIXED CODE ###

from collections import deque
a,b=map(int,input().split())
c=[list(map(int,input().split())) for i in range(a-1)]
d=[[]for i in range(a)]
for i in range(a-1):
  ca=c[i][0]
  cb=c[i][1]
  d[ca-1].append(cb-1)
  d[cb-1].append(ca-1)
g=[0 for i in range(a)]
q=deque()
q.append(0)
e=b
while len(q):
  i=q.pop()
  h=len(d[i])
  g[i]=1
  if i==0:
      f=b-1
  else:
    f=b-2
  g[i]=1
  for j in range(h):
    if g[d[i][j]]==0:
      q.append(d[i][j])
      e=(e*f)%1000000007
      f-=1


print(e%1000000007)
### BUGGY CODE ###

str_s = input()
int_k = int(input())

result = list()
for f in range(len(str_s)):
    pattern = set()
    for t in range(f + 1, len(str_s) + 1):
        pattern.add(str_s[f:t])
        result = sorted(set(result + list(pattern)))[:int_k]

print(result[-1])



### FIXED CODE ###

str_s = input()
int_k = int(input())

result = list()
for f in range(len(str_s)):
    pattern = set()
    for t in range(f + 1, f + 1 + int_k):
        pattern.add(str_s[f:t])
        result = sorted(set(result + list(pattern)))[:int_k]

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

import sys
import math


def input():
    return sys.stdin.readline().rstrip()


def main():
    s = input()
    t = input()
    ls = len(s)
    lt = len(t)

    dp = [[0] * (lt + 1) for _ in range(ls + 1)]
    text = []
    dptx = [[""] * (lt + 1) for _ in range(ls + 1)]
    for i in range(1, ls + 1):
        for j in range(1, lt + 1):
            if s[i - 1] == t[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] +1
                dptx[i][j] = dptx[i - 1][j - 1] + s[i - 1]
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
                if dp[i - 1][j] >= dp[i][j - 1]:
                    dptx[i][j] = dptx[i - 1][j]
                else:
                    dptx[i][j] = dptx[i][j - 1]

    print(dptx[ls][lt])


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
import math


def input():
    return sys.stdin.readline().rstrip()


def main():
    s = input()
    t = input()
    ls = len(s)
    lt = len(t)
    txt=""
    dp = [[0] * (lt + 1) for _ in range(ls + 1)]
    for i in range(1, ls + 1):
        for j in range(1, lt + 1):
            if s[i - 1] == t[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    while lt != 0 and ls != 0:
        if dp[ls][lt] == dp[ls - 1][lt]:
            ls -= 1
        elif dp[ls][lt] == dp[ls][lt - 1]:
            lt -= 1
        else:
            ls -= 1
            lt -= 1
            txt = txt +s[ls]

    print(txt[::-1])


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

import sys
input = sys.stdin.buffer.readline

n,Q = map(int,input().split())
c = list(map(int,input().split()))


#####segfunc######
def segfunc(x,y):
    return x|y

def init(init_val):
    #set_val
    for i in range(n):
        seg[i+num-1]=init_val[i]    
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2]) 
    
def update(k,x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])
    
def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res

#####単位元######
ide_ele = 0

#num:n以上の最小の2のべき乗
num =2**(n-1).bit_length()
seg=[ide_ele]*2*num

def popcnt(n):
    c = (n & 0x5555555555555555) + ((n>>1) & 0x5555555555555555)
    c = (c & 0x3333333333333333) + ((c>>2) & 0x3333333333333333)
    c = (c & 0x0f0f0f0f0f0f0f0f) + ((c>>4) & 0x0f0f0f0f0f0f0f0f)
    c = (c & 0x00ff00ff00ff00ff) + ((c>>8) & 0x00ff00ff00ff00ff)
    c = (c & 0x0000ffff0000ffff) + ((c>>16) & 0x0000ffff0000ffff)
    c = (c & 0x00000000ffffffff) + ((c>>32) & 0x00000000ffffffff)
    return c

for i in range(n):
    update(i,1<<c[i])

for i in range(Q):
    l,r = map(int,input().split())
    l -= 1

    res = query(l,r)

    print(popcnt(res))

### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline

n,Q = map(int,input().split())
c = [0] + list(map(int,input().split()))
dg = 10**6
dg2 = 10**12
res = [0]*Q
LRI = []
for i in range(Q):
    l,r = map(int,input().split())
    LRI.append(l*dg2 + r*dg + i)
LRI.sort()

#A1 ... AnのBIT(1-indexed)
BIT = [0]*(n+1)

#A1 ~ Aiまでの和 O(logN)
def BIT_query(idx):
    res_sum = 0
    while idx > 0:
        res_sum += BIT[idx]
        idx -= idx&(-idx)
    return res_sum

#Ai += x O(logN)
def BIT_update(idx,x):
    while idx <= n:
        BIT[idx] += x
        idx += idx&(-idx)
    return

fi = [[] for i in range(n+1)]
nxt = [-1]*(n+1)
for i in range(1,n+1):
    num = c[i]
    if len(fi[num]) == 0:
        BIT_update(i,1)
    else:
        nxt[fi[num][-1]] = i
    fi[num].append(i)

idx = 0

for i in range(1,n+1):

    while idx < Q:
        l,ri = divmod(LRI[idx],dg2)
        if l != i:
            break
        r,resi = divmod(ri,dg)
        res[resi] = BIT_query(r)
        idx += 1
    BIT_update(i,-1)
    if nxt[i] != -1:
        BIT_update(nxt[i],1)


print(*res,sep='\n')
### BUGGY CODE ###

import math

while True:
	num = int(raw_input())
	tmp = [i+1 for i in range(1, num)]
	x = math.sqrt(num)
	for i in tmp:
		if i > x: break
		for j in range(2,num):
			if i*j > num: break
			if i*j in tmp: tmp.remove(i*j)
	print len(tmp)

### FIXED CODE ###

from bisect import bisect

def sieve(n):
    num = [True]*n
    num[0] = num[1] = False
    for i in xrange(2,int(n**0.5)+1):
        if num[i]:
            for j in xrange(i**2, n, i):
                num[j] = False
    return [i for i in xrange(2,n) if num[i]]

prime =  sieve(999999)

while True:
	try:
		print bisect(prime, input())
	except:
		break
### BUGGY CODE ###

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

# 最小値の定義

ans = 0

for k in range(N):
  min_k = min([P[i] for i in range(k+1)])
  if min_k == P[k]:
    ans += 1

print(ans)

### FIXED CODE ###

N = int(input())
P = list(map(int,input().split()))
 
m = 10**6
ans = 0
for p in P:
    if p < m:
        m = p
        ans += 1
print(ans)
### BUGGY CODE ###

s = input()
t = input()

dp = [[0 for _ in range(len(t)+1)] for _ in range(len(s)+1)]
dp1 = [["" for _ in range(len(t)+1)] for _ in range(len(s)+1)]

for i in range(len(s)):
    for j in range(len(t)):
        if s[i] == t[j]:
            dp[i+1][j+1] = dp[i][j] + 1
            dp1[i + 1][j + 1] = dp1[i][j] + s[i]
        else:
            if dp[i+1][j] >= dp[i][j+1]:
                dp[i+1][j+1] = dp[i+1][j]
                dp1[i + 1][j + 1] = dp1[i + 1][j]
            else:
                dp[i + 1][j + 1] = dp[i][j+1]
                dp1[i + 1][j + 1] = dp1[i][j+1]

print(dp1[-1][-1])

### FIXED CODE ###

s = input()
t = input()

dp = [[0 for _ in range(len(t)+1)] for _ in range(len(s)+1)]

for i in range(len(s)):
    for j in range(len(t)):
        if s[i] == t[j]:
            dp[i+1][j+1] = dp[i][j] + 1
        else:
            dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])

ans = ""
n = dp[-1][-1]
i = len(s)
j = len(t)
while n > 0:
    if dp[i][j] == dp[i-1][j]:
        i -=1
    elif dp[i][j] == dp[i][j-1]:
        j -=1
    elif dp[i][j] == dp[i-1][j-1] + 1:
        ans = s[i-1] + ans
        n -= 1
        i -= 1
        j -= 1

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

import sys
input=sys.stdin.readline
def main():
  n,m,q=map(int,input().split())
  x=[[0]*(n+1) for i in range(n+1)]
  c=[[0]*(n+1) for i in range(n+1)]
  for i in range(m):
    l,r=map(int,input().split())
    x[l][r]+=1
  for i in range(1,n+1):
    for j in range(1,n+1):
      c[i][j]=c[i][j-1]+x[i][j]
  for i in range(q):
    p,q=map(int,input().split())
    s=0
    for j in range(p,q+1):
      s+=c[j][q]-c[j][p-1]
    print(s)
if __name__=='__main__':
  main()

### FIXED CODE ###

n,m,q=map(int,input().split())
x=[[0]*(n+1) for i in range(n+1)]
c=[[0]*(n+1) for i in range(n+1)]
for i in range(m):
  l,r=map(int,input().split())
  x[l][r]+=1
for i in range(1,n+1):
  for j in range(1,n+1):
    c[i][j]=c[i][j-1]+x[i][j]
for i in range(q):
  p,q=map(int,input().split())
  s=0
  for j in range(p,q+1):
    s+=c[j][q]-c[j][p-1]
  print(s)
### BUGGY CODE ###

import fileinput


class Cache():
    def __init__(self, n_1, n_2, n_3):
        self._n_1 = n_1 + n_2 + n_3 + 1
        self._n_2 = n_2 + n_3 + 1
        self._n_3 = n_3 + 1

        self._arr = [-1] * (self._n_1 * self._n_2 * self._n_3)

    def get(self, n_1, n_2, n_3):
        return self._arr[n_1 + n_2 * self._n_1 + n_3 * self._n_1 * self._n_2]

    def add(self, n_1, n_2, n_3, val):
        self._arr[n_1 + n_2 * self._n_1 + n_3 * self._n_1 * self._n_2] = val


def num_turns(total, n_1, n_2, n_3, cache):
    for i_3 in range(n_3 + 1):
        for i_2 in range(n_2 + 1 + n_3 - i_3):
            for i_1 in range(n_1 + 1 + n_2 + n_3 - i_3 - i_2):
                with_sushi = i_1 + i_2 + i_3
                if with_sushi == 0:
                    cache.add(i_1, i_2, i_3, 0)
                    continue
                expectation = total / with_sushi
                if i_1 > 0:
                    p = i_1 / with_sushi
                    expectation += p * cache.get(i_1 - 1, i_2, i_3)

                if i_2 > 0:
                    p = i_2 / with_sushi
                    expectation += p * cache.get(i_1 + 1, i_2 - 1, i_3)

                if i_3 > 0:
                    p = i_3 / with_sushi
                    expectation += p * cache.get(i_1, i_2 + 1, i_3 - 1)
                cache.add(i_1, i_2, i_3, expectation)
    return cache.get(n_1, n_2, n_3)


inp = fileinput.FileInput()
total = int(inp.readline())

n_1 = 0
n_2 = 0
n_3 = 0

for v in inp.readline().split(" "):
    v = int(v)
    if v == 1:
        n_1 += 1
    if v == 2:
        n_2 += 1
    if v == 3:
        n_3 += 1

print(num_turns(total, n_1, n_2, n_3, Cache(n_1, n_2, n_3)))

### FIXED CODE ###

import fileinput


def num_turns(total, n_1, n_2, n_3):
    _n_1 = n_1 + n_2 + n_3 + 1
    _n_2 = n_2 + n_3 + 1
    _n_3 = n_3 + 1

    _arr = [0.0] * (_n_1 * _n_2 * _n_3)

    for i_3 in range(n_3 + 1):
        for i_2 in range(n_2 + 1 + n_3 - i_3):
            for i_1 in range(n_1 + 1 + n_2 + n_3 - i_3 - i_2):
                with_sushi = i_1 + i_2 + i_3
                if with_sushi == 0:
                    continue
                expectation = total / with_sushi
                if i_1 > 0:
                    p = i_1 / with_sushi
                    expectation += p * _arr[(i_1 - 1) + i_2 * _n_1 + i_3 * _n_1 * _n_2]

                if i_2 > 0:
                    p = i_2 / with_sushi
                    expectation += p * _arr[i_1 + 1 + (i_2 - 1) * _n_1 + i_3 * _n_1 * _n_2]

                if i_3 > 0:
                    p = i_3 / with_sushi
                    expectation += p * _arr[i_1 + (i_2 + 1) * _n_1 + (i_3 - 1) * _n_1 * _n_2]
                _arr[i_1 + i_2 * _n_1 + i_3 * _n_1 * _n_2] = expectation

    return _arr[n_1 + n_2 * _n_1 + n_3 * _n_1 * _n_2]


inp = fileinput.FileInput()
total = int(inp.readline())

n_1 = 0
n_2 = 0
n_3 = 0

for v in inp.readline().split(" "):
    v = int(v)
    if v == 1:
        n_1 += 1
    if v == 2:
        n_2 += 1
    if v == 3:
        n_3 += 1

print(num_turns(total, n_1, n_2, n_3))
### BUGGY CODE ###

a, b, x = map(int, input().split())

counter = 0
for i in range(a, b+1):
    if i % x == 0:
        counter += 1

print(counter)

### FIXED CODE ###

import numpy as np
a, b, x = map(int, input().split())
upper = b // x
lower = (a-1)//x

ans = upper - lower

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

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

x = []
y = []

for i, elem in enumerate(a):
    x.append(i+a[i])
    y.append(i-a[i])

ans = 0

for j in range(n):
    for i in range(j):
        if x[i] == y[j]:
            ans += 1;

print(ans)


### FIXED CODE ###

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

x = []
y = {}

for i, elem in enumerate(a):
    x.append(i+a[i])
    y[i-a[i]] = y.get(i-a[i], 0) + 1

ans = 0

for i in x:
    ans += y.get(i, 0)

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

import sys 
sys.setrecursionlimit(2147483647)

N,W = map(int,input().split())
A = [list(map(int, input().split())) for i in range(N)]

def dfs(w,s):
    if (w,s) in dic: return dic[(w,s)]
    ma = 0 
    ls = set(s)
    for idx in range(N):
        if idx not in ls and A[idx][0] <= w:
            ls.add(idx)
            res = dfs(w - A[idx][0],tuple(ls)) + A[idx][1]
            ma = max(res,ma)
            ls.remove(idx)
    dic[(w,s)] = ma
    return ma
dic = {}
seen = set()
res = dfs(W,tuple(seen))
print(res)

### FIXED CODE ###

import sys 
sys.setrecursionlimit(2147483647)

N,W = map(int,input().split())
A = [list(map(int, input().split())) for i in range(N)]
dp = [[0 for _ in range(W+1) ] for _ in range(N + 1)] 

for i in range(1,N + 1): 
    for j in range(W + 1): 
        if j - A[i-1][0] >= 0:
            res1 = dp[i - 1][j - A[i-1][0]] + A[i - 1][1]
            res2 = dp[i - 1][j]
            dp[i][j] = max(res1,res2)
        else:
            dp[i][j] = dp[i-1][j]
#print(dp)
print(max(dp[N]))
### BUGGY CODE ###

n, k = [int(e) for e in input().split()]
divisor = 10 ** 9 + 7
cache = {}
def memoize(f):
    global cache
    def _(*args):
        if not args in cache:
            cache[args] = f(*args)
        return cache[args]
    return _
@memoize
def f(n, x):
  if x == 1:
    return 1
  if x == 2:
    return n + 1
  if x == 3:
    return (n + 1) * (n + 2) // 2
  else:
    return sum(f(i, x - 1) for i in range(n + 1)) % divisor
for i in range(1, k + 1):
  print(f(k - i, i) * f(n - k - i + 1, i + 1) % divisor)


### FIXED CODE ###

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

    c = [[0] * 4000 for _ in range(4000)]
    c[0][0] = 1
    for i in range(1, 4000):
        ci = c[i]
        ci1 = c[i - 1]
        ci[0] = 1
        for j in range(1, i + 1):
            ci[j] = (ci1[j - 1] + ci1[j]) % 1000000007

    def f(n, k):
        return c[n+k-1][k-1]

    for i in range(1, K + 1):
        print((f(K-i, i) * f(N-K-(i-1), i+1)) % 1000000007)


main()
### BUGGY CODE ###

import bisect

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

lisL.sort()
ans = 0
for i in range(N):
    for j in range(i+1,N):
        ab = lisL[i] + lisL[j]
        ans += bisect.bisect_left(lisL[j+1:],ab)

print(ans)

### FIXED CODE ###

import bisect

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

lisL.sort()
ans = 0
for i in range(N):
    for j in range(i+1,N):
        ab = lisL[i] + lisL[j]
        ans += bisect.bisect_left(lisL[j+1:],ab)

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

import numpy as np

def tot(x):
	tot= 0
	for d in x:
		tot+= d
	return tot

n = int(input())
start= np.array(list(map(int, input().split())))
q= int(input())
for _ in range(q):
	b,c= map(int, input().split())
	for index in range(len(start)):
		if start[index]==b:
			start[index]=c
	print(tot(start))

### FIXED CODE ###

n = int(input())
l= list(map(int, input().split()))
table= {}
for num in l:
	if num in table:
		table[num]+=1
	else:
		table[num]=1

tot= 0
for num in l:
	tot+= num

q= int(input())
for _ in range(q):
	b,c= map(int, input().split())
	if b in table:
		if c in table:
			table[c]+= table[b]
			tot+= table[b]*(c-b)
		else:
			table[c]=table[b]
			tot+= table[b]*(c-b)
	table[b]=0
	print(tot)