Harryxun/stf_run huggingface dataset:
s = input()[::-1]
t = input()[::-1]
for i,c in enumerate(s):
  if c == t[0] and (i+len(t) < len(s)):
    for j in range(len(t)):
      if t[j] != s[i+j] and s[i+j] != '?':
        break
    else:
      for j in range(len(t)):
        s[i+j] =  t[j]
      print(s.replace('?', 'a')[;;-1])
      break
else:
  print('UNRESTORABLE')



### FIXED CODE ###

s = input()[::-1]
t = input()[::-1]
for i,c in enumerate(s):
  if (c == t[0] or c == '?') and (i+len(t) < len(s)+1):
    for j in range(len(t)):
      if t[j] != s[i+j] and s[i+j] != '?':
        break
    else:
      str_list = list(s)
      for j in range(len(t)):
        str_list[i+j] =  t[j]
      s = ''.join(str_list)
      print(s.replace('?', 'a')[::-1])
      break
else:
  print('UNRESTORABLE')
def main():	
  	#!/usr/bin/env python3
	#B
	import numpy as np
    import math
    import re
     
    a,b,c,n = list(map(int,re.split(" ",input())))
    N = n
    s = []
    s.append(a)
    s.append(b)
    s.append(c)
    s.sort()
    a,b,c = s
    #print(a,b,c)
    ans = 0
    for i in range(int(N/c)+1):
        for j in range(int((N-i*c)/b)+1):
                if (N - i*c  - j*b)%a == 0:
                    ans += 1
                
    print(ans)
main()

### FIXED CODE ###

#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

