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

import bisect
import sys
input = sys.stdin.readline
n,d,a = map(int,input().split())
xh = [list(map(int,input().split())) for i in range(n)]
for i in range(n):
  xh[i][1] = (xh[i][1]+a-1)//a
xh.sort()
x = [xh[i][0] for i in range(n)]
remain = [xh[i][1] for i in range(n)]
ans = 0
for i in range(n):
  if remain[i] <= 0:
    continue
  br = bisect.bisect_right(x,x[i]+2*d)
  k = remain[i]
  ans += k
  for j in range(i,br):
    remain[j] -= k
print(ans)

### FIXED CODE ###

import bisect
import sys
input = sys.stdin.readline
from collections import defaultdict
class Bit:
  def __init__(self, n):
    self.size = n
    self.tree = [0] * (n + 1)

  def sum(self, i):
    s = 0
    while i > 0:
        s += self.tree[i]
        i -= i & -i
    return s

  def add(self, i, x):
    while i <= self.size:
      self.tree[i] += x
      i += i & -i
n,d,a = map(int,input().split())
xh = [list(map(int,input().split())) for i in range(n)]
for i in range(n):
  xh[i][1] = (xh[i][1]+a-1)//a
xh.sort()
x = [xh[i][0] for i in range(n)]
remain = [xh[i][1] for i in range(n)]
ans = 0
bit = Bit(n+1)

for i in range(n):
  if bit.sum(i+1) >= remain[i]:
    continue
  br = bisect.bisect_right(x,x[i]+2*d)
  y = remain[i]-bit.sum(i+1)
  ans += y
  bit.add(i+1,y)
  bit.add(br+1,-y)
print(ans)
### BUGGY CODE ###

from collections import defaultdict
from itertools import combinations

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

adj = defaultdict(list)
in_deg = {(i, j): 0 for i, j in combinations(range(n), 2)}

for i, li in enumerate(a):
    for j, k in zip(li, li[1:]):
        j -= 1
        k -= 1
        match1 = min(i, j), max(i, j)
        match2 = min(i, k), max(i, k)
        adj[match1].append(match2)
        in_deg[match2] += 1

cnd = [k for k, v in in_deg.items() if v == 0]
day = 0
while cnd:
    nxt_cnd = []
    for u in cnd:
        for v in adj[u]:
            in_deg[v] -= 1
            if in_deg[v] == 0:
                nxt_cnd.append(v)

    cnd = nxt_cnd
    day += 1

if sum(in_deg.values()) != 0:
    day = -1

print(day)


### FIXED CODE ###

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


def match2int(x, y):
    x, y = min(x, y), max(x, y)
    return (2 * n - 1 - x) * x // 2 + y - x - 1


match_sm = n * (n - 1) // 2

adj = [[] for _ in range(match_sm)]
in_deg = [0] * match_sm
for i, li in enumerate(a):
    for j, k in zip(li, li[1:]):
        j -= 1
        k -= 1
        match1 = match2int(i, j)
        match2 = match2int(i, k)
        adj[match1].append(match2)
        in_deg[match2] += 1

cnd = [i for i, e in enumerate(in_deg) if e == 0]
day = 0
while cnd:
    nxt_cnd = []
    for u in cnd:
        for v in adj[u]:
            in_deg[v] -= 1
            if in_deg[v] == 0:
                nxt_cnd.append(v)

    cnd = nxt_cnd
    day += 1

if in_deg.count(0) != match_sm:
    day = -1

print(day)
### BUGGY CODE ###

from functools import reduce
from operator import mul

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

if 0 in a_li:
    print(0)
    exit()

ans = reduce(mul, a_li)

if ans > 1000000000000000000:
    print(-1)
    exit()
else:
    print(ans)


### FIXED CODE ###

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

if 0 in a_li:
    print(0)
    exit()

ans = 1
a_li = [a for a in a_li if a != 1 and a != 0]
a_li.append(1)
for a in a_li:
    ans *= a
    if ans > 1000000000000000000:
        print(-1)
        exit()
print(ans)
### BUGGY CODE ###

n = int(input())
s = [''.join(sorted(input())) for i in range(n)]


cnt = 0
for i in range(len(s)):
    tmp = s[i+1:].count(s[i])
    cnt += tmp

