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

"""
map(int,input().split())

"""
N,K = map(int,input().split())
S = input()
s = []
for i in range(0,len(S)):
    s.append(S[i])


Nums = []
now = 1
cnt = 0
for i in range(0,N):
    if(s[i] == str(now)):
        cnt+=1
    else:
        Nums.append(cnt)
        now = 1-now
        cnt = 1

if cnt!=0:
    Nums.append(cnt)

if len(Nums)%2 == 0:
    Nums.append(0)

Add = 2*K + 1
ans = 0
for i in range(0,len(Nums),2):
    tmp = 0
    left = i
    right = min(i + Add , len(Nums))

    for j in range(left,right):
        tmp += Nums[j]
    ans = max(tmp,ans)

print(ans)


### FIXED CODE ###

"""
map(int,input().split())

"""
N,K = map(int,input().split())
S = input()
s = []
for i in range(0,len(S)):
    s.append(S[i])


Nums = []
now = 1
cnt = 0
for i in range(0,N):
    if(s[i] == str(now)):
        cnt+=1
    else:
        Nums.append(cnt)
        now = 1-now
        cnt = 1

if cnt!=0:
    Nums.append(cnt)

if len(Nums)%2 == 0:
    Nums.append(0)

Add = 2*K + 1
ans = 0
W = []

wsm = 0
for i in range(0,len(Nums)):
    wsm = Nums[i] + wsm
    W.append(wsm)

W.append(wsm)
W.append(wsm)

for i in range(0,len(Nums),2):
    tmp = 0
    left = i
    if left == 0:
        left = 1
    right = min(i + Add , len(Nums))
    if left-1<=0:
        tmp = W[right-1]
    else:
        tmp = W[right-1] - W[left-1]
    #print(tmp,left,right)
    ans = max(tmp,ans)
if  N == 1:
    print(1)
else:
    print(ans)
### BUGGY CODE ###

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

count = 0
for i,a in enumerate(L[:N-2]):
    for j in range(i+1, N-1):
        before = abs(a-L[j])
        after = a+L[j]
        for c in L[j+1:]:
            if before < c < after:
                count += 1

print(count)

### FIXED CODE ###

"""
素直に実装するとN**9
"""

import bisect
 
N = int(input())
L = list(map(int, input().split()))
 
L.sort()
ans = 0
for ai in range(N):
    for bi in range(ai+1, N):
        ci = bisect.bisect_left(L, L[ai]+L[bi])
        if ci > bi:
            ans += ci - bi - 1
        else:
            pass
 
print(ans)
### BUGGY CODE ###

N, K = list(map(int, input().split()))
links = [list(map(int, input().split())) for _ in range(N-1)]

def perm(a, b):
    s = 1
    for i in range(a-b+1, a+1):
        s *= i
    return s

if N == 1:
    print(K)
elif K == 1:
    print(0)
else:
    mod = 1000000007
    d = {}
    for a, b in links:
        if a in d:
            d[a].append(b)
        else:
            d[a] = [b]
        if b in d:
            d[b].append(a)
        else:
            d[b] = [a]
    for j in d[1]:
        d[j].remove(1)
    ans = K * perm(K - 1, len(d[1]))
    root = d[1]
    a = K - 2
    while True:
        children = []
        for i in root:
            for j in d[i]:
                d[j].remove(i)
            b = len(d[i])
            if a < b:
                print(0)
                break
            if b == 0:
                continue
            ans *= perm(a, b)
            children.extend(d[i])
        else:
            if children == []:
                print(ans % mod)
                break
            root = children
            continue
        break


### FIXED CODE ###

N, K = list(map(int, input().split()))
l = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    a, b = list(map(int, input().split()))
    l[a].append(b)
    l[b].append(a)

deg1 = [0] * (N + 1)
deg2 = [0] * (N + 1)
history = [True] * (N + 1)
stack = [1]
ans = 1

while stack:
    node = stack.pop()
    ans *= K - deg1[node] - deg2[node]
    ans %= 1000000007
    history[node] = False
    for child in l[node]:
        if history[child]:
            deg1[child] += 1
            deg2[child] += deg1[node]
            deg1[node] += 1
            stack.append(child)
            
print(ans)
### BUGGY CODE ###

import itertools

K, S = map(int, input().split())

if not ((2 <= K and K <= 2500) or (0 <= S and S <= 3*K)):
    exit()

count = 0
for X, Y, Z in itertools.product(range(0, K+1), range(0, K+1), range(0, K+1)):
    if (X + Y + Z) == S:
        count+=1
