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

N, Q = map(int, input().split())
S = input()
for _ in range(Q):
    li, ri = map(int, input().split())
    substr = S[li - 1:ri]
    print(substr.count("AC"))


### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
count = 0
counts = [0 for _ in range(N)]

for i in range(N - 1):
    if S[i] == "A" and S[i + 1] == "C":
        count += 1
        counts[i + 1] = count
    else:
        counts[i + 1] = count

for _ in range(Q):
    li, ri = map(int, input().split())
    print(counts[ri - 1] - counts[li - 1])
### BUGGY CODE ###

N = int(input())
S = {}

for i in range(N):
    s = input()
    if s not in S.values():
        S[i] = s
print(len(S))        

### FIXED CODE ###

N = int(input())
S = []
ans = N
S = [input() for i in range(N)]
#for i in range(N):
#    S.append(input())
S.sort()
for i in range(N-1):
    if S[i] == S[i+1]:
        ans = ans - 1
print(ans)
### BUGGY CODE ###

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

for _ in range(Q):
    inpu_ = input()
    if len(inpu_)==1:
        S.reverse()
    else:
        a,f,c = map(str,inpu_.split())
        if f=="1":
            S.insert(0,c)
        else:
            S.append(c)

print("".join(S))


### FIXED CODE ###

S = input()
Q = int(input())
flag = True
from collections import deque
que=deque(S)

for i in range(Q):
    a = input().split()
    if a[0]=="1":
        flag = not flag

    else:
        f = a[1]
        c = a[2]
        if f=="1":
            if flag:
                que.appendleft(c)
            else:
                que.append(c)
        else:
            if flag:
                que.append(c)
            else:
                que.appendleft(c)

if not flag:
    que.reverse()

print("".join(que))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

debug = True
debug = False

def dprint(*objects):
    if debug == True:
        print(*objects)

def main():
    s = SI()
    t = SI()

    d = {}
    for i, c in enumerate(s):
        if c not in d.keys():
            d[c] = [i]
        else:
            d[c].append(i)

    import collections
    didx = collections.defaultdict(int)

    for c in set(t):
        if c not in d.keys():
            print(-1)
            return

    dprint(d)
    dprint(didx)

    import bisect

    i_loop = 0
    currentidx = -1
    for c in t:
        # 次の文字を読む
        poslist = d[c]

        if len(poslist) <= didx[c]:
            # 文字を取り切っている場合は次のループに
            i_loop += 1
            didx = collections.defaultdict(int)
            currentidx = poslist[0]
            didx[c] += 1
        else:
            # とり切っていない場合
            poslist_afteridx = poslist[didx[c]:]
            posidx = bisect.bisect_right(poslist_afteridx, currentidx)

            if posidx >= len(poslist_afteridx):
                # とれないなら次のループでとったことにする
                i_loop += 1
                didx = collections.defaultdict(int)
                currentidx = poslist[0]
                didx[c] += 1
            else:
                # 同じループでとれるなら取って、現在位置を更新
                pos = poslist_afteridx[posidx]
                currentidx = pos
                didx[c] = posidx + 1

        dprint(c, i_loop, pos, currentidx)
        dprint(didx)

    print(len(s)*i_loop + currentidx + 1)

main()

### FIXED CODE ###

import sys
def SI(): return sys.stdin.readline().strip()

def main():
    s = SI()
    t = SI()

    import collections
    d = collections.defaultdict(list)
    for i, c in enumerate(s):
        d[c].append(i)

    keys = d.keys()
    for c in set(t):
        if c not in keys:
            print(-1)
            return

    import bisect

    i_loop = 0
    currentidx = -1
    for c in t:
        # 次の文字を読む
        poslist = d[c]

        # とり切っていない場合
        posidx = bisect.bisect_right(poslist, currentidx)

        if posidx >= len(poslist):
            # とれないなら次のループでとったことにする
            i_loop += 1
            currentidx = poslist[0]
        else:
            # 同じループでとれるなら取って、現在位置を更新
            pos = poslist[posidx]
            currentidx = pos

    print(len(s)*i_loop + currentidx + 1)

main()
### BUGGY CODE ###

import math