#solve
def solve():
    R, G, B, n = LI()
    ans = 0
    for r in range(n // R + 1):
        for g in range((n - r * R) // G + 1):
            b = (n - r * R - g * G) // B
            if r * R + g * G + b * B == n:
                
                ans += 1
    print(ans)
    return


#main
if __name__ == '__main__':
    solve()
from functools import reduce

INF = float("inf")

N, a, b, *A = map(int, open(0).read().split())
c = reduce(lambda a, b: a ^ b, A, 0)

def solve(a, b, c):
    if (a % 2) ^ (b % 2) != (c % 2):
        return INF
    if c == 0:
        return INF if a < b else (a - b) // 2

    return min(
        2 * solve(a // 2, b // 2, c // 2),
        1 + 2 * solve((a - 1) // 2, (b + 1) // 2, c // 2)
    )

print(-1 if (res := solve(a, b, c)) >= a else res)

### FIXED CODE ###

from functools import reduce, lru_cache

INF = float("inf")

N, a, b, *A = map(int, open(0).read().split())
c = reduce(lambda a, b: a ^ b, A, 0)

@lru_cache(None)
def solve(a, b, c):
    if (a % 2) ^ (b % 2) != (c % 2):
        return INF
    if c == 0:
        return INF if a < b else (a - b) // 2

    return min(
        2 * solve(a // 2, b // 2, c // 2),
        1 + 2 * solve((a - 1) // 2, (b + 1) // 2, c // 2)
    )

print(-1 if (res := solve(a, b, c)) >= a else res)
N=int(input())
T,A=map(int,input().split())
H_list=list(map(int,input().split()))
a=list(map(lambda x:abs(A-(T-x*0.006)), H_list))
#print(a)
print(min(a))

### FIXED CODE ###

x,y=map(int,input().split())
print(x+(y//2))
import sys
from collections import defaultdict
sys.setrecursionlimit(100000)
N, Q = map(int,input().split())
edges = [[] for _ in range(N)]
for _ in range(N-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    edges[a].append(b)
    edges[b].append(a)

d = defaultdict(int)
for _ in range(Q):
    p,x = map(int,input().split())
    d[p-1] += x
visited = [False]*N
cnt = [0]*N
def dfs(n, acc):
    cnt[n] = acc
    for m in edges[n]:
        if not visited[m]:
            visited[m] = True
            dfs(m, acc+d[m])
visited[0] = True
dfs(0, d[0])
print(*cnt)

### FIXED CODE ###

import sys
from collections import defaultdict
sys.setrecursionlimit(1000000)
N, Q = map(int,input().split())
edges = [[] for _ in range(N)]
for _ in range(N-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    edges[a].append(b)
    edges[b].append(a)

d = defaultdict(int)
for _ in range(Q):
    p,x = map(int,input().split())
    d[p-1] += x
visited = [False]*N
cnt = [0]*N
def dfs(n, acc):
    cnt[n] = acc
    for m in edges[n]:
        if not visited[m]:
            visited[m] = True
            dfs(m, acc+d[m])
visited[0] = True
dfs(0, d[0])
print(*cnt)
from collections import deque

def bfs():
    d = [[float("inf")] * w for _ in range(h)]

    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

    que = deque([])
    que.append((sx,sy))
    d[sx][sy] = 0

    while que:
        p = que.popleft()
        if p[0] == gx and p[1] == gy:
            break

        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]

            if 0 <= nx < w and 0 <= ny < h and maze[nx][ny] != "#" and d[nx][ny] == float("inf"):
                que.append((nx,ny))
                d[nx][ny] = d[p[0]][p[1]] + 1
    
    return d[gy][gx]

h, w = map(int, input().split())
maze = [list(input()) for _ in range(h)]
sx, sy = 0, 0
gx, gy = h-1, w-1

white = 0
for i in range(h):
    for j in range(w):
        if maze[i][j] == ".":
            white += 1

res = bfs()

if 0 < res < float("inf"):
    print(white-res-1)
else:
    print(-1)

### FIXED CODE ###

from collections import deque

def bfs():
    d = [[float("inf")] * w for i in range(h)]

    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

    que = deque([])
    que.append((sx, sy))
    d[sx][sy] = 0

    while que:
        p = que.popleft()
        if p[0] == gx and p[1] == gy:
            break

        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]

            if 0 <= nx < h and 0 <= ny < w and maze[nx][ny] != "#" and d[nx][ny] == float("inf"):
                que.append((nx, ny))
                d[nx][ny] = d[p[0]][p[1]] + 1
    
    return d[gx][gy]

h, w = map(int, input().split())
maze = [list(input()) for _ in range(h)]
sx, sy = 0, 0
gx, gy = h-1, w-1

white = 0
for i in range(h):
    for j in range(w):
        if maze[i][j] == ".":
            white += 1

res = bfs()

if 0 < res < float("inf"):
    print(white-res-1)
else:
    print(-1)
abc161b
n,m=map(int,raw_input().split())
a=map(int,raw_input().split())
x=sum(a)/(4*m)
l=[i for i in a if i>x]
if len(l)>=m:
 print 'Yes'
else:
 print 'No'


### FIXED CODE ###

#abc161a
x,y,z=map(int,raw_input().split())
x,y=y,x
x,z=z,x
print x,y,z
import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
RB = B[::-1]

start = v = -1
seq = 0
for i,(a,b) in enumerate(zip(A,RB)):
    if a==b:
        v = a
        seq += 1
        if start == -1:
            start = i

if v == -1:
    print('Yes')
    print(*RB)
    exit()

if A.count(v) + B.count(v) > N:
    print('No')
    exit()

from bisect import bisect_left,bisect
al = bisect_left(A,v)
bl = bisect_left(B,v)
br = bisect(B,v)
rbl = N - br

m = min(seq,start,al,bl)
RB[:m],RB[start:start+m] = RB[start:start+m],RB[:m]
seq -= m
start += m
if seq:
    RB[start:start+seq],RB[-seq:] = RB[-seq:],RB[start:start+seq]

assert all(a!=b for a,b in zip(A,RB))
print('Yes')
print(*RB)

### FIXED CODE ###

import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
RB = B[::-1]

start = v = -1
seq = 0
for i,(a,b) in enumerate(zip(A,RB)):
    if a==b:
        v = a
        seq += 1
        if start == -1:
            start = i

if v == -1:
    print('Yes')
    print(*RB)
    exit()

if A.count(v) + B.count(v) > N:
    print('No')
    exit()

from bisect import bisect_left,bisect
al = bisect_left(A,v)
bl = bisect_left(B,v)
br = bisect(B,v)
rbl = N - br

m = min(seq,start,al,rbl)
RB[:m],RB[start:start+m] = RB[start:start+m],RB[:m]
seq -= m
start += m
if seq:
    RB[start:start+seq],RB[-seq:] = RB[-seq:],RB[start:start+seq]

assert all(a!=b for a,b in zip(A,RB))
print('Yes')
print(*RB)
#
# abc064 c
#
import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """4
2100 2500 2700 2700"""
        output = """2 2"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """5
1100 1900 2800 3200 3200"""
        output = """3 5"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """20
800 810 820 830 840 850 860 870 880 890 900 910 920 930 940 950 960 970 980 990"""
        output = """1 1"""
        self.assertIO(input, output)


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

    C = [0] * 9
    for a in A:
        for i in range(8):
            if 400*i <= a <= 400*i+399:
                C[i] = 1
                break
        else:
            C[8] += 1

    print(f"{max(1, C[:8].count(1))} {C[:8].count(1)+C[8])}")


if __name__ == "__main__":
    # unittest.main()
    resolve()


### FIXED CODE ###

#
# abc064 c
#
import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """4
2100 2500 2700 2700"""
        output = """2 2"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """5
1100 1900 2800 3200 3200"""
        output = """3 5"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """20
800 810 820 830 840 850 860 870 880 890 900 910 920 930 940 950 960 970 980 990"""
        output = """1 1"""
        self.assertIO(input, output)


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

    C = [0] * 9
    for a in A:
        for i in range(8):
            if 400*i <= a <= 400*i+399:
                C[i] = 1
                break
        else:
            C[8] += 1

    print(f"{max(1, C[:8].count(1))} {C[:8].count(1)+C[8]}")


if __name__ == "__main__":
    # unittest.main()
    resolve()
s=input()
s=s.trim()
if s=="rrs" || s=="srr":
    print("2")
else if s=="rrr":
    print("3")
else if s=="sss":
    print('0')
else:
    print('1')


### FIXED CODE ###

s = str(input())
s=s.lower()

if s=="rrr":
    print('3')
elif s.find('rr') != -1:
    print("2")
elif s.find('r') != -1:
    print("1")
else:
    print ("0")
n = int(input())
if n == 1:
    print('Yes')
    prnt(2)
    print("1")
    print("1")
    exit()
t = [3]
cnt = 3
while t[-1]+cnt <= n:
    t.append(t[-1]+cnt)
    cnt += 1
if t[-1] != n:
    print('No')
    exit()
print('Yes')
try:
    n_cols = t[-1]-t[-2]
except:
    print(3)
    print("2 1 2")
    print("2 3 1")
    print("2 2 3")
    exit()
print(n_cols+1)
t_len = len(t)
t2 = [i+1 for i in t]
t3 = [0 for i in t]
for col in range(n_cols+1):
    out = str(n_cols)
    if col <=2:
        if col == 0:
            out += " 1 2"
        elif col == 1:
            out += " 1 3"
        elif col == 2:
            out += " 2 3"
    else:
        idx = t[col-3]+1
        while idx <= t[col-2]:
            out += " " + str(idx)
            idx += 1
    for i in range(t_len-1):
        if t2[i] != t[i+1]+1:
            out += " " + str(t2[i])
            t2[i] += 1
    print(out)

### FIXED CODE ###

n = int(input())
if n == 1:
    print('Yes')
    print(2)
    print("1 1")
    print("1 1")
    exit()
t = [3]
cnt = 3
while t[-1]+cnt <= n:
    t.append(t[-1]+cnt)
    cnt += 1
if t[-1] != n:
    print('No')
    exit()
print('Yes')
try:
    n_cols = t[-1]-t[-2]
except:
    print(3)
    print("2 1 2")
    print("2 3 1")
    print("2 2 3")
    exit()
print(n_cols+1)
t_len = len(t)
t2 = [i+1 for i in t]
t3 = [0 for i in t]
for col in range(n_cols+1):
    out = str(n_cols)
    if col <=2:
        if col == 0:
            out += " 1 2"
        elif col == 1:
            out += " 1 3"
        elif col == 2:
            out += " 2 3"
    else:
        idx = t[col-3]+1
        while idx <= t[col-2]:
            out += " " + str(idx)
            idx += 1
    for i in range(t_len-1):
        if t2[i] != t[i+1]+1:
            out += " " + str(t2[i])
            t2[i] += 1
    print(out)
# 入力
N=int(input())
tl=list(map(int,input().split()))
M=int(input())

# 和
sm=sum(tl)

for i in range(N):
  P,X=map(int,input().split())

  # 変更した場合の変化量を求める
  a=X-tl[P-1]

  # 出力
  print(sm+a)

### FIXED CODE ###

n=int(input())
t=list(map(int,input().split()))
m=int(input())
s=sum(t)
l=[]
for i in range(m):
  p,x=map(int,input().split())

  l.append(s-t[p-1]+x)
for i in l:
  print(i)
import math
import collections
import copy
import sys

n = int(input())

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

sCheck = math.gcd(a[0],a[1])
if n == 2:
    if sCheck == 1:
        print("pairwise coprime")
    else:
        print("not coprime")
    sys.exit()
else:
    for i in range(2,n):
        sCheck = math.gcd(sCheck,a[i])


beforeQ = collections.deque([int(i) for i in range(3,(10**6 + 1))])
D = dict()
p = 2
D[2] = 2
D[1] = 1

while p < math.sqrt(10**6):
    afterQ = collections.deque()
    while len(beforeQ) > 0:        
        k = beforeQ.popleft()
        if k % p != 0:
            afterQ.append(k)
        else:
            D[k] = p
    beforeQ = copy.copy(afterQ)
    p = beforeQ.popleft()
    D[p] = p
    
ansSet = set()
count = 0

for i in a:
    k = i
    kSet = set()
    while k != 1:
        if D[k] in ansSet:
            if not(D[k] in kSet):
                count = 1
                break
        else:
            ansSet.add(D[k])
            kSet.add(D[k])
        k = int(k // D[k])
    if count == 1:
        break

if count == 0:
    print("pairwise coprime")
elif sCheck == 1:
    print("setwise coprime")
else:
    print("not coprime")


### FIXED CODE ###

import math
import collections
import copy
import sys

n = int(input())

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

limit = 10 ** 6

sCheck = math.gcd(a[0],a[1])
if n == 2:
    if sCheck == 1:
        print("pairwise coprime")
    else:
        print("not coprime")
    sys.exit()
else:
    for i in range(2,n):
        sCheck = math.gcd(sCheck,a[i])


beforeQ = collections.deque([int(i) for i in range(3,(limit + 1))])
D = dict()
p = 2
D[2] = 2
D[1] = 1

while p < math.sqrt(limit):
    afterQ = collections.deque()
    while len(beforeQ) > 0:        
        k = beforeQ.popleft()
        if k % p != 0:
            afterQ.append(k)
        else:
            D[k] = p
    beforeQ = copy.copy(afterQ)
    p = beforeQ.popleft()
    D[p] = p
while len(beforeQ) > 0:
    k = beforeQ.popleft()
    D[k] = k
    
ansSet = set()
count = 0

for i in a:
    k = i
    kSet = set()
    while k != 1:
        if D[k] in ansSet:
            if not(D[k] in kSet):
                count = 1
                break
        else:
            ansSet.add(D[k])
            kSet.add(D[k])
        k = int(k // D[k])
    if count == 1:
        break

if count == 0:
    print("pairwise coprime")
elif sCheck == 1:
    print("setwise coprime")
else:
    print("not coprime")
h,w,m=map(int,input().split())
hlist=[0]*(h+1)
wlist=[0]*(w+1)

cnt=[[False]*(w+1) for i in range(h+1)]
for i in range(m):
  a,b=map(int,input().split())
  hlist[a]+=1
  wlist[b]+=1
  cnt[a][b]=True
  
hcnt,wcnt=0,0
for i in range(1,h+1):
  hcnt=max(hcnt,hlist[i])
  
for i in range(1,w+1):
  wcnt=max(wcnt,wlist[i])

hh,ww=[],[]

for i in range(1,h+1):
  if hlist[i]==hcnt:
    hh+=[i]

for i in range(1,h+1):
  if wlist[i]==wcnt:
    ww+=[i]

ans=0

for i in hh:
  for j in ww:
    if cnt[i][j]==True:
      print(hcnt+wcnt-1)
      exit()
  
print(hcnt+wcnt)

### FIXED CODE ###

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


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


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


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


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


print(hcnt+wcnt-1)
X=int(input())
0<=A<=100
0<=B<=100
if A<=X<=A+B;
print("Yes")
else;
print("No")

### FIXED CODE ###

a, b, x = map(int, input().split())
 
n = x - a
 
if n >= 0 and b >=  n:
    print('YES')
else:
    print('NO')
#include<stdio.h>

int main(void){
  double n;
  int c;
  scanf("%d", &n);
  c = (1+n)/2*n;
  print(c);
  return 0;
}

### FIXED CODE ###

n = float(input())
c = int(((1 + n) / 2) * n)
print(c)
a,b = map(int, input().split())
if a*b%2 == 0:
  print(even)
else:
  print(odd)


### FIXED CODE ###

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

if a*b%2 == 0:
  print('Even')
else:
  print('Odd')
a,b,k=map(int,input().split());*r,=range(a,b+1);print(*sorted(set(r[:k]+r[-k:])),sep='\n')

### FIXED CODE ###

a,b,k=map(int,input().split());r=range(a,b+1);print(*sorted(set(r[:k])|set(r[-k:])),sep='\n')
= int(input())
a = 100
c = 0
while a < x:
    a += a//100
    c += 1
print(c)


### FIXED CODE ###

x = int(input())
a = 100
c = 0
while a < x:
    a += a//100
    c += 1
print(c)
n = int(input())
s = list(map(int, input().split()))
ans = "Three"
for i in range(n):
    if s[i] == "Y":
        ans = "Four"
        break
print(ans)

### FIXED CODE ###

n = int(input())
s = input()
ans = "Three"
for i in range(n):
    if s[i] == "Y":
        ans = "Four"
        break
print(ans)
import sys
sys.setrecursionlimit(10 ** 7)

n = int(input())
adjacent_list = [[] for i in range(n+1)]
data = []
edgedata = [[0 for i in range(n+1)] for j in range(n+1)]
for i in range(n-1):
    a, b = list(map(int, input().split()))
    data.append([a,b])
    adjacent_list[a].append(b)
    adjacent_list[b].append(a)
#adjacent_list = sorted(adjacent_list, key = lambda x:len(x),reverse = True)
max_node = 0
finished = set()
for i in range(1,n):
    if len(adjacent_list[i]) > max_node:
        max_node = i
k = len(adjacent_list[max_node])
def dfs(node, num):
    global edgedata
    node_list = sorted(adjacent_list[node], key = lambda x:len(adjacent_list[x]))
    color_list = [i for i in range(1,k+1) if i != num]
    c_i = 0
    finished.add(node)
    for i in node_list:
        if i not in finished:
            s = min(node, i)
            t = max(node, i)
            edgedata[s][t] = color_list[c_i]
            dfs(i, color_list[c_i])
            c_i += 1
dfs(k,-1)
print(k)
for i in data:
    print(edgedata[i[0]][i[1]])
#output k


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 7)
n = int(input())
#隣接リスト
adjacent_list = [[] for i in range(n+1)]
#入力されたデータを保存しておくやつ
data = [None] * (n - 1)
#最終的に色を入れておくやつ。
#edgedata[(1,2)] => 1->2の辺の色を入れておく
edgedata = {}
for i in range(n-1):
    a, b = list(map(int, input().split()))
    data[i] = [a, b]
    adjacent_list[a].append(b)
    adjacent_list[b].append(a)
#つながってるノードが一番多いやつを保存しておく
max_node = 0
#探索が終わったやつを入れる
finished = set()
for i in range(1,n):
    if len(adjacent_list[i]) > len(adjacent_list[max_node]):
        max_node = i
#kには色の種類を入れる
k = len(adjacent_list[max_node])
#print("k => {}".format(k))
def dfs(node, num):
    #隣接リストの中身を、つながってるノード順にソート
    node_list = sorted(adjacent_list[node], key = lambda x:len(adjacent_list[x]))
    #さっきつかったいろは使わないようにする
    color_list = [i for i in range(1,len(node_list) + 2) if i != num]
    c_i = 0
    finished.add(node)
    for i in node_list:
        #まだ見てなかったら、dfsを掛ける
        if i not in finished:
            #小さいほうから大きいほうに文字を並べ、ハッシュに値を保存
            #print("{}".format(color_list))
            #print("c_i =>{}  node =>{}".format(c_i,node))
            edgedata[(min(node, i), max(node, i))] = color_list[c_i]
            #color_list[c_i]は使ったので、使った色として引数で渡す。
            dfs(i, color_list[c_i])
            #この色は使ったから、一個ずらす
            c_i += 1
#一番のノードを根とし、dfsをかける
dfs(k,-1)
print(k)
for i in data:
    print(edgedata[tuple(i)])
#output k
def resolve():
    N, D, A = map(int, input().split())
    AB = [list(map(int, input().split())) for _ in range(N)]
    AB.sort()
    
    # imos
    x_max = AB[-1][0] + (2*D+5)
    imos = [0] * x_max
    ans = 0
    R = 0
    for l in range(N):
        if l:
            imos[l] += imos[l-1]
        x = AB[l][0]
        h = AB[l][1]
        if imos[l] < h:
            R = max(R, l+1)
            while R < N and AB[R][0] - x <= 2*D:
                R += 1
            d = h - imos[l]
            cnt = d//A
            imos[l] += cnt*A
            imos[R] -= cnt * A
            ans += cnt
    print(ans)

if __name__ == "__main__":
    resolve()


### FIXED CODE ###


def resolve():
    N, D, A = map(int, input().split())
    AB = [list(map(int, input().split())) for _ in range(N)]
    AB.sort()

    # imos
    imos = [0] * (N+1)
    ans = 0
    R = 0
    for l in range(N):
        if l:
            imos[l] += imos[l - 1]
        x = AB[l][0]
        h = AB[l][1]
        if imos[l] < h:
            R = max(R, l + 1)
            while R < N and AB[R][0] <= 2 * D + x:
                R += 1
            d = h - imos[l]
            cnt = (d+A-1) // A
            imos[l] += cnt * A
            imos[R] -= cnt * A
            ans += cnt
    print(ans)

if __name__ == "__main__":
    resolve()
n=int(input())
a=list(map(int,input().split()))
a_2=[]
for i in range(len(a)):
    a_2.append(bin(a[i]))
import collections
c = collections.Counter(a_2)
b=[]
out=0
for i in c.values():
    b.append(i)
if a.count(0)==0:#0がない場合
    if len(b)!=3:
        out=1
    if b[0]!=b[1] or b[1]!=b[2]:
        out=1
        break
    else:
        pass
else:#0あり
    if len(b)>2:
        out=1
    elif len(b)==1:
        pass
    elif len(b)==2:
        if a.count(0)*3==len(a):
            pass
        else:
            out=1
if out==0:
    print('Yes')
elif out==1:
    print('No')

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
a_2=[]
for i in range(len(a)):
    a_2.append(bin(a[i]))
import collections
c = collections.Counter(a)
b=[]
d=[]
out=0
for i in c.values():
    b.append(i)
for i in c.keys():
    d.append(i)
if a.count(0)==0:#0がない場合
    if len(b)!=3:
        out=1
    elif b[0]!=b[1] or b[1]!=b[2]:
        out=1
    elif (d[0]^d[1]^d[2])!=0:
        out=1
else:#0あり
    if len(b)>2:
        out=1
    elif len(b)==1:
        pass
    elif len(b)==2:
        if a.count(0)*3==len(a):
            pass
        else:
            out=1
if out==0:
    print('Yes')
elif out==1:
    print('No')
n = list(input())
#a,b = map(int,input().split())
#a_L = list(map(int,input().split()))

fx = sum(n)

if int(n)%fx == 0:
    print("Yes")
else:
    print("No")

### FIXED CODE ###


n= input()
x = map(int,list(n))
#a,b = map(int,input().split())
#a_L = list(map(int,input().split()))
#print(n)
fx = sum(x)

if int(n)%fx == 0:
    print("Yes")
else:
    print("No")
a,b=input().split()
a=int(a)
b=int(b)
a//b=d
d=int(d)
a%b=r
r=int(r)
a/b=f
f = float(f)
print(d,r,f)


### FIXED CODE ###

a,b = input().split()
a = int(a)
b = int(b)
d = a // b
r = a % b
f = a / b
print(d,r,"{:.5f}".format(f))
from itertools import accumulate

input()
l = [0] + list(accumulate(c == '.' for c in input()))
print(min(i - x + l[-1] - x for i, x in enumerate(l)))


### FIXED CODE ###

a, b, c = map(int, input().split())
print(('No', 'Yes')[a < c < b or a > c > b])
L=["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y"]
print(L[L.index(input())+1])

### FIXED CODE ###

l="abcdefghijklmnopqrstuvwxyz"
print(l[l.index(input())+1])