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

n,c = map(int,input().split())
X = []
V = []
for i in range(n):
  x,v = map(int,input().split())
  X.append(x)
  V.append(v)
right = []
left = []
count = 0
for i in range(n):
  if i == 0:
    count += (V[i] - X[i])
  else:
    count += (V[i] - (X[i] - X[i - 1]))
  right.append(count)
count = 0
for i in range(n):
  if i == 0:
    count += (V[(i + 1) * (-1)] - (c - X[(i + 1) * (-1)]))
  else:
    count += (V[(i + 1) * (-1)] - ((X[i * (-1)] - X[((i + 1) * (-1))])))
  left.append(count)
ans = max(0,max(right),max(left))
for i in range(n):
  if n - i - 1 > 0:
    ans = max(ans, right[i] - X[i] + max(left[0:n-i-1]))
for i in range(n):
  if n - i - 1 > 0:
    ans = max(ans, left[i] - (c - X[(i+1) * (-1)]) + max(right[0:n-i-1]))
print(ans)

### FIXED CODE ###

n,c = map(int,input().split())
X = []
V = []
for i in range(n):
  x,v = map(int,input().split())
  X.append(x)
  V.append(v)
right = []
right2 = []
left = []
count = 0
left2 = []
for i in range(n):
  if i == 0:
    count += (V[i] - X[i])
    right.append(count)
    right2.append(count)
  else:
    count += (V[i] - (X[i] - X[i - 1]))
    right.append(count)
    right2.append(max(right2[-1],count))

count = 0
for i in range(n):
  if i == 0:
    count += (V[(i + 1) * (-1)] - (c - X[(i + 1) * (-1)]))
    left.append(count)
    left2.append(count)
  else:
    count += (V[(i + 1) * (-1)] - ((X[i * (-1)] - X[((i + 1) * (-1))])))
    left.append(count)
    left2.append(max(left2[-1],count))
ans = max(0,max(right),max(left))
for i in range(n - 1):
  ans = max(ans, right[i] - X[i] + left2[n-i-2])
for i in range(n - 1):
  ans = max(ans, left[i] - (c - X[(i + 1) * (-1)]) + right2[n-i-2])
print(ans)
### BUGGY CODE ###