print(cnt)

### FIXED CODE ###

n = int(input())
s = [''.join(sorted(input())) for i in range(n)]

cnt = 0
dic = {}
for i in s:
    dic.setdefault(i, 0)
    cnt += dic[i]
    dic[i] += 1

print(cnt)
### BUGGY CODE ###

n,w = map(int,input().split())
dp = [[0]*(w+1) for j in range(n+1)] # DPテーブルの作成
v = []
W = []
for i in range(n):
    w_,v_ = map(int,input().split())
    v.append(v_)
    W.append(w_)
for i in range(n):
    for j in range(w+1):
        if j >= W[i]:
            dp[i+1][j] = max(dp[i][j],dp[i][j-W[i]]+v[i])
        else:
            dp[i+1][j] = dp[i][j]
print(dp[n][w])

### FIXED CODE ###


import numpy as np
n, W = map(int,input().split())
w = []
v = []
for i in range(n):
    w_,v_= map(int,input().split())
    w.append(w_)
    v.append(v_)
dp = np.zeros(W+1, dtype=np.int64)
for i in range(n):
	dp[w[i]:] = np.maximum(dp[:-w[i]] + v[i], dp[w[i]:])
print(dp[W])
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
A.reverse()
ans = 0
max_step = 0
for i in range(N):
    ans += max(A[i:]) - A[i]
print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = 0
for i in range(1, N):
    if A[i-1] <= A[i]:
        continue
    ans += A[i-1] - A[i]
    A[i] = A[i-1]
print(ans)
### BUGGY CODE ###

n, k = map(int, input().lower().split())
h = map(int, input().lower().split())

h = list(h)
max_monster = []

if k >= len(h):
  print("0")
else:
  for i in range(0, len(h)):
      h[i] = int(h[i])
      
  for i in range(0, k):
    max_monster.append(max(h))
  print(sum(h) - sum(max_monster))
  
  


### FIXED CODE ###

N, K = map(int, input().lower().split())
H = []
total = 0
input_string = input()
H = input_string.split()
H = list(map(int, H))

H.sort(reverse = True)
del H[0:K]

print(sum(H))
### BUGGY CODE ###

def main():
    import sys
    def MI():
        return map(int, sys.stdin.readline().rstrip().split())
    def LI():
        return list(map(int, sys.stdin.readline().rstrip().split()))  # 空白あり

    N,Q = MI()
    c = [0] + LI()
    lr = []
    for i in range(Q):
        l,r = MI()
        lr.append((r,l,i))

    lr.sort()  # 右端rでソート
    a = 0
    d = {}  # d[i] = 玉iが現れた最も右の位置
    ANS = [0]*Q


    class BIT():
        def __init__(self, init_value):
            self.n = len(init_value)
            self.tree = [0] * (self.n + 1)
            for i in range(1, self.n + 1):
                x = init_value[i - 1]
                while i <= self.n:
                    self.tree[i] += x
                    i += i & (-i)

        def update(self, i, x):  # i(1-index)番目の値を+x
            while i <= self.n:
                self.tree[i] += x
                i += i & (-i)
            return

        def query(self, i):  # 1番目からi(1-index)番目までの和を返す
            res = 0
            while i > 0:
                res += self.tree[i]
                i -= i & (-i)
            return res


    bit = BIT([0]*N)  # 最も右に現れた玉の位置を管理
    for i in range(1,N+1):
        if not c[i] in d.keys():
            d[c[i]] = i
            bit.update(i,1)
        else:
            bit.update(d[c[i]],-1)
            d[c[i]] = i
            bit.update(i, 1)
        while a <= Q-1 and lr[a][0] == i:
            r,l,j = lr[a]
            ANS[j] = bit.query(r)-bit.query(l-1)
            a += 1

    print(*ANS,sep='\n')


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    import sys
    def MI():
        return map(int, sys.stdin.readline().rstrip().split())
    def LI():
        return list(map(int, sys.stdin.readline().rstrip().split()))  # 空白あり

    N,Q = MI()
    c = [0] + LI()
    lr = []
    for i in range(Q):
        l,r = MI()
        lr.append((i,l,r))

    from operator import itemgetter

    lr = sorted(lr,key=itemgetter(2))  # 右端rでソート
    a = 0
    d = {}  # d[i] = 玉iが現れた最も右の位置
    ANS = [0]*Q


    class BIT():
        def __init__(self, init_value):
            self.n = len(init_value)
            self.tree = [0] * (self.n + 1)
            for i in range(1, self.n + 1):
                x = init_value[i - 1]
                while i <= self.n:
                    self.tree[i] += x
                    i += i & (-i)

        def update(self, i, x):  # i(1-index)番目の値を+x
            while i <= self.n:
                self.tree[i] += x
                i += i & (-i)
            return

        def query(self, i):  # 1番目からi(1-index)番目までの和を返す
            res = 0
            while i > 0:
                res += self.tree[i]
                i -= i & (-i)
            return res


    bit = BIT([0]*N)  # 最も右に現れた玉の位置を管理
    for i in range(1,N+1):
        if not c[i] in d.keys():
            d[c[i]] = i
            bit.update(i,1)
        else:
            bit.update(d[c[i]],-1)
            d[c[i]] = i
            bit.update(i, 1)
        while a <= Q-1 and lr[a][2] == i:
            j,l,r = lr[a]
            ANS[j] = bit.query(r)-bit.query(l-1)
            a += 1

    print(*ANS,sep='\n')


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