print(count)


### FIXED CODE ###

import itertools

K, S = map(int, input().split())

if not ((2 <= K and K <= 2500) or (0 <= S and S <= 3*K)):
    exit()

count = 0
for X in range(0, K + 1):
    for Y in range(0, K + 1):
        if 0 <= (S - X - Y) and (S - X - Y) <= K:
            count += 1

print(count)
### BUGGY CODE ###

# input
N, K, C = map(int, input().split())
S = input()

# process/output
def isZero(l):
    return l.count(0) == len(l)

daysL = [0]*(N+1)
t = 1
for i in range(N):
    if S[i] == 'o' and isZero(daysL[max(0,i-C+1):i+1]):
        daysL[i+1] = t
        t += 1
    else:
        daysL[i+1] = 0
# print(daysL)

if max(daysL) == K:
    daysR = [0]*(N+1)
    t = K
    for i in reversed(range(1,N+1)):
        if S[i-1] == 'o' and isZero(daysR[i:min(N+1,i+C)]):
            daysR[i-1] = t
            t -= 1
        else:
            daysR[i-1] = 0
    
    # print(daysR)
    for i in range(N):
        if S[i] == 'o' and daysL[i+1] != 0 and daysL[i+1] == daysR[i]:
            print(i+1)


### FIXED CODE ###

# input
N, K, C = map(int, input().split())
S = input()

# process
l = [i+1 for i in range(N) if S[i] == 'o']
left = [l[0]]
right = [l[-1]]
for i in range(1, len(l)):
    if l[i] > left[-1]+C:
        left.append(l[i])
    if l[-i-1] < right[-1]-C:
        right.append(l[-i-1])

# output
# print(l)
# print(left)
# print(right)
if len(left) == K:
    for i in range(len(left)):
        if left[i] == right[-i-1]:
            print(left[i])
### BUGGY CODE ###

import copy

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

ans = 0
C = set(A)

for k in range(N):
    B = copy.copy(A)
    #k = k + 1
    del B[k]
    for x in C:
        cnt = B.count(x)
        ans += cnt * (cnt-1) // 2
        cnt = 0
    print(ans)
    ans = 0

### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(map(int,input().split()))

n = 0
B = set(A)

C = Counter(A)

for i in C.keys():
    n += C[i] * (C[i]-1) // 2

for i in range(N):
    a = A[i]
    print(n - C[a] + 1)
### BUGGY CODE ###

x,k,d=map(int,input().split())
x=abs(x)
sa=x//d
ans=x
pbk,mbk=0,0
bk1,bk2,bk3=1,1,1
mansbk,pansbk=0,0
if sa>=k:
  ans=x-d*k
else:
  ans=x-d*sa
  k=k-sa
  for i in range(k):
    mansbk=abs(ans-d)
    pansbk=abs(ans+d)
    if mansbk!=pansbk:
      ans=min(mansbk,pansbk)
      if bk3!=1:
        bk1=min(mansbk,pansbk)
        bk2=max(mansbk,pansbk)
        ans=1 if (k-i)%2==1 else bk1
        break
      elif ans==1:
        bk3=max(mansbk,pansbk) 
    else:
      ans=0 if (k-i)%2==0 else d
      break
    pbk=max(mansbk,pansbk)
    mbk=min(mansbk,pansbk)
print(ans)

### FIXED CODE ###

x,k,d=map(int,input().split())
x=abs(x)
sa=x//d
ans=x
pbk,mbk=0,0
bk1,bk2,bk3=1,1,1
mansbk,pansbk=0,0
if sa>=k:
  ans=x-d*k
else:
  ans=x-d*sa
  k=k-sa
  for i in range(k):
    mansbk=abs(ans-d)
    pansbk=abs(ans+d)
    if mansbk!=pansbk:
      ans=min(mansbk,pansbk)
      if bk3!=1:
        bk1=min(mansbk,pansbk)
        bk2=max(mansbk,pansbk)
        ans=mbk if (k-i)%2==0 else bk1
        break
      else:
        bk3=max(mansbk,pansbk) 
    else:
      ans=0 if (k-i)%2==0 else d
      break
    pbk=max(mansbk,pansbk)
    mbk=min(mansbk,pansbk)
print(ans)
### BUGGY CODE ###