n = int(input())
a = list(map(int, input().split()))
a_ = set(a)
dic = {x:{} for x in a_}
lis = {i:a.count(i) for i in a_}
for i in a_:
    res =0
    for j in a_:
        k = lis[j]
        if i == j:
            k -= 1
            if k > 1:
                x = math.factorial(k) // (math.factorial(k-2) * math.factorial(2))
                res += x
        else:
            if k > 1:
                x = math.factorial(k) // (math.factorial(k-2) * math.factorial(2))
                res += x
    dic[i] = res
for i in a:
    print(dic[i])

### FIXED CODE ###

from collections import Counter

n = int(input())
a = list(map(int, input().split()))
a_ = set(a)
x = Counter(a)
y = {i:x[i]*(x[i]-1)//2 for i in a_}

res = sum(y.values())
for i in a:
    t = x[i]
    t_ = y[i]
    print(res-t_+(t-1)*(t-2)//2)
### BUGGY 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 invmod(a, m):
    g, x, y = xgcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m


n, k = map(int, input().split())
k_ = k - 2
a = sorted([int(i) for i in input().split(" ")])
c = 10**9 + 7

comb = [1 for i in range(n)]
for i in range(1, n-1):
    comb[i] = comb[i-1] * (k_+i) * invmod(i, c) % c
ans = 0
for i in range(n-1, max(-1, n-k-2), -1):
    for j in range(i-k+2):
        #print("ij", i, j)
        tmp = a[i] - a[j]
        
        ans += tmp*comb[i-1-j-k_] % c
        #print("comb_temp", comb[i-2-j-k_], tmp)
        #print("ans", ans)
print(ans%c)



### 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 invmod(a, m):
    g, x, y = xgcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m


n, k = map(int, input().split())
k_ = k - 1
a = sorted([int(i) for i in input().split(" ")])
c = 10**9 + 7

comb = [1 for i in range(n-k_)]
for i in range(1, n-k_):
    comb[i] = comb[i-1] * (k_+i) * invmod(i, c) % c
ans = 0
for i in range(k_, n):       
        ans += a[i]*comb[i-k_] % c
        #print("comb_temp", comb[i-2-j-k_], tmp)
        #print("ans", ans)
for i in range(n-k+1):
    ans -= a[i]*comb[n-k-i]
    ans = ans % c
print(ans)
### BUGGY CODE ###

n, m = map(int,input().split())
a = []
for i in range(m):
    x,y=[int(i) for i in input().split()]
    a.append([x,y])
for s in range(m):
	counter = 1
	for t in range(m):
		if a[s][0] == a[t][0] and a[s][1] > a[t][1]:
			counter += 1
	print(str("{0:06d}".format(a[s][0])) + str("{0:06d}".format(counter)))

### FIXED CODE ###

n,m = map(int,input().split())
si = []
for i in range(m):
    p,y = map(int,input().split())
    si.append([i,p,y])
si.sort(key=lambda x:x[2])
ans = []
all = [0]*n
for i in range(m):
    now = si[i]
    all[now[1]-1] += 1
    x = all[now[1]-1]
    ans.append([now[0],now[1],x])
ans.sort(key=lambda x:x[0])
for i in range(m):
    now = ans[i]
    str_1 = str(now[1])
    str_1 = str_1.zfill(6)
    str_2 = str(now[2])
    str_2 = str_2.zfill(6)
    print(str_1+str_2)
### BUGGY CODE ###

n = int(input())
s = [input() for i in range(n)]

ans = []
for i in range(n):
    if not s[i] in ans:
        ans.append(s[i])

print(len(ans))

### FIXED CODE ###

import collections
n = int(input())
s = [input() for i in range(n)]

ans = collections.Counter(s)
print(len(ans))
### BUGGY CODE ###

import numpy as np
INF = 10**15
def solve(n, k, h):
    dp = np.full((n+1, n+1), INF, dtype=int)
    dp[0, 0] = 0
    h = [0] + h
    for x in range(n+1):
        for y in range(n+1):
            for i in range(x):
                dp[x, y] = min(dp[x, y], dp[i, y-1] + max(0, h[x] - h[i]))
    return np.min(dp[:, n-k])

n, k = map(int, input().split())
h = list(map(int, input().split()))
print(solve(n, k, h))

### FIXED CODE ###

import numpy as np
INF = 10**15
def solve(n, k, h):
    dp = np.full((n+1, n+1), INF, dtype=int)
    dp[0, 0] = 0
    h = np.array([0] + h, dtype=int)
    for i, h_i in enumerate(h[1:], 1):
        t = np.maximum(h_i - h[:i], 0)
        dp[i,1:] = np.min(dp[:i,:-1]+t[:,None], axis=0)
    return np.min(dp[:, n-k])

n, k = map(int, input().split())
h = list(map(int, input().split()))
print(solve(n, k, h))
### BUGGY CODE ###

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

    cut_mode = True
    
    if cut_mode and K + min(A) >= N:
        print(" ".join(map(str, [N]*N)))
        return

    from functools import lru_cache

    @lru_cache(maxsize=100000)
    def func(i, a):
        A_tmp = [0] * len(A)
        #print(A_tmp[i:i+a+1])
        A_tmp[i:i+a+1] = [1]*(len(A_tmp[i:i+a+1]))

        #print(A_tmp[i-a:i+1])
        A_tmp[max(0, i-a):i+1] = [1]*(len(A_tmp[max(0, i-a):i+1]))
        
        #print(A_tmp)
        return A_tmp


    for i in range(K):
        #print("i", i)
        A_next = [0] * len(A)
        for i, a in enumerate(A):
            #print(i, a)
            A_tmp = func(i, a)
            #print("A_tmp", A_tmp)
            A_next = [x + y for (x, y) in zip(A_next, A_tmp)]
            #print("A_next", A_next)

        A = copy.deepcopy(A_next)
        #print("new A: ", A)

        if cut_mode and min(A) == N:
            break 

    print(" ".join(map(str, A_next)))

if __name__ == "__main__":
    resolve()

### FIXED CODE ###

import copy
from functools import lru_cache
import numpy as np
from numba import njit

#@njit
# @njit('(i8[::1],)', cache=True)
# def func(A):
#     N = len(A)
#     B = np.zeros_like(A)
#     for i in range(N):
#         l = max(0, i - A[i])
#         r = min(i + A[i], N-1)
#         B[l] += 1
#         if r+1 < N:
#             B[r+1] -= 1

#     B = np.cumsum(B)
#     return B

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

    # N = 2 * 10**5
    # K = 2 * 10**5
    # A = np.array([0] *  N)

    @njit
    def func(A):
        #N = len(A)
        B = np.zeros_like(A)
        for i in range(N):
            l = max(0, i - A[i])
            r = min(i + A[i], N-1)
            B[l] += 1
            if r+1 < N:
                B[r+1] -= 1

        B = np.cumsum(B)
        return B

    for k in range(K):
        #print(k)
        A = func(A)
        if k >= 50:
            break

    print(" ".join(map(str, A)))

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

from fractions import gcd

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

mod=10**9+7

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

L=A[0]
for i in range(1,n):
    L=lcm(L,A[i])
ans=0
for i in range(n):
    ans+=(L//A[i])%mod
print(ans%mod)

### FIXED CODE ###

from fractions import gcd

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

mod=10**9+7

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

L=A[0]
for i in range(1,n):
    L=lcm(L,A[i])
L%=mod

coef=sum(pow(x,mod-2,mod) for x in A)
print(L*coef%mod)
### BUGGY CODE ###

import bisect
import functools
import os
import sys

sys.setrecursionlimit(10000)
INF = float('inf')

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


def debug(fn):
    if not os.getenv('LOCAL'):
        return fn

    @functools.wraps(fn)
    def wrapper(*args, **kwargs):
        ret = fn(*args, **kwargs)
        print('DEBUG: {}({}) -> '.format(
            fn.__name__,
            ', '.join(
                list(map(str, args)) +
                ['{}={}'.format(k, str(v)) for k, v in kwargs.items()]
            )
        ), end='')
        print(ret)
        return ret

    return wrapper


@debug
def calc_bit(k):
    """
    答えの下から k ビット目を返す
    :param int k:
    :return:
    """
    # 答えの k ビット目が偶数なら 0、奇数なら 1

    # これ以上の桁は不要
    mod = 1 << (k + 1)
    amod = [a & (mod - 1) for a in A]
    bmod = [b & (mod - 1) for b in B]
    bmod.sort()
    ret = 0
    for a in amod:
        # bmod + a のうち k ビット目が 1 となる数
        # => (1 << k) 以上 (2 << k) 未満または (3 << k) 以上 (4 << k) 未満
        ret += bisect.bisect_left(bmod, (2 << k) - a) - bisect.bisect_left(bmod, (1 << k) - a)
        ret += bisect.bisect_left(bmod, (3 << k) - a) - len(bmod)

    return ret % 2


ans = 0
for i in range(30):
    ans += calc_bit(i) * (2 ** i)
print(ans)


### FIXED CODE ###

import bisect
import functools
import os
import sys

sys.setrecursionlimit(10000)
INF = float('inf')

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


def debug(fn):
    if not os.getenv('LOCAL'):
        return fn

    @functools.wraps(fn)
    def wrapper(*args, **kwargs):
        ret = fn(*args, **kwargs)
        print('DEBUG: {}({}) -> '.format(
            fn.__name__,
            ', '.join(
                list(map(str, args)) +
                ['{}={}'.format(k, str(v)) for k, v in kwargs.items()]
            )
        ), end='')
        print(ret)
        return ret

    return wrapper


@debug
def calc_bit(k):
    """
    答えの下から k ビット目を返す
    :param int k:
    :return:
    """
    # 答えの k ビット目が偶数なら 0、奇数なら 1

    # これ以上の桁は不要
    mod = 1 << (k + 1)
    amod = [a & (mod - 1) for a in A]
    bmod = [b & (mod - 1) for b in B]
    amod.sort()
    bmod.sort()
    ret = 0

    # bmod + amod のうち k ビット目が 1 となる数
    # => (1 << k) 以上 (2 << k) 未満または (3 << k) 以上 (4 << k) 未満
    # しゃくとる
    b01 = bisect.bisect_left(bmod, (1 << k) - amod[0])
    b10 = bisect.bisect_left(bmod, (2 << k) - amod[0])
    b11 = bisect.bisect_left(bmod, (3 << k) - amod[0])
    for a in range(len(amod)):
        while b01 - 1 >= 0 and bmod[b01 - 1] >= (1 << k) - amod[a]:
            b01 -= 1
        while b10 - 1 >= 0 and bmod[b10 - 1] >= (2 << k) - amod[a]:
            b10 -= 1
        while b11 - 1 >= 0 and bmod[b11 - 1] >= (3 << k) - amod[a]:
            b11 -= 1
        # (1 << k) 以上 (2 << k) 未満
        ret += b10 - b01
        # (3 << k) 以上 (4 << k) 未満
        ret += len(bmod) - b11

    return ret % 2


ans = 0
for i in range(30):
    ans += calc_bit(i) * (2 ** i)
print(ans)
### BUGGY CODE ###

from operator import mul
from functools import reduce
from bisect import bisect_left
from sys import stdin


def solve(a):
    a.sort()
    max_cmb = cmb(a[1], a[0])
    ans = [a[1], a[0]]
    for ai in a[n-1:1:-1]:
        divided_ai = ai//2
        ak = a[bisect_left(a, divided_ai)]
        q = cmb(ai, ak)
        if a[1] <= ai//2:
            aj = a[bisect_left(a, divided_ai)-1]
            p = cmb(ai, aj)
            if q < p and max_cmb < p:
                ans = [ai, aj]
                max_cmb = p
            elif max_cmb < q:
                ans = [ai, ak]
                max_cmb = q
            else:
                return str(ans[0]) + ' '+str(ans[1])

        else:
            if max_cmb < q:
                ans = [ai, ak]
                max_cmb = q
            else:
                return str(ans[0]) + ' '+str(ans[1])

    return str(ans[0]) + ' '+str(ans[1])


def cmb(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


if __name__ == '__main__':
    n = int(input())
    a = list(map(int, stdin.readline().split()))
    print(solve(a))


### FIXED CODE ###

from bisect import bisect_left
from sys import stdin



def solve(a):
    a.sort()
    mid = a[n-1]/2
    ai = a[bisect_left(a, mid)-1]
    aj = a[bisect_left(a, mid)]
    am = ai if abs(mid-ai) <= abs(mid-aj) else aj

    print(a[n-1], am)


if __name__ == '__main__':
    n = int(input())
    a = list(map(int, stdin.readline().split()))
    solve(a)
### BUGGY CODE ###

n, m = map(int, input().split())
U = 10**9
for i in range(n, U+1):
    if m % i == 0:
        print(m//i)
        break


### FIXED CODE ###

n, m = map(int, input().split())
divisors = set()
for i in range(1, int(m**.5)+1):
    if m % i == 0:
        divisors |= {i, m//i}
divisors = sorted(divisors)
for div in divisors:
    if n <= div:
        print(m//div)
        break
### BUGGY CODE ###

import sys
import math
import collections
import bisect
import copy

# import numpy as np

sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))


# ===CODE===


def main():
    n, m = ns()
    e = [[] for _ in range(n)]
    root = [True for _ in range(n)]
    ans = [-1 for _ in range(n)]

    for _ in range(n - 1 + m):
        a, b = ns()
        a, b = a - 1, b - 1
        e[a].append(b)
        root[b] = False

    root_idx = root.index(True)

    que = collections.deque([root_idx])
    while que:
        q = que.popleft()

        for ei in e[q]:
            ans[ei] = q
            que.append(ei)

    for ansi in ans:
        print(ansi + 1)



if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import math
import collections
import bisect
import copy

# import numpy as np

sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))


# ===CODE===


def main():
    n, m = ns()
    e = [[] for _ in range(n)]
    root = [True for _ in range(n)]
    prnt_cnt = [0 for _ in range(n)]
    ans = [-1 for _ in range(n)]

    for _ in range(n - 1 + m):
        a, b = ns()
        a, b = a - 1, b - 1
        e[a].append(b)
        root[b] = False
        prnt_cnt[b] += 1

    root_idx = root.index(True)

    que = collections.deque([root_idx])

    while que:
        q = que.popleft()

        for ei in e[q]:
            ans[ei] = q
            prnt_cnt[ei] -= 1
            if prnt_cnt[ei] == 0:
                que.append(ei)

    for ansi in ans:
        print(ansi + 1)


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

n = int(input())
A = list(map(int, input().split()))
result = 1

for number in A:
  result = result * number
  
if result > 1000000000000000000:
  print(-1)  
  
else:
  print(result)
  

### FIXED CODE ###

tukawan = int(input())
A = list(map(int, input().split())) 
result = 1

if 0 in A:
    print(0)

else:
  for number in A:
    result = result * number
    
    if result > 1000000000000000000:
      result = -1
      break
    
  print(result)
### BUGGY CODE ###

mod = 1000000000+7

def product(N, As):
  result = 0
  for i in range(N):
    left = As[i]
    rights = As[i+1:]
    result += left * sum(rights)
  return result % mod


if __name__ == "__main__":
  N = list(map(int, input().split()))
  As = list(map(int, input().split()))
  print(product(N[0], As))

### FIXED CODE ###

mod = 1000000000+7

def product(N, As):
  result = 0
  summer = sum(As)
  for i in range(N-1):
    left = As[i]
    summer = summer - left
    result += left * summer
    
  return result % mod


if __name__ == "__main__":
  N = list(map(int, input().split()))
  As = list(map(int, input().split()))
  print(product(N[0], As))
### BUGGY CODE ###

# coding: utf-8
import math
#import numpy
#N = int(input())
N, K = map(int,input().split())
A = list(map(int,input().split()))
#K =int(input())
ANS = []
a = 1
for i in range(K):
    a *= A[K-i-1]
ANS.append(a)
for i in range(K,N):
    a *=A[i]
    a //= A[i-K]
    ANS.append(a)
#print(ANS)
for i in range(N-K):
    if ANS[i+1] > ANS[i]:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

# coding: utf-8
#import math
#import numpy
#N = int(input())
def main():
    import sys
    input = sys.stdin.readline
    N, K = map(int,input().split())
    A = list(map(int,input().split()))
    #K =int(input())
    ANS = []
    
    #ANS.append(a)
    for i in range(K,N):
        if A[i-K] < A[i]:
            print("Yes")
        else:
            print("No")
        
        
        #ANS.append(a)
    #print(ANS)
    

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

import sys
import math
import fractions
import bisect
sys.setrecursionlimit(4100000)

MOD = int(1e9+7)
PI = 3.14159265358979323846264338327950288
INF = 1e18

'''
1行のint
N, K = map(int, input().split())

1行のstring
S, T = input().split()

1行の整数配列
P = list(map(int,input().split()))

改行あり
x = []
y = []
for i in range(N):
    x1,y1=[int(i) for i in input().split()]
    x.append(x1)
    y.append(y1)

N行M列の初期化
dp = [[INF] * M for i in range(N)]

'''

N, D, A = map(int, input().split())
XH = []
X = []

for i in range(N):
    x1,y1=[int(i) for i in input().split()]
    XH.append([x1, y1])

    
def counting(hp):
    return hp//A + int(hp%A!=0)

ans = 0
XH.sort()
for i in range(N):
    X.append(XH[i][0])

begin = 0
last = XH[begin][0] + 2*D
while True:
    need = counting(XH[begin][1])
    ans += need
    
    # これより手前までを減らす
    end = bisect.bisect_right(X, last)

    # 爆発
    for i in range(begin, end):
        # 最後に達したら終える
        if i == N:
            break
        XH[i][1] -= need*A
        
    # 次の範囲に更新
    for i in range(begin, end):
        
        if XH[i][1] > 0:
            begin = i
            last = XH[begin][0] + 2*D
            break

        # 最後まで０にできてたらおしまい
        elif i == N-1:
            print(ans)
            sys.exit()

        # 範囲がすべて０以下なら次に行く
        elif i == end-1:
            begin = end
            last = XH[begin][0] + 2*D








"""
ATTENTION: Pythonで間に合うか？？

            <目安>
 文字列結合、再帰関数を含む→Python
 上を含まず時間が不安→PyPy3

"""

### FIXED CODE ###

import sys
import math
import fractions
import bisect
import queue
import heapq
from collections import deque
sys.setrecursionlimit(4100000)

MOD = int(1e9+7)
PI = 3.14159265358979323846264338327950288
INF = 1e18

'''
1行のint
N, K = map(int, input().split())

1行のstring
S, T = input().split()

1行の整数配列
P = list(map(int,input().split()))

改行あり
x = []
y = []
for i in range(N):
    x1,y1=[int(i) for i in input().split()]
    x.append(x1)
    y.append(y1)

N行M列の初期化
dp = [[INF] * M for i in range(N)]

'''

N, D, A = map(int, input().split())
XH = []

for i in range(N):
    x1,y1=[int(i) for i in input().split()]
    XH.append([x1, y1])

    
def counting(hp):
    if hp < 0:
        return 0
    return hp//A + int(hp%A!=0)

XH.sort()


bombs = deque([]) # 有効な爆弾の威力と範囲を保存する
power = 0 # 有効な爆弾の威力の合計

ans = 0
for i in range(N):
    
    # 使えない爆弾を捨てる
    while len(bombs)>0 and bombs[0][0] < XH[i][0]:
        power -= bombs.popleft()[1]

    # パワーの不足分の爆弾
    add = counting(XH[i][1]-power) 
    ans += add
    
    # 追加した爆弾をキューに加える
    bombs.append((XH[i][0] + 2*D, add*A))
    power += add*A


print(ans)









"""
ATTENTION: Pythonで間に合うか？？

            <目安>
 文字列結合、再帰関数を含む→Python
 上を含まず時間が不安→PyPy3

"""
### BUGGY CODE ###

# problem D
s = input()
Q = int(input())

query = [input().split() for _ in range(Q)]
    
summ = 0
    
for i in query:
    if int(i[0]) == 1:
        summ += 1
    elif (summ % 2 == 0 and int(i[1]) == 1) or (summ % 2 == 1 and int(i[1]) == 2):
        s = ''.join([str(i[2]),s])
    else:
        s = ''.join([s,str(i[2])])
    
if summ % 2 == 1:
    s = s[::-1]
        
print(s)

### FIXED CODE ###

from collections import deque

s = deque(input())
Q = int(input())
    
t = True
    
for i in range(Q):
    query = input().split()
    if query[0] == '1':
        t = not t
    else:
        if(t and query[1] == '1') or (not t and query[1] == '2'):
            s.appendleft(query[2])
        else:
            s.append(query[2])
            
s = ''.join(s)
    
if not t:
    s = s[::-1]
        
print(s)