h, n = (int(x) for x in input().split())
w = []
v = []
for _ in range(n):
    a, b = (int(x) for x in input().split())
    w.append(a)
    v.append(b)
dp = [float('inf')] * (h)
for i in range(n):
    for j in range(h):
        if j < w[i]:
            dp[j] = min(dp[j], v[i])
        else:
            dp[j] = min(dp[j], dp[j - w[i]] + v[i])
print(dp[h - 1])

### FIXED CODE ###

h, n = (int(x) for x in input().split())
ab = []
for _ in range(n):
    a, b = (int(x) for x in input().split())
    ab.append([a, b])
max_a = max(a for a, _ in ab)
dp = [0] * (h + max_a)
for i in range(1, h + 1):
    dp[i] = min(dp[i - a] + b for a, b in ab)
print(dp[h])
### BUGGY CODE ###

c=0
a = int(input())
for i in range(1,3234566668):
    f=0
    if i>12:
        l = [int(x) for x in list(str(i))]
        for j in range(1,len(str(i))):
            if abs(l[j-1]-l[j])>1:
                f=1
    if f==0:
        c+=1
    if c==a:
        print(i)
        break

### FIXED CODE ###

import queue
count=9
target=int(input())
q=queue.Queue()
for i in range(1,10):
    q.put(i)
if count>=target:
    print(target)

if count<target:
    while(1):
        a=q.get()
        if a%10!=0:
            q.put(a*10+a%10-1)
            count+=1
            if count==target:
                print(a*10+a%10-1)
                break
        q.put(a*10+a%10)
        count+=1
        if count==target:
            print(a*10+a%10)
            break
        if a%10!=9:
            q.put(a*10+a%10+1)
            count+=1
            if count==target:
                print(a*10+a%10+1)
                break
### BUGGY CODE ###

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def pattcount(num):
    if(num < 0): return 0
    result = 1
    ranmax = num // 2 + 1
    for i in range(1, ranmax):
        result += cmb(num-i, i)
    
    return result
    

if __name__ == '__main__':
    n,m = list(map(int, input().split()))

    pattern = 1
    step = 0
    for i in range(m):
        a = int(input())
        pattern *= pattcount(a - 1 - step)
        step = a + 1

    pattern *= pattcount(n - step)

    print(pattern % 1000000007)


### FIXED CODE ###

if __name__ == '__main__':
    n,m = list(map(int, input().split()))
    a = []
    for i in range(m):
        a.append(int(input()))
    a.append(0)
    ac = 0

    step0 = 0
    step1 = 1
    for i in range(1, n+1):
        temp = step0 + step1
        step0 = step1
        step1 = temp
        if(i == a[ac]):
            step1 = 0
            ac += 1

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