"""
# 標準入力取得
## 文字列
 = sys.stdin.readline().rstrip()
 = list(sys.stdin.readline().rstrip())

## 数値
 = int(sys.stdin.readline())
 = map(int, sys.stdin.readline().split())
 = list(map(int, sys.stdin.readline().split()))
 = [list(map(int,list(sys.stdin.readline().split()))) for i in range(h)]  # 二次元配列入力　二次元マップみたいな入力のとき

# 0埋め, 小数点出力桁指定時のときの出力
a = 100
b = 0.987654321
print("{0:06d}-{1:6f}".format(a,b))
000100-0.987654

# 文字列をリストに格納
char_list = list("abcd") # ["a","b","c","d"]
"""

import math
import sys
import itertools
import queue
from fractions import gcd

def lcm(a, b):
    return a * b // gcd(a, b)

mod = 1000000007

if __name__ == "__main__":
    N= int(sys.stdin.readline())
    A = list(map(int,sys.stdin.readlines()))
    def d(A,i):
        k=A.pop(i)
        print(max(A))
        A.insert(i,k)
    for i in range(len(A)):
        d(A,i)

### FIXED CODE ###

"""
# 標準入力取得
## 文字列
 = sys.stdin.readline().rstrip()
 = list(sys.stdin.readline().rstrip())

## 数値
 = int(sys.stdin.readline())
 = map(int, sys.stdin.readline().split())
 = list(map(int, sys.stdin.readline().split()))
 = [list(map(int,list(sys.stdin.readline().split()))) for i in range(h)]  # 二次元配列入力　二次元マップみたいな入力のとき

# 0埋め, 小数点出力桁指定時のときの出力
a = 100
b = 0.987654321
print("{0:06d}-{1:6f}".format(a,b))
000100-0.987654

# 文字列をリストに格納
char_list = list("abcd") # ["a","b","c","d"]
"""

import math
import sys
import itertools
import queue
from fractions import gcd
import time


def lcm(a, b):
    return a * b // gcd(a, b)

mod = 1000000007

if __name__ == "__main__":
    N= int(sys.stdin.readline())
    A = list(map(int,sys.stdin.readlines()))
    l = sorted(A)
    m1 = l[-1]
    m2 = l[-2]
    for i in range(N):
        if A[i] == m1:
            print(m2)
        else:
            print(m1)
### BUGGY CODE ###

n=int(input())
path_color=[None]*(n-1)
tree_path=[[] for x in range(n)]
path_num_to_edges=[]
tree_edge_flag=set()
for i in range(n-1):
    ai,bi=[int(x) -1 for x in input().split()]
    tree_path[ai].append((bi,i))
    tree_path[bi].append((ai,i))
    path_num_to_edges.append((ai,bi))

path_color[0]=1
from collections import deque
d=deque()
d.append(0)
while d:
    temp=d.pop()
    temp_color=path_color[temp]
    edges=path_num_to_edges[temp]
    for edge in edges:
        new_path_color=1
        tree_edge_flag.add(edge)
        for other_edge,path_num in tree_path[edge]:
            if path_color[path_num]!=None:
                continue
            if other_edge in tree_edge_flag:
                continue
            tree_edge_flag.add(other_edge)
            if new_path_color==temp_color:
                new_path_color+=1
            path_color[path_num]=new_path_color
            new_path_color+=1
            d.append(path_num)


print(max(path_color))
for i in path_color:
    print(i)

### FIXED CODE ###

n=int(input())
path_color=[None]*(n-1)
tree_path=[[] for x in range(n)]
path_num_to_edges=[]
tree_edge_flag=set()
for i in range(n-1):
    ai,bi=[int(x) -1 for x in input().split()]
    tree_path[ai].append((bi,i))
    tree_path[bi].append((ai,i))
    path_num_to_edges.append((ai,bi))

path_color[0]=1
from collections import deque
d=deque()
for i in path_num_to_edges[0]:
    d.append(i)
while d:
    temp_edge=d.pop()
    if temp_edge in tree_edge_flag:
        continue
    tree_edge_flag.add(temp_edge)
    new_path_color=1
    for other_edge,path_num in tree_path[temp_edge]:
        if path_color[path_num]!=None:
            old_color=path_color[path_num]
            break
    for other_edge,path_num in tree_path[temp_edge]:
        if path_color[path_num]!=None:
            continue
        if new_path_color==old_color:
            new_path_color+=1
        path_color[path_num]=new_path_color
        new_path_color+=1
        d.append(other_edge)

print(max(path_color))
for i in path_color:
    print(i)
### BUGGY CODE ###

import sys
stdin = sys.stdin