R,G,B,N = map(int,input().split())
ans = 0
for i in range(0,N//R+1):
  for j in range(0,N//G+1):
    k = N - i*R -j*G
    if k%B == 0 and k>= 0:
      ans += 1
print(ans)

### FIXED CODE ###

R,G,B,N = map(int,input().split())
ans = 0
for i in range(0,N//R+1):
    for j in range(0,(N - R*i)//G+1):
        k = N - R*i - G*j
        if k%B == 0:
            ans += 1
print(ans)
### BUGGY CODE ###

s=str(input())
c=len(s)

for _ in range(10000):
        s=s.replace('01','')
        s=s.replace('10','')
print(c-len(s))

### FIXED CODE ###

s=str(input())

a=s.count('0')
b=s.count('1')
print(min(a,b)*2)
### BUGGY CODE ###

import collections
n, m = map(int, input().split())
linked = collections.defaultdict(set)
for i in range(1, n + 1):
  linked[i].add(i)

for i in range(m):
  a, b = map(int, input().split())
  if linked[a] == linked[b]:continue
  if len(linked[a]) > len(linked[b]):
     tmp = a
     a = b
     b = tmp
  linked[a].update(linked[b])
  tmp =linked[a]

  for t in linked[b]:
    linked[t] = tmp

n_connected = 0
n_group = 0
for s in linked.values():
  if s:
    n_group += 1
    n_connected += len(s)
    s.clear()
print((n - n_connected) + (n_group - 1))


### FIXED CODE ###

import collections
n, m = map(int, input().split())
linked = collections.defaultdict(list)
i2group = dict()

gid = n + 1
def get_root(i):
  if i not in linked:
    return i
  j = get_root(linked[i])
  linked[i] = j
  return j

def get_groups():
  return [get_root(i) for i in range(1, n + 1)]

for i in range(m):
  a, b = map(int, input().split())
  ra, rb = get_root(a), get_root(b)
  if ra == rb: continue
  linked[ra] = gid
  linked[rb] = gid
  gid += 1

g = get_groups()
print(len(set(g)) - 1)
exit()

n_connected = 0
n_group = 0
for s in linked.values():
  s = s[0]
  if s:
    n_group += 1
    n_connected += len(s)
    s.clear()
print((n - n_connected) + (n_group - 1))
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
anslist = []
for i in range(n):
    idx = a.index(i + 1)
    anslist.append(str(idx + 1))
print(" ".join(anslist))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
mydict = {}
for i in range(n):
    mydict[str(i+1)] = a[i]
mydict = sorted(mydict.items(), key= lambda x:x[1])
for j in range(n):
    print(mydict[j][0], end=' ')
### BUGGY CODE ###

import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, Q = lr()
squares = np.zeros(N+2, np.bool)
squares[0] = 1; squares[N+1] = 1
S = np.array(list('-' + sr() + '-'))
TD = [sr().split() for _ in range(Q)]
start = ord('A')
alpha_index = dict()
for x in range(start, start+26):
    y = chr(x)
    alpha_index[y] = np.where(S==y)[0]
for t, d in TD[::-1]:
    index = alpha_index[t]
    if d == 'L':
        i = -1
    else:
        i = 1
    squares[index] = squares[index] | squares[index+i]

answer = N + 2 - np.count_nonzero(squares)
print(answer)
# 49


### FIXED CODE ###

import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, Q = lr()
S = '-' + sr() + '-'
TD = [sr().split() for _ in range(Q)]

L = 1
for t, d in TD[::-1]:
    if d == 'L':
        if L <= N and S[L] == t:
            L += 1
    if d == 'R':
        if L >= 1 and S[L-1] == t:
            L -= 1
R = N
for t, d in TD[::-1]:
    if d == 'L':
        if R <= N and S[R+1] == t:
            R += 1
    if d == 'R':
        if R >= 1 and S[R] == t:
            R -= 1

answer = max(0, R - L + 1)
print(answer)
# 34
### BUGGY CODE ###

h, w = map(int, raw_input().split())
S = [[c for c in raw_input()] for i in range(h)]
Gh = [[0]*w for i in range(h)]
Gw = [[0]*w for i in range(h)]

for i in range(h):
    ps = 0
    leftObstacle = -1
    s = S[i]
    for j in range(w+1):
        if w == j or s[j] == "#":
            for k in range(leftObstacle + 1, j):
                Gh[i][k] = ps
            ps = 0
            leftObstacle = j
        else:
            ps += 1

for j in range(w):
    ps = 0
    upObstacle = -1
    for i in range(h+1):
        if i == h or S[i][j] == "#":
            for k in range(upObstacle+1, i):
                Gw[k][j] = ps
            ps = 0
            upObstacle = i
        else:
            ps += 1
maxLight = 0
for i in range(h):
    for j in range(w):
        maxLight = max(maxLight, Gh[i][j] + Gw[i][j]-1)
print maxLight

### FIXED CODE ###

h, w = map(int, raw_input().split())
S = [[0 if c == "." else 1 for c in raw_input()] for i in range(h)]
L = [[0]*w for i in range(h)]
R = [[0]*w for i in range(h)]
U = [[0]*w for i in range(h)]
D = [[0]*w for i in range(h)]

for i in xrange(h):
    ps = 0
    for j in xrange(w):
        if S[i][j] == 1:
            ps = 0
        else:
            ps += 1
            L[i][j] = ps

for j in xrange(w):
    ps = 0
    for i in xrange(h):
        if S[i][j] == 1:
            ps = 0
        else:
            ps += 1
            U[i][j] = ps

for i in xrange(h-1, -1, -1):
    ps = 0
    for j in xrange(w-1, -1, -1):
        if S[i][j] == 1:
            ps = 0
        else:
            ps += 1
            R[i][j] = ps
for j in xrange(w-1, -1, -1):
    ps = 0
    for i in xrange(h-1, -1, -1):
        if S[i][j] == 1:
            ps = 0
        else:
            ps += 1
            D[i][j] = ps
maxLight = 0
for i in xrange(h):
    for j in xrange(w):
        maxLight = max(maxLight, L[i][j] + R[i][j] + U[i][j] + D[i][j] - 3)
print maxLight
### BUGGY CODE ###

# coding: utf-8
# Your code here!
N,W=map(int,input().split())

l=[-1]*(W+1)
l[0]=0
dp=l[:]

for i in range(N):
    w,v=map(int,input().split())
    for index,item in enumerate(l):
        if item!=-1 and W>=index+w:
            dp[index+w]=max(item+v,l[index+w])
    l=dp[:]
print(max(l))


### FIXED CODE ###

# coding: utf-8
# Your code here!
N,W=map(int,input().split())

l=[-1]*(W+1)
l[0]=0
dp=l[:]

for i in range(N):
    w,v=map(int,input().split())
    for index,item in enumerate(l):
        if item!=-1 and W>=index+w:
            dp[index+w]=max(item+v,l[index+w])
    l=dp[:]
print(max(l))
### BUGGY CODE ###

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

for i in range(1, n + 1):
    if q - a.count(i) >= k:
        print("No")
    else:
        print("Yes")

### FIXED CODE ###

n, k, q = map(int, input().split())
a = [int(input()) for _ in range(q)]
p = [0] * n

for i in a:
    p[i - 1] += 1

for i in p:
    if q - i >= k:
        print("No")
    else:
        print("Yes")
### BUGGY CODE ###

s=input()
ans=0
for  i in range(10**5):
  if s.count("BW")==0:
    print(ans)
    exit()
  ans+=s.count("BW")
  s=s.replace("BW","WB")



### FIXED CODE ###

s=input()
t=list(s).count("W")
A=[i for i,x in enumerate (list(s)) if x=="W"]
print(int(sum(A)-t*(t-1)/2))
### BUGGY CODE ###

N, Q = map(int,input().split())
S = input()
LRlist = []
for i in range(Q):
    LRlist.append(list(map(int,input().split())))
indexlist = []
for i in range(len(S)-1):
    if S[i] == 'A':
        if S[i+1] == 'C':
            indexlist.append(i)
for LR in LRlist:
    L = LR[0]
    R = LR[1]
    answer = 0
    for i in indexlist:
        if L - 1 <= i <= R - 2:
            answer += 1
        elif R - 2 < i:
            break
    print(answer)

### FIXED CODE ###

N, Q = map(int,input().split())
S = input()
LRlist = []
for i in range(Q):
    LRlist.append(list(map(int,input().split())))
t = [0] * (N + 1)
for i in range(N):
    t[i+1] = t[i] + (1 if S[i:i+2] == 'AC' else 0) #t[i]=i文字目までのACのAの数：累積和
for LR in LRlist:
     L = LR[0]
     R = LR[1]
     print(t[R-1] - t[L-1])
### BUGGY CODE ###

S = input()
Q = int(input())
st = S
for i in range(1, Q+1):
    query = input()
    if len(query) == 1:
        st = st[::-1]
    else:
        n, F, C = query.split()
        if F == '1':
            st = C + st
        else:
            st = st + C
print(st)


### FIXED CODE ###

from collections import deque
S = list(input())
Q = int(input())

d = deque()
d.extend(S)
cnt = 0
for i in range(1, Q+1):
    query = input()
    if len(query) == 1:
        cnt += 1
    else:
        n, F, C = query.split()
        if cnt % 2 == 0:  # 反転cntが偶数,F=1で末尾
            if F == '1':
                d.appendleft(C)
            else:
                d.append(C)
        else:  # 反転cntが偶数,F=1で先頭
            if F == '1':
                d.append(C)
            else:
                d.appendleft(C)

if cnt % 2 == 1:  # cnt奇数の場合、反転
    d.reverse()
else:
    pass

l = list(d)
S = ''.join(l)
print(S)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)
t=input()
tl=list(t)
tln=len(t)
x=0
x=t.find("?")
while x != -1:
    if x == tln-1:
        tl[x]="D"
        t="".join(tl)
        break
    elif x==0:
      if tl[x+1]=="?":
        tl[x]="P"
        tl[x+1]="D"
      else:
        tl[x]="D"
    elif tl[x-1]=="P":
        tl[x]="D"
    elif tl[x+1]=="?":
        tl[x]="P"
        tl[x+1]="D"
    elif tl[x+1]=="D":
        tl[x]="P"
    else:
        tl[x]="D"
    t="".join(tl)
    x=t.find("?")
print(t)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
t=input()
tl=list(t)
tln=len(t)
x=0
for x in range(tln):
    if tl[x] == "?":
        if x == tln-1:
            tl[x]="D"
            break
        elif x==0:
            if tl[x+1]=="?":
                tl[x]="P"
                tl[x+1]="D"
            else:
                tl[x]="D"
        elif tl[x-1]=="P":
            tl[x]="D"
        elif tl[x+1]=="?":
            tl[x]="P"
            tl[x+1]="D"
        elif tl[x+1]=="D":
            tl[x]="P"
        else:
            tl[x]="D"
t="".join(tl)
print(t)
### BUGGY CODE ###

import sys


input = sys.stdin.readline
n, p = map(int, input().split())
if n == 1:
    ans = p
else:
    ans = 1
    for i in range(1, 10**6+1):
        if i**n > p:
            break
        elif p % i**n == 0:
            ans = i
print(ans)


### FIXED CODE ###

import sys


input = sys.stdin.readline
n, p = map(int, input().split())
if n == 1:
    ans = p
elif n > 10**6:
    ans = 1
else:
    ans = 1
    for i in range(2, 10**6+1):
        check = i**n
        if check > p:
            break
        elif p % check == 0:
            ans = i
print(ans)
### BUGGY CODE ###

a = list(input())
a.reverse()
add = 0
ans = [1] + [0] * 2018
ans_int = 0

for i in range(len(a)):
    add = (add + int(a[i]) * 10 ** i) %2019
    if ans[add] == 1:
        ans_int += 1
        continue
    else:
        ans[add] = 1


print(ans_int)

### FIXED CODE ###

a = input()[::-1]
add = 0
ans = [1] + [0] * 2018
ans_int = 0
d = 1

for i in range(len(a)):
    add = (add + int(a[i]) * d) % 2019
    d = (10 * d) %2019
    ans[add] += 1

for i in range(len(ans)):
    a =((ans[i] - 1) * ans[i]) /2
    ans_int += a

print(int(ans_int))
### BUGGY CODE ###

INF = 10 ** 18


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

dp = [[INF] * (H + 1) for _ in range(N + 1)]
dp[0][0] = 0
for i in range(N):
    for j in range(H + 1):
        if j < AB[i][0]:
            dp[i + 1][j] = min(dp[i][j], dp[i + 1][0] + AB[i][1])
        else:
            dp[i + 1][j] = min(dp[i][j], dp[i + 1][j - AB[i][0]] + AB[i][1])
    
print (dp[N][H])

# for d in dp:
#     print (d)

### FIXED CODE ###

INF = 10 ** 18


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

dp = [[INF] * (H + 1) for _ in range(N + 1)]
dp[0][0] = 0
for i in range(N):
    for j in range(H + 1):
        if j < AB[i][0]:
            dp[i + 1][j] = min(dp[i][j], dp[i + 1][0] + AB[i][1])
        else:
            dp[i + 1][j] = min(dp[i][j], dp[i + 1][j - AB[i][0]] + AB[i][1])
    
print (dp[N][H])

# for d in dp:
#     print (d)
### BUGGY CODE ###

#%%
N, M = map(int, input().split())

a = [0] * M
b = [0] * M
c = [[] for _ in range(M)]
for i in range(M):
    a[i], b[i] = map(int, input().split())
    c[i] = list(map(int, input().split()))

inf = (10**5) * 13
cost = [inf] * (2**N)
cost[0] = 0

movement = []
for i in range(M):
    move = 0
    for j in range(len(c[i])):
        move += 2 ** (c[i][j]-1)
    movement.append(move)

for i in range(2**N):
    for j in range(M):
        move2 = movement[j]
        cost[i|move2] = min(cost[i|move2], cost[i]+a[j])

if cost[2**N-1] == inf:
    print(-1)
else:
    print(cost[2**N-1])

### FIXED CODE ###

#%%
N, M = map(int, input().split())

a = [0] * M
b = [0] * M
c = [[] for _ in range(M)]
for i in range(M):
    a[i], b[i] = map(int, input().split())
    c[i] = list(map(int, input().split()))

inf = float('inf') 
cost = [inf] * (2**N)
cost[0] = 0

movement = []
for i in range(M):
    move = 0
    for j in range(len(c[i])):
        move += 2 ** (c[i][j]-1)
    movement.append(move)

for i in range(2**N):
    for j in range(M):
        move2 = movement[j] 
        if cost[i|move2] > cost[i]+a[j]:
            cost[i|move2] = cost[i]+a[j]

if cost[2**N-1] == inf:
    print(-1)
else:
    print(cost[2**N-1])
### BUGGY CODE ###

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

for i in range(Q):
    x = input().split()
    
    if x[0] == "1":
        S = S[::-1]
    else:
        if x[1] == "1":
            S = x[2] + S
        else:
            S = S + x[2]
            
print(S)

### FIXED CODE ###

from collections import deque
S = list(input())
Q = int(input())

day = deque(S)

r = False
for i in range(Q):
    x = input().split()
    
    if x[0] == "1":
        r = not r
        
    else:
        if x[1] == "1":
            if r == False :
                day.appendleft(x[2])
            else:
                day.append(x[2])
        else:
            if r == True :
                day.appendleft(x[2])
            else:
                day.append(x[2])
                
day = list(day)
        
if r:
    print("".join(day[::-1]))
else:
    print("".join(day))
### BUGGY CODE ###

N = input()
list = map(int, input().split())
count = 0
while all(a % 2 == 0 for a in list):
  list = [a/2 for a in list]
  count += 1
print(count)

### FIXED CODE ###

input()
A = list(map(int, input().split()))
count = 0
while all(a % 2 == 0 for a in A):
    A = [a/2 for a in A]
    count += 1
print(count)
### BUGGY CODE ###

N=int(input())
A=[int(input()) for i in range(N)]
i=0
while i < N:
    cont=A[i]
    del A[i]
    print(max(A))
    A.insert(i,cont)
    i += 1

### FIXED CODE ###

N=int(input())
A=[int(input()) for i in range(N)]
B=sorted(A,reverse=True)
maxA=B[0]
secondA=B[1]
i=0
for i in range(N):
    if A[i] == maxA:
        print(secondA)
    else:
        print(maxA)
    i += 1
### BUGGY CODE ###

import math
from functools import reduce


def gcd(*numbers):
    return reduce(math.gcd, numbers)


k = int(input())
cnt = 0
for a in range(1, k+1):
    for b in range(1, k+1):
        for c in range(1, k+1):
            cnt += gcd(a, b, c)

print(cnt)


### FIXED CODE ###

import collections
import math
# math.gcd(a,b)
k = int(input())
cnts = collections.defaultdict(int)
for i in range(1, k+1):
    for j in range(1, k+1):
        cnts[math.gcd(i,j)] += 1
ans = 0
for i in range(1, k+1):
    for key in cnts.keys():
        ans += math.gcd(i, key)*cnts[key]
print(ans)
### BUGGY CODE ###


import sys
sys.setrecursionlimit(500000)
N, Q = map(int, input().split())
E = [[] for _ in range(N+1)]
for _ in range(N-1):
    a, b = map(int, input().split())
    E[a].append(b)
    E[b].append(a)
C = [0] * (N+1)
for _ in range(Q):
    p, x = map(int, input().split())
    C[p] += x

Ans = [0] * (N+1)
def dfs(v, p, a):
    global ans
    a += C[v]
    Ans[v] = a
    for u in E[v]:
        if u!=p:
            dfs(u, v, a)
dfs(1, 0, 0)
print(" ".join(map(str, Ans[1:])))


### FIXED CODE ###

import sys
input = sys.stdin.readline

import sys
sys.setrecursionlimit(500000)
N, Q = map(int, input().split())
E = [[] for _ in range(N+1)]
for _ in range(N-1):
    a, b = map(int, input().split())
    E[a].append(b)
    E[b].append(a)
C = [0] * (N+1)
for _ in range(Q):
    p, x = map(int, input().split())
    C[p] += x
Ans = [0] * (N+1)
def dfs(v, p, a):
    a += C[v]
    Ans[v] = a
    for u in E[v]:
        if u!=p:
            dfs(u, v, a)
dfs(1, 0, 0)
print(" ".join(map(str, Ans[1:])))
### BUGGY CODE ###

import sys
# N,M = [int(n) for n in input().split()]
# S = str(input())
# T = str(input())

S = str(input())
K = int(input())
numplace = 0

for i in range(len(S)):
    if (S[i] == "1"):
        numplace+=1
    else:
        numplace+= int(S[i])**5000000000000000
    if(numplace>=K):
        print(S[i])
        sys.exit()


### FIXED CODE ###

import sys
# N,M = [int(n) for n in input().split()]
# S = str(input())
# T = str(input())

S = str(input())
K = int(input())
numplace = 0

for i in range(len(S)):
    if (S[i] == "1"):
        numplace+=1
    else:
        numplace+= 5000000000000000**int(S[i])
    if(numplace>=K):
        print(S[i])
        sys.exit()
### BUGGY CODE ###

n=int(input())
a=[]
for i in range(n):
    a.append(int(input())-1)

#TLEチーンコ
i=0
j=0
b=[]
while True:
    if i==1:
        print(j)
        break
    elif i in b:
        print(-1)
        break
    else:
        b.append(i)
        i=a[i]
        j+=1


### FIXED CODE ###

n=int(input())
a=[]
for i in range(n):
    a.append(int(input())-1)
'''
#TLEチーンコ
i=0
j=0
b=[]
while True:
    j+=1
    if a[i]==1:
        print(j)
        break
    elif a[i] in b:
        print(-1)
        break
    else:
        b.append(a[i])
        i=a[i]
'''
i=0
j=0
while True:
    j+=1
    if a[i]==1:
        print(j)
        break
    elif j==n:
        print(-1)
        break
    else:
        i=a[i]
### BUGGY CODE ###

s = list(input())
count = 0
for i in range(len(s)):
    if s[-i-1] == 'A':
        tmp = -i-1
        while tmp <= -3 and s[tmp+1] == 'B' and s[tmp+2] == 'C':
            s[tmp] = 'B'
            s[tmp+1] = 'C'
            s[tmp+2] = 'A'
            count += 1
            tmp += 2
print(count)

### FIXED CODE ###

inp = input()
changed_input = inp.replace('BC', 'D')
A_count = 0
total_ans = 0
for st in changed_input:
    if st == 'A':
        A_count += 1
    elif st == 'D':
        total_ans += A_count
    else:
        A_count = 0
print(total_ans)
### BUGGY CODE ###

# D - Not Divisible
n = int(input())
a = list(map(int, input().split()))
dic = dict()

for ai in a:
	dic.setdefault(ai, 0)
	dic[ai] += 1

multiples = set()
upper = 10 ** 6

for k in dic.keys():
  i = 2
  
  while True:
    if k * i <= upper:
      multiples.add(k * i)
      i += 1
    else:
      break

ans = 0

for k, v in dic.items():
  if v == 1:
    if not k in multiples:
      ans += 1

print(ans)
  

### FIXED CODE ###

import sys
input = sys.stdin.readline

# D - Not Divisible
n = int(input())
a = list(map(int, input().split()))
dic = dict()

for ai in a:
	dic.setdefault(ai, 0)
	dic[ai] += 1

multiples = set()
upper = 10 ** 6

for k in dic.keys():
  i = 2
  
  while True:
    if k * i <= upper:
      multiples.add(k * i)
      i += 1
    else:
      break

ans = 0

for k, v in dic.items():
  if v == 1:
    if not k in multiples:
      ans += 1

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

n = int(input())
p = enumerate(map(int, input().split()))
next(p)
a = list(range(1, n + 1))
b = list(range(n, 0, -1))
for c, i in p:
    i -= 1
    a[i:] = [x + c for x in a[i:]]
    b[:i + 1] = [x + c for x in b[:i + 1]]
print(*a)
print(*b)


### FIXED CODE ###

# numpyが使えると聞いて
import numpy as np

n = int(input())
p = enumerate(map(int, input().split()))
next(p)
a = np.arange(1, n + 1)
b = np.arange(n, 0, -1)
for c, i in p:
    i -= 1
    a[i:] += c
    b[:i + 1] += c
print(*a)
print(*b)
### BUGGY CODE ###

import sys
from collections import defaultdict

n, m = map(int, sys.stdin.readline().strip().split(" ", 2))
count_city = defaultdict(list)

for line in sys.stdin:
    p, y = map(int, line.strip().split(" ", 2))
    count_city[p].append(y)


for p, yl in count_city.iteritems():
    count_city[p] = sorted(yl)

    sys.stdin.seek(0)
    n, m = map(int, sys.stdin.readline().strip().split(" ", 2))

for line in sys.stdin:
    p, y = map(int, line.strip().split(" ", 2))
    print("{:0=6}{:0=6}".format(p, count_city[p].index(y) + 1))


### FIXED CODE ###

import sys
from collections import defaultdict

n, m = map(int, sys.stdin.readline().strip().split(" ", 2))
list_city = defaultdict(list)

for line in sys.stdin:
    p, y = map(int, line.strip().split(" ", 2))
    list_city[p].append(y)

count_city = {}
for p, yl in list_city.iteritems():
    count_city[p] = {y:i+1 for i, y in enumerate(sorted(yl))}

    
sys.stdin.seek(0)
n, m = map(int, sys.stdin.readline().strip().split(" ", 2))

for line in sys.stdin:
    p, y = map(int, line.strip().split(" ", 2))
    print("{:0=6}{:0=6}".format(p, count_city[p][y]))
### BUGGY CODE ###

import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N = int(sys.stdin.readline())
X = list(map(int, sys.stdin.readline().split()))
L = int(sys.stdin.readline())
Q = int(sys.stdin.readline())
AB = [list(map(int, sys.stdin.readline().split())) for _ in range(Q)]

N += 2
X = [X[0]] + X + [X[-1]]
X = np.array(X, dtype=int)
# dp[d][i]: i番のホテルから(2^d)日で何個右までいけるか
dp = np.zeros((N.bit_length() + 1, N), dtype=int)
dp[0] = np.searchsorted(X, X + L, side='right') - np.arange(N) - 1
for d in range(1, N.bit_length() + 1):
    dp[d] = dp[d - 1] + dp[d - 1][np.arange(N) + dp[d - 1]]


def solve(l, r):
    ret = 0
    d = IINF
    while l < r:
        d = max(0, np.searchsorted(dp[:d + 1, l], r - l) - 1)
        ret += 2 ** d
        l += dp[d, l]
    return ret


for a, b in AB:
    r = solve(min(a, b), max(a, b))
    print(r)


### FIXED CODE ###

import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N = int(sys.stdin.readline())
X = list(map(int, sys.stdin.readline().split()))
L = int(sys.stdin.readline())
Q = int(sys.stdin.readline())
AB = [list(map(int, sys.stdin.readline().split())) for _ in range(Q)]

N += 2
X = [X[0]] + X + [X[-1]]
X = np.array(X, dtype=int)
# dp[d][i]: i番のホテルから(2^d)日で何個右までいけるか
dp = np.zeros((N.bit_length() + 1, N), dtype=int)
dp[0] = np.searchsorted(X, X + L, side="right") - 1
for d in range(1, N.bit_length() + 1):
    dp[d] = dp[d - 1][dp[d - 1]]
dp = dp.tolist()


def solve(l, r):
    ret = 0
    d = len(dp) - 1
    while l + 1 < r:
        while d > 0 and dp[d][l] >= r:
            d -= 1
        ret += 1 << d
        l = dp[d][l]
    if l < r:
        ret += 1
    return ret


ans = []
for a, b in AB:
    ans.append(solve(min(a, b), max(a, b)))
print(*ans, sep='\n')