import copy
from collections import deque
def main():
  H, W = map(int, input().split())
  M = [['#' == x for x in input()] for _ in range(H)]

  black = deque([(i, j) for i in range(H) for j in range(W) if M[i][j]])

  ans = 0
  while True:
    ans += 1
    next_black = deque()
    while black:
      bi, bj = black.popleft()
      if bi - 1 >= 0 and not M[bi - 1][bj]:
        M[bi - 1][bj] = True
        next_black.append((bi - 1, bj))
      if bj - 1 >= 0 and not M[bi][bj - 1]:
        M[bi][bj - 1] = True
        next_black.append((bi, bj - 1))
      if bi + 1 < H and not M[bi + 1][bj]:
        M[bi + 1][bj] = True
        next_black.append((bi + 1, bj))
      if bj + 1 < W and not M[bi][bj + 1]:
        M[bi][bj + 1] = True
        next_black.append((bi, bj + 1))
    if next_black:
       black = copy.copy(next_black)
    else:
       break
  print(ans - 1)
  
if __name__ == "__main__":
  main()


### FIXED CODE ###

from collections import deque
import copy
 
def main():
    h, w = map(int, input().split())
    a = [[j == "#" for j in input()] for _ in range(h)]
 
 
    que = deque([(i, j) for i in range(h) for j in range(w) if a[i][j]])
 
    count = 0
    while True:
        count += 1
        nque = deque()
        while que:
            y, x = que.popleft()
            if x > 0 and not a[y][x-1]:
                a[y][x-1] = True
                nque.append((y,x-1))
            if x < w-1 and not a[y][x+1]:
                a[y][x+1] = True
                nque.append((y,x+1))
            if y > 0 and not a[y-1][x]:
                a[y-1][x] = True
                nque.append((y-1,x))
            if y < h-1 and not a[y+1][x]:
                a[y+1][x] = True
                nque.append((y+1,x))
 
        if nque:
            que = copy.copy(nque)
        else:
            break
 
    print(count - 1)

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

s = input().rstrip().split()
a = int(s[0])
b = int(s[1])
c = int(s[2])
k = int(s[3])

for i in range(k):
  n_a = b+c
  n_b = a+c
  n_c = a+b
  a = n_a
  b = n_b
  c = n_c
  if(a == b and b == c ):
    break

d = a - b
if(abs(d) < 100000000):
  print(a-b)
else:
  print("Unfair")

### FIXED CODE ###

s = input().rstrip().split()
a = int(s[0])
b = int(s[1])
c = int(s[2])
k = int(s[3])

ans = a - b

if(k%2==1):
  ans = -1 * ans

if(abs(ans) < 1000000000000000000):
  print(ans)
else:
  print("Unfair")
### BUGGY CODE ###

while True:
    try:
        n = int(input())
        prime_cnt = 0

        for i in range(2, n+1):
            cnt = 0
            for j in range(1,i):
                if i % j == 0:
                    cnt = cnt + 1
                    
            if cnt == 1:
                #?´???°
                prime_cnt = prime_cnt + 1
                

        print(str(prime_cnt))
    except:
        break
    

### FIXED CODE ###

#init
max_num = 1000000
is_prime_num = [True for i in range (max_num+1)]

#0, 1 --- not prime number
is_prime_num[0] = False
is_prime_num[1] = False
end = int(max_num ** .5)

for i in range(2, end+1):
    if is_prime_num[i]:
        for j in range(i*i, max_num+1, i):
            is_prime_num[j] = False


while True:
    try:
        n = int(input())
        prime_cnt = 0
        for i in range(1, n+1):
            if is_prime_num[i]:
                prime_cnt = prime_cnt + 1
                   
   
        print(str(prime_cnt))
    except:
        break
### BUGGY CODE ###

K=int(input())
i=1
current_num=0
while (i<=K) :
  current_num+=1
  current_string=str(current_num)
  
  
  
  flag=True
  for k in range(len(current_string)-1) :
    
    if abs(int(current_string[k])-int(current_string[k+1]))>1 :
      
      flag=False
      break
  if flag==True :
    i+=1
  
  
print(current_num)


### FIXED CODE ###