sys.setrecursionlimit(10**5)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n = ni()
s = [" "] + lc()
q = ni()
k = list(li())



def find_ans(k:int):
    d__ = 0
    dm_ = 0
    _m_ = 0
    ans = 0
    
    for i in range(1, n+1):
        
        if s[i] == 'C':
            ans += dm_

        if i-k+1 > 0:
            if s[i-k+1] == 'D':
                d__ -= 1
                dm_ -= _m_
                
            elif s[i-k+1] == 'M':
                _m_ -= 1
                
        if s[i] == 'D':
            d__ += 1    
        
        elif s[i] == 'M':
            dm_ += d__
            _m_ += 1

            
    return ans
        
for ki in k:
    print(find_ans(ki))

### FIXED CODE ###

import sys
stdin = sys.stdin

sys.setrecursionlimit(10**5)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n = ni()
s = " " + ns()
q = ni()
k = list(li())

def find_ans(k:int):
    cnt = [0,0,0]
    ans = 0
    
    for i in range(1, n+1):
        
        if s[i] == 'C':
            ans += cnt[2]

        if i-k+1 > 0:
            if s[i-k+1] == 'D':
                cnt[0] -= 1
                cnt[2] -= cnt[1]
                
            elif s[i-k+1] == 'M':
                cnt[1] -= 1
                
        if s[i] == 'D':
            cnt[0] += 1    
        
        elif s[i] == 'M':
            cnt[2] += cnt[0]
            cnt[1] += 1

            
    return ans
        
for ki in k:
    print(find_ans(ki))
### BUGGY CODE ###

from collections import Counter

n = list(input())
n.reverse()
x = [0]*(len(n))
a=0
for i in range(len(n)):
    a+=int(n[i])*10**i
    x[i]=a%2019
c=Counter(x)
cc=c.most_common()
ans = c[0]
for i in range(len(cc)):
    b=cc[i][1]
    ans += b*(b-1)//2

print(ans)


### FIXED CODE ###

from collections import Counter

n = list(input())
n.reverse()
x = [0]*(len(n))
a=0
ex=1
for i in range(len(n)):
    a+=int(n[i])*ex
    x[i]=a%2019
    ex=ex*10%2019
c=Counter(x)
ans = c[0]
for i in c.keys():
    b=c[i]
    ans += b*(b-1)//2

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

s = input()
K = int(input())
substring = []
for i in range(len(s)):
    for j in range(i,len(s)):
        substring.append(s[i:j+1])
ans = sorted(list((set(substring))))
print(ans[K-1])

### FIXED CODE ###

s = input()
K = int(input())
substring = []
for i in range(len(s)):
    for j in range(i, i+5):
        substring.append(s[i: j + 1])
substring = list(set(substring))
substring.sort()                
print(substring[K-1])
### BUGGY CODE ###

k, s = [int(i) for i in input().split()]

print([a + b + c == s for a in range(k + 1) for b in range(k + 1) for c in range(k + 1)].count(True))

### FIXED CODE ###

k, s = [int(i) for i in input().split()]
print([0 <= s-i-j <= k for i in range(k+1) for j in range(k+1)].count(True))
### BUGGY CODE ###

import sys
import collections
from operator import mul
from functools import reduce
 
def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom
 
n = int(input())
l = [int(x) for x in input().split()]
c = collections.Counter(l)
 
# cl = [0 for i in range(n)]
cl = []
ll = [x for x in set(l) if l.count(x) > 1]
 
# print(ll)
 
if not ll:
    for i in range(n):
        print(0)
    sys.exit()
 
sum = 0
for i in ll:
    nc = combinations_count(c[i], 2)
    sum += nc
    # print(nc)
    # cl[i-1] = nc - int(nc*(m-2)/m)
    cl.append(nc - int(nc * (c[i] - 2) / c[i]))
 
# print(sum)
# print(cl)
 
def my_index(l, x, default=n):
    if x in l:
        return l.index(x)
    else:
        return default
 
for i in l:
    # print(sum - cl[i-1])
    idx = my_index(ll, i)
    if idx == n:
        print(sum)
    else:
        print(sum - cl[idx])

### FIXED CODE ###

import collections

def combinations_count(n, r):
    return n * (n-1) // r


n = int(input())
l = [int(x) for x in input().split()]

l1 = []
l2 = []
c = collections.Counter(l)

total = sum([combinations_count(i, 2) for i in c.values()])

for a in l:
    print(total-combinations_count(c[a], 2)+combinations_count(c[a]-1, 2))