from collections import deque
a=int(input())
list1=deque([1,2,3,4,5,6,7,8,9])
i=1
while(i<=a) :
  #print (list1)
  if i!=a :
    k=list1.popleft()
    k=str(k)
    if int(k[-1])==0 :
      list1.append(int(str(k)+'0'))
      list1.append(int(str(k)+'1'))
      i+=1
    elif int(k[-1])==9 :
      list1.append(int(str(k)+'8'))
      list1.append(int(str(k)+'9'))
      i+=1
    else :
      list1.append(int(str(k)+str(int(k[-1])-1)))
      list1.append(int(str(k)+str(int(k[-1]))))
      list1.append(int(str(k)+str(int(k[-1])+1)))
      i+=1
  else :
    print(list1[0])
    break
### BUGGY CODE ###

N = int(input())
A_list = list(map(int, input().split()))
sum = 1
for i in range(N):
    sum = sum * A_list[i]

if sum > 10**18:
    print("-1")
else:
    print(sum)

### FIXED CODE ###

N = int(input())
A_list = list(map(int, input().split()))
limit = 10**18
sum = 1

if 0 in A_list:
    print(0)
else:
    for i in  A_list:
        sum = sum * i
        if sum > limit:
            sum = -1
            break
    print(sum)
### BUGGY CODE ###

n = int(input())
c = list(map(int, input().split()))
ans=1
max =10**18
for i in range(n):
    if ans< max:
        ans=ans*c[i]
        if ans > max:
            ans =-1
    else:
        ans = -1
print(ans)

### FIXED CODE ###

n = int(input())
c = list(map(int, input().split()))
ans=1
max =10**18

if 0 in c:
    ans =0
else:
    for i in range(n):
        if ans< max:
            ans=ans*c[i]
            if ans > max:
                ans =-1
                break
        else:
            ans = -1
            break
print(ans)
### BUGGY CODE ###

def abc161_C(N,K):
    if K == 1:
        return print(0)
    Min = 0
    diff_list = [N]
    while 1:
        diff = abs(N - K)
        N = diff
        if diff in diff_list:
            return print(min(diff_list))
        elif diff < K/2:
            diff_list.append(diff)
            return print(min(diff_list))
        else:
            diff_list.append(diff)
    
N,K = map(int,input().split())
abc161_C(N,K)

### FIXED CODE ###

def abc161_C(N,K):
    if K == 1:
        return print(0)
    Min = 0
    N = N%K
    diff_list = [N]
    while 1:
        diff = abs(N - K)
        N = diff
        if diff in diff_list:
            return print(min(diff_list))
        elif diff < K/2:
            diff_list.append(diff)
            return print(min(diff_list))
        else:
            diff_list.append(diff)
    
N,K = map(int,input().split())
abc161_C(N,K)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N=int(input())
    M=N**2
    P=tuple(map(int1,input().split()))
    d=[0]*M
    for i in range(N):
        for j in range(N):
            d[i*N+j]=min(min(i,N-1-i),min(j,N-1-j))
    used=[1]*M
    ans=0
    que=[]
    for p in P:
        ans+=d[p]
        used[p]=0
        que.append(p)
        while que:
            x=que.pop()
            for ddx in (-1,1,-N,N):
                nx=x+ddx
                if 0<=nx<M:
                    if used[x]==0 and d[nx]-d[x]>=1:
                        d[nx]-=1
                        que.append(nx)
                    elif used[x]==1 and d[nx]-d[x]>=2:
                        d[nx]-=1
                        que.append(nx)
    print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
from collections import deque
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N=int(input())
M=N**2
P=tuple(map(int1,input().split()))
d=[0]*M
for i in range(N):
    for j in range(N):
        d[i*N+j]=min(min(i,N-1-i),min(j,N-1-j))
used=[1]*M
ans=0
que=[]
for p in P:
    ans+=d[p]
    used[p]=0
    que.append(p)
    while que:
        x=que.pop()
        for ddx in (-1,1,-N,N):
            nx=x+ddx
            if 0<=nx<M:
                if used[x]==0 and d[nx]-d[x]>=1:
                    d[nx]-=1
                    que.append(nx)
                elif used[x]==1 and d[nx]-d[x]>=2:
                    d[nx]-=1
                    que.append(nx)
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3

n, k = map(int, input().split())
A = list(map(int, input().split()))
a = [0]*n
b = A[0]
per = []
tes = -1