### BUGGY CODE ###

from collections import deque

S = input()
Q = int(input())

for i in range(Q):
  A = input().split()
  if A[0] == "1":
    S = S[::-1]
  else:
    if A[1] == "1":
      a = deque(S)
      a.appendleft(A[2])
      S = list(a)
    else:
      a = deque(S)
      a.append(A[2])
      S = list(a)
print("".join(S))

### FIXED CODE ###

from collections import deque

S = input()
Q = int(input())
a = deque(S)

flag = 0

for i in range(Q):
  A = input().split()
  if A[0] == "1":
    if flag == 0:
      flag = 1
    else:
      flag = 0
  else:
    if A[1] == "1" and flag == 0 or A[1] == "2" and flag == 1:      
      a.appendleft(A[2])
    else:
      a.append(A[2])

if flag == 1:
  a.reverse()
print("".join(a))
### BUGGY CODE ###

def culc(s,c,l,b,x,y):
    if s == l-1:
        return s
    if x+y >b[c]:
        s = c
        c = int((c+l)/2)
        return culc(s,c,l,b,x,y)
    else:
        l = c
        c = int((c+s)/2)
        return culc(s,c,l,b,x,y)
    
    
N = int(input())
b = list(int(i) for i in input().split())
b.sort()
sum_N = 0
for i,x in enumerate(b):
    s = i+1
    for y in range(i+1,N,1):
        c = int((i+N)/2)
        lim_num =culc(s,c,N,b,x,b[y])
        sum_N += lim_num-y
        s=lim_num
print(sum_N)

### FIXED CODE ###

import bisect    
    
N = int(input())
b = list(int(i) for i in input().split())
b.sort()
sum_N = 0
for i,x in enumerate(b):
    s = i+1
    for y in range(i+1,N,1):
        index = bisect.bisect_left(b,x+b[y])
        sum_N += max(0,index - y -1)
print(sum_N)
### BUGGY CODE ###

from math import gcd

N = 1000001
 
spf = [*range(N)]
i = 2
while i * i < N:
  if spf[i] == i:
    for j in range(i * i, N, i):
      if spf[j] == j:
        spf[j] = i
  i += 1
  
r = 'pairwise'

input()
d = None
p = 1
for x in map(int, input().split()):
  d = gcd(d or x, x)
  e = gcd(p, x)
  if e > 1:
    r = 'setwise'
  p = p // e * x
print('not' if d > 1 else r, 'coprime')


### FIXED CODE ###

N = 1000001
 
spf = [*range(N)]
i = 2
while i * i < N:
  if spf[i] == i:
    for j in range(i * i, N, i):
      if spf[j] == j:
        spf[j] = i
  i += 1
  
r = 'pairwise'
n = int(input())
a = [int(x) for x in input().split() if x > '1']
if len(a) > 1:
  u = set()
  i = None
  for x in a:
    s = set()
    while x > 1:
      p = spf[x]
      if p in u:
        r = 'setwise'
      s.add(p)
      x //= p
    u |= s
    if len(a) == n:
      if i is None: i = s
      else: i &= s
  if i:
    r = 'not'
print(r, 'coprime')
### BUGGY CODE ###

import math
MOD = 10**9+7
x, y = map(int, input().split())
if (x+y)%3 != 0 or 3*x < x+y or 3*y < x+y:
    print(0)
    exit()
n = (x+y)//3
x -= n
y -= n
factX = factY = factN = 1
for i in range(1,n+1):
    factN *= i
    if i == x: factX = factN
    if i == y: factY = factN
c = factN // factX // factY
print(c%MOD)


### FIXED CODE ###

def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0

def modinv(a, m):
    g, x, y = xgcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

MOD = 10**9+7
x, y = map(int, input().split())
if (x+y)%3 != 0 or 3*x < x+y or 3*y < x+y:
    print(0)
    exit()
n = (x+y)//3
x -= n
y -= n
fact = [1, 1]
for i in range(2,n+1):
    fact.append(fact[i-1] * i % MOD)
factX = fact[x]
factY = fact[y]
factN = fact[n]
# print(x,y,n)
# print(factX,factY,factN)

c = factN * modinv(factX, MOD) * modinv(factY, MOD)
c %= MOD
print(c)
### BUGGY CODE ###

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

cnt=0
for i in range(N):
    min=p[0]
    for j in range(i):
        if min>=p[j]:
            min=p[j]
    
    if p[i]<=min:
        cnt+=1

print(cnt)

### FIXED CODE ###

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