if n >= k:
    for _ in range(k-1):
        b = A[b-1]
    print(b)
    exit()

for _ in range(k*k):
    a[b-1] += 1
    tes += 1
    if 3 in a:
        tes -= len(per)*2
        break
    if 2 in a:
        per.append(b)
    b = A[b-1]

_len = len(per)

ans = (k - tes) % _len

print(per[ans-1])

### FIXED CODE ###

#!/usr/bin/env python3

N, K = map(int, input().split())
A = [int(a) - 1 for a in input().split()]

if K <= N:
    p = 0
    for _ in range(K):
        p = A[p]
    print(p + 1)
    exit()

p = 0
t = [-1] * N
t[0] = 0
for i in range(1, N):
    p = A[p]
    if t[p] != -1:
        break
    t[p] = i

d = i - t[p]
K -= i
K %= d

for i in range(K):
    p = A[p]
print(p + 1)
### BUGGY CODE ###

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

from itertools import accumulate
    
for _ in range(K):
    ans=[0]*(N+1)
    for i,a in enumerate(A):
        ans[max(0,i-a)]+=1
        ans[min(i+a+1,N)]-=1
    A = list(accumulate(ans))[:-1]
print(*A)

### FIXED CODE ###

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

from itertools import accumulate

if N-min(A) <= K:
    print(*[N]*N)
    exit()
    
ans=[0]*(N+1)
for _ in range(K):
    for i,a in enumerate(A):
        ans[max(0,i-a)]+=1
        ans[min(i+a+1,N)]-=1
    A = list(accumulate(ans))[:-1]
    ans=[0]*(N+1)
    if all(i == N for i in A):
        break
print(*A)
### BUGGY CODE ###

import numpy as np
n,k = map(int, input().split())
h = [int(i) for i in input().split()]
dp = [(10**4)*(10**5)]*n
dp[0]=0
for i in range(n-1):
    for j in range(1,k+1):
        if i+j>n-1: break
        dp[i+j] = min(dp[i+j],dp[i]+np.abs(h[i]-h[i+j]))
print(dp[n-1])   

### FIXED CODE ###

n,k = map(int, input().split())
h = [int(i) for i in input().split()]
dp = [(10**4)*(10**5)]*n
dp[0]=0
for i in range(n-1):
    loop = min(k+1,n-i)
    for j in range(1,loop):
        dp[i+j] = min(dp[i+j],dp[i]+abs(h[i]-h[i+j])) 
print(dp[n-1])
### BUGGY CODE ###

import itertools

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

l=set(itertools.combinations(S, 3))

print(len(l))

### FIXED CODE ###

N=int(input())
S=input()
cnt=0
 
for i in range(10):
    a=S.find(str(i))
    if a==-1:
        continue
    for j in range(10):
        b=S.find(str(j),a+1)
        if b==-1:
            continue
        for k in range(10):
            if S.find(str(k),b+1)!=-1:
                cnt+=1
print(cnt)
### BUGGY CODE ###

import re
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
import functools
def v(): return input()
def k(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def X(): return list(input())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
mod = 10**9+7
cnt = 0
ans = 0
inf = float("inf")
al = "abcdefghijklmnopqrstuvwxyz"

s = v()
q = k()
q_list = deque(deque(L()) for i in range(q))

while q_list:
    a = q_list.popleft()
    while a:
        b = a.popleft()
        if b == "1":
            s = s[::-1]
        else:
            c = a.popleft()
            d = a.popleft()
            if c == "1":
                s = d+s
            else:
                s = s+d

print(s)

### FIXED CODE ###

import re
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
import functools
def v(): return input()
def k(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def X(): return list(input())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
mod = 10**9+7
cnt = 0
ans = 0
inf = float("inf")
al = "abcdefghijklmnopqrstuvwxyz"
AL = al.upper()

s = deque(X())
n = k()
normal = 0
for i in range(n):
  a = input().split()
  if int(a[0]) == 1:
    normal ^= 1
  else:
    k = int(a[1]) - 1
    k ^= normal
    if k == 1:
      s.append(a[2])
    else:
      s.appendleft(a[2])
print(''.join(s) if normal == 0 else ''.join(list(s)[::-1]))