N = int(input())
S = input()
min = S[1:N].count("E")

for i in range (1,N):
    if S[i] == "W":
        continue
    count = S[0:i].count("W") + S[i+1:N].count("E")
    if min > count:
        min = count
print(min)


### FIXED CODE ###

N = int(input())
S = input()
min = S[1:N].count("E")
now = S[1:N].count("E")

for i in range (1,N):
    if S[i-1] == "E" and S[i] == "E":
        now -= 1
    if S[i-1] == "W" and S[i] == "W":
        now += 1
    if now < min:
        min = now
print(min)
### BUGGY CODE ###

import sys
import bisect
from operator import itemgetter

input = sys.stdin.readline


def main():
    N, D, A = [int(x) for x in input().split()]
    XH = []
    X = []
    for _ in range(N):
        x, h = [int(x) for x in input().split()]
        XH.append([x, h, float("inf")])
        XH.append([x + 2 * D + 1, float("inf"), 0])
        X.append(x)
        X.append(x + 2 * D + 1)

    X.sort()
    XH.sort(key=itemgetter(0, 2))

    ans = 0
    ruiseki = 0

    for x, h, r in XH:
        if h != float("inf"):
            if h > ruiseki:
                tmpruiseki = -(-(h - ruiseki) // A) * A
                ans += -(-(h - ruiseki) // A)
                ruiseki += tmpruiseki
                nx = bisect.bisect_left(X, x + 2 * D + 1)
                if XH[nx][1] == float("inf"):
                    XH[nx][2] -= tmpruiseki
                else:
                    XH[nx + 1][2] -= tmpruiseki
            else:
                continue
        else:
            ruiseki += r

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import bisect
from operator import itemgetter

input = sys.stdin.readline


def main():
    N, D, A = [int(x) for x in input().split()]
    XH = []
    X = []
    R = [0] * (N * 2)
    for _ in range(N):
        x, h = [int(x) for x in input().split()]
        XH.append((x, h))
        XH.append((x + 2 * D + 1, -float("inf")))
        X.append(x)
        X.append(x + 2 * D + 1)

    X.sort()
    XH.sort(key=itemgetter(0, 1))

    ans = 0
    ruiseki = 0

    for i in range(N * 2):
        x, h = XH[i]
        if h != -float("inf"):
            if h > ruiseki:
                tmpruiseki = -(-(h - ruiseki) // A) * A
                ans += -(-(h - ruiseki) // A)
                ruiseki += tmpruiseki
                nx = bisect.bisect_left(X, x + 2 * D + 1)
                if XH[nx][1] == -float("inf"):
                    R[nx] -= tmpruiseki
                else:
                    R[nx + 1] -= tmpruiseki
            else:
                continue
        else:
            ruiseki += R[i]

    print(ans)


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

n = int(input())
a = list(map(int, input().split()))
law = 10 ** 9 + 7

bitsum = [0 for _ in range(60)]
for x in a:
    for i in range(60):
        bitsum[i] += bool(x & (1 << i))

ans = 0
for x in a:
    for i in range(60):
        k = bitsum[i]
        if (x & (1 << i)):
            k = n - k
        ans += k << i
        ans %= law
if ans % 2 == 0:
    print(ans // 2)
else:
    print((ans + law) // 2)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
law = 10 ** 9 + 7

bitsum = [0 for _ in range(60)]
for x in a:
    for i in range(60):
        bitsum[i] += bool(x & (1 << i))

ans = 0
for x in a:
    for i in range(60):
        k = bitsum[i]
        if (x & (1 << i)):
            k = n - k
        ans += k << i
    ans %= law
if ans % 2 == 0:
    print(ans // 2)
else:
    print((ans + law) // 2)
### BUGGY CODE ###

n,q=map(int,input().split())
s=input()
for i in range(q):
	a,b=map(int,input().split())
	cnt=0
	for i in range(a-1,b-1):
		if s[i]+s[i+1]=="AC":
			cnt+=1
	print(cnt)

### FIXED CODE ###

n,q=map(int,input().split())
s=input()
i=0
d=""
while i<n-1:
	if s[i]=="A" and s[i+1]=="C":
		d+="0"*2
		i+=2
	else:
		d+=s[i]
		i+=1
d+=s[-1]
num=[0]*n
cnt=0
for i in range(n):
	if d[i]=="0":
		cnt+=1
	num[i]=cnt//2
for i in range(q):
	x,y=map(int,input().split())
	print(num[y-1]-num[x-1])