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

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
a.sort()
b.sort()
def isOK(idx: int, key: int, lis: list) -> bool:
    if lis[idx] >= key:
        return True
    else:
        return False

def binary_search(key: int, lis: list) -> int:
    left = -1
    right = len(lis)
    while(right - left > 1):
        mid = left + (right - left) // 2
        if isOK(mid, key, lis):
            right = mid
        else:
            left = mid
    return left
ans = 0
for i in c:
    k = binary_search(i, b)
    for j in range(k + 1):
        l = binary_search(b[j], a)
        ans += l + 1
print(ans)


### FIXED CODE ###

import bisect

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
a.sort()
c.sort()

ans = 0
for i in b:
    k = bisect.bisect_left(a, i)
    l = bisect.bisect_right(c, i)
    ans += k * (n - l)
print(ans)
### BUGGY CODE ###

n = int(input())
a = [int(i) for i in input().split()]
ans = []
a_sum = sum(a)
for i in range(n-1):
    ans.append(abs(-a_sum+2*sum(a[:i+1])))
print(min(ans))

### FIXED CODE ###

import numpy
n = int(input())
a = [int(i) for i in input().split()]
a_sum = numpy.cumsum(a)
ans = []
for i in range(n-1):
    ans.append(abs(-a_sum[-1]+2*a_sum[i]))
print(min(ans))
### BUGGY CODE ###

import sys
import numpy as np
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix

input = sys.stdin.buffer.readline

N, M, S, T = map(int, input().split())
S -= 1
T -= 1
UVAB = np.array([tuple(map(int, input().split())) for _ in range(M)])
UVAB[:, :2] -= 1

yen_matrix = csr_matrix((UVAB[:, 2], (UVAB[:, 0], UVAB[:, 1])), shape=(N, N))
yen_path = dijkstra(yen_matrix, indices=S, directed=False).astype(int)

snuke_matrix = csr_matrix((UVAB[:, 3], (UVAB[:, 0], UVAB[:, 1])), shape=(N, N))
snuke_path = dijkstra(snuke_matrix, indices=T, directed=False).astype(int)

path = yen_path + snuke_path
path_acc = np.minimum.accumulate(path[::-1])[::-1]
print(*(10 ** 15 - path_acc), sep='\n')


### FIXED CODE ###

import sys
import networkx as nx

input = sys.stdin.buffer.readline

MAX = 10 ** 15
N, M, S, T = map(int, input().split())

G = nx.Graph()
G.add_nodes_from(range(1, N + 1))
for _ in range(M):
    u, v, a, b = map(int, input().split())
    G.add_edge(u, v, yen=a, snuuk=b)

yen_path = nx.single_source_dijkstra_path_length(G, S, weight='yen')
snuuk_path = nx.single_source_dijkstra_path_length(G, T, weight='snuuk')

ans = [MAX] * (N + 1)
for i in range(N, 0, -1):
    ans[i - 1] = min(ans[i], yen_path[i] + snuuk_path[i])
for x in ans[:N]:
    print(MAX - x)
### BUGGY CODE ###

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

for i in range(N):
    P[i] -= 1

ans = -1 * 2 ** 30

if K <= N:
    for i in range(N):
        pos = i
        score = 0
        for j in range(K):
            score += C[pos]
            pos = P[pos]
            ans = max(ans, score)
    print(ans)
    exit(0)

for i in range(N):
    pos = i
    k = 0
    score = 0

    for j in range(N):
        score += C[pos]
        pos = P[pos]
        ans = max(ans, score)
        k += 1
        if pos == i:
            break

    score *= K // k
    ans = max(ans, score)
    for j in range(K % k):
        score += C[pos]
        pos = P[pos]
        ans = max(ans, score)
print(ans)

### FIXED CODE ###

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

for i in range(N):
    P[i] -= 1

ans = -1 * 2 ** 30

if K <= N:
    for i in range(N):
        pos = i
        score = 0
        for j in range(K):
            score += C[pos]
            pos = P[pos]
            ans = max(ans, score)
    print(ans)
    exit(0)

for i in range(N):
    pos = i
    k = 0
    score = 0

    for j in range(N):
        score += C[pos]
        pos = P[pos]
        ans = max(ans, score)
        k += 1
        if pos == i:
            break

    score *= (K // k) - 1
    ans = max(ans, score)
    for j in range(k + (K % k)):
        score += C[pos]
        pos = P[pos]
        ans = max(ans, score)
print(ans)
### BUGGY CODE ###

import sys
from collections import deque
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
n,q=map(int,input().split())
ki=[[] for _ in range(n)]
ans=[0]*n

def dfs(numQ,parent):
    for child in ki[numQ]:
        if child!=parent:
            ans[child]+=ans[numQ]
            dfs(child,numQ)

for i in range(n-1):
    a,b=map(int,input().split())
    ki[a-1].append(b-1)
    ki[b-1].append(a-1)

for i in range(q):
    p,x=map(int,input().split())
    ans[p-1]+=x

dfs(0,-1)
print(*ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
n,q=map(int,input().split())
ki=[[] for _ in range(n)]
ans=[0]*n

def dfs(numQ,parent):
    for child in ki[numQ]:
        if child==parent:
            continue
        ans[child]+=ans[numQ]
        dfs(child,numQ)

for i in range(n-1):
    a,b=map(int,input().split())
    ki[a-1].append(b-1)
    ki[b-1].append(a-1)

for i in range(q):
    p,x=map(int,input().split())
    ans[p-1]+=x

dfs(0,-1)
print(*ans)
### BUGGY CODE ###

check=dict()
N,b,d=0,[],0
#ttfは235、chaはabc
inf=10**13
def dfs_sub(n,ttf,cha):
    global check,d
    check[0]=min(check[n]+n*d,check.get(0,inf))
    if n//ttf==0:
        check[n//ttf]=min(check.get(n//ttf,inf),check[n]+(n%ttf)*d)
    else:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d+cha:
                check[n//ttf]=check[n]+(n%ttf)*d+cha
                dfs(n//ttf)
        else:
            check[n//ttf]=check[n]+(n%ttf)*d+cha
            dfs(n//ttf)
    if 1+n//ttf in check:
        if check[1+n//ttf]>check[n]+(ttf-n%ttf)*d+cha:
            check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
            dfs(1+n//ttf)
    else:
        check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
        dfs(1+n//ttf)


def dfs(n):
    global b,check,d
    for i,j in zip([2,3,5],b):
        dfs_sub(n,i,j)

t=int(input())
for i in range(t):
    N,*b,d=map(int,input().split())
    check={N:0}
    dfs(N)
    print(check[0])

### FIXED CODE ###

import sys
check=dict()
N,a,b,c,d=0,0,0,0,0
#ttfは235、chaはabc
def dfs_sub(n,ttf,cha):
    global check,d
    if 0 in check:
        check[0]=min(check[n]+n*d,check[0])
    else:
        check[0]=check[n]+n*d
    if n//ttf==0:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d:
                check[n//ttf]=check[n]+(n%ttf)*d
        else:
            check[n//ttf]=check[n]+(n%ttf)*d
    else:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d+cha:
                check[n//ttf]=check[n]+(n%ttf)*d+cha
                dfs(n//ttf)
        else:
            check[n//ttf]=check[n]+(n%ttf)*d+cha
            dfs(n//ttf)
    if 1+n//ttf in check:
        if check[1+n//ttf]>check[n]+(ttf-n%ttf)*d+cha:
            check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
            dfs(1+n//ttf)
    else:
        check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
        dfs(1+n//ttf)


def dfs(n):
    global check,a,b,c,d
    dfs_sub(n,2,a)
    dfs_sub(n,3,b)
    dfs_sub(n,5,c)

t=int(input())
ans=[0]*t
for i in range(t):
    N,a,b,c,d=map(int,input().split())
    check={N:0}
    dfs(N)
    ans[i]=check[0]
for i in range(t):
    print(ans[i])
### BUGGY CODE ###

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

for i in range(1,n+1):
	ans = a.count(i)
	
	print(ans)

### FIXED CODE ###

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

from collections import Counter

c = Counter(a)

for i in range(1,n+1):
	print(c[i])
### BUGGY CODE ###

N, K  = map(int, input().split())
L = [list(map(int, input().split())) for _ in range(K)]
S = set()
for l in L:
  S = S|set([i for i in range(l[0], l[1]+1)])
DP = [0]*N
DP[0]=1
for i in range(1, N):
  for j in S:
    if i>=j:
      DP[i] += DP[i-j]
      DP[i] %= 998244353
    else:
      break
  continue
print(DP[-1])

### FIXED CODE ###

N, K = map(int, input().split())
L = []
for _ in range(K):
  a, b = map(int, input().split())
  L.append((a,b))
L.sort()
DP_1 = [0]*N
DP_2 = [0]*(N+1)
DP_1[0], DP_2[1] = 1, 1
mod = 998244353
for i in range(1, N):
  for l in L:
    if l[0]>i:
      break
    elif l[1]>i:
      DP_1[i] += DP_2[i-l[0]+1]
      DP_1[i] %= mod
    elif l[1]<=i:
      DP_1[i] += DP_2[i-l[0]+1]-DP_2[i-l[1]]
      DP_1[i] %= mod
  DP_2[i+1] = DP_2[i] + DP_1[i]
  DP_2[i+1] %= mod
print(DP_1[-1]%mod)
### BUGGY CODE ###

import sys
from collections import defaultdict
from heapq import *

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    to = defaultdict(list)
    n, m = map(int, input().split())
    for _ in range(m):
        l, r, c = map(int, input().split())
        l, r = l - 1, r - 1
        to[l].append([r, c])
    costs = [-1] * n
    hp = []
    heappush(hp, [0, 0])
    while hp:
        #print(hp)
        c, u = heappop(hp)
        if u == n - 1:
            print(c)
            #print(costs)
            exit()
        if costs[u] != -1: continue
        costs[u] = c
        for v, dc in to[u]:
            if costs[v] != -1: continue
            heappush(hp, [c + dc, v])
            for w in range(v - 1, u, -1):
                if costs[w] != -1: break
                heappush(hp, [c + dc, w])

    print(-1)

main()


### FIXED CODE ###

import sys
from collections import defaultdict
from heapq import *

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    to = defaultdict(list)
    n, m = map(int, input().split())
    for _ in range(m):
        l, r, c = map(int, input().split())
        l, r = l - 1, r - 1
        to[l].append([r, c])
    costs = [-1] * n
    hp = []
    heappush(hp, [0, 0])
    while hp:
        # print(hp)
        c, u = heappop(hp)
        if u == n - 1:
            print(c)
            # print(costs)
            exit()
        if costs[u] != -1: continue
        costs[u] = c
        for v, dc in to[u]:
            if costs[v] != -1: continue
            heappush(hp, [c + dc, v])
        for v in range(u - 1, 0, -1):
            if costs[v] != -1: break
            heappush(hp, [c, v])
    print(-1)

main()
### BUGGY CODE ###

import copy
n = int(input())
# 隣接リスト
graph = {i+1000*j:set() for i in range(n) for j in range(i+1,n)}
# 入次数を管理
st = {i+1000*j:0 for i in range(n) for j in range(i+1,n)}

#たどったかどうかチェック
check = {i+1000*j:True for i in range(n) for j in range(i+1,n)}

# 入次数が0の頂点の集まり
szero = []

#ソートされたやつたち
ans = []

for i in range(n):
    ls = list(map(int,input().split()))
    f = -1
    for p in ls:
        v = min(i,p-1) + 1000*(max(i,p-1))
        if f != -1:
            graph[f].add(v)
            st[v] += 1
        f = v

for v in st.keys():
    if st[v] == 0:szero.append(v)
count = 0
next_szero = []
while True:
    count += 1
    for i in szero:
        ans.append(i)
        for v in graph[i]:
            #if check[v]:check[v] = False
            #else:continue
            st[v] -= 1
            if st[v] == 0:
                next_szero.append(v)
    if len(next_szero) == 0:break
    szero = copy.deepcopy(next_szero)
    next_szero = []

if len(ans) != n*(n-1)//2:
    print(-1)
else:
    print(count)

### FIXED CODE ###

n = int(input())
# 隣接リスト
graph = {i+1000*j:[] for i in range(n) for j in range(i+1,n)}
# 入次数を管理
st = {i+1000*j:0 for i in range(n) for j in range(i+1,n)}


# 入次数が0の頂点の集まり
szero = []

#ソートされたやつたち
ans = []

for i in range(n):
    ls = list(map(int,input().split()))
    f = -1
    for p in ls:
        v = min(i,p-1) + 1000*(max(i,p-1))
        if f != -1:
            graph[f].append(v)
            st[v] += 1
        f = v

for v in st.keys():
    if st[v] == 0:szero.append(v)
count = 0
next_szero = []
while True:
    count += 1
    for i in szero:
        ans.append(i)
        for v in graph[i]:
            st[v] -= 1
            if st[v] == 0:
                next_szero.append(v)
    if len(next_szero) == 0:break
    szero = next_szero
    next_szero = []

if len(ans) != n*(n-1)//2:
    print(-1)
else:
    print(count)
### BUGGY CODE ###

import sys

input = sys.stdin.readline
import fractions


def main():
    N = int(input())
    A = [int(x) for x in input().split()]
    MOD = 10 ** 9 + 7

    x = 1
    for a in A:
        x = (a * x) // fractions.gcd(a, x)


    ans = 0
    for a in A:
        ans += x // a
        ans %= MOD

    print(ans % MOD)



    
    

if __name__ == '__main__':
    main()



### FIXED CODE ###

import sys

input = sys.stdin.readline
import fractions



def main():
    N = int(input())
    A = tuple([int(x) for x in input().split()])
    MOD = 10 ** 9 + 7

    x = 1
    for a in A:
        x = (a * x) // fractions.gcd(a, x)

    ans = 0
    for a in A:
        ans += x // a

    print(ans % MOD)



    
    

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

N = int(input())

for i in range(1,1000000):
    for j in range(1,i+1):
        if (i*j) == N:
            break
    else:
        continue
    break

ans = i + j - 2

print(ans)

### FIXED CODE ###

N = int(input())

divisors = []
for i in range(1, int(N**0.5)+1):
    if N % i == 0:
        divisors.append(i+N//i)

print(min(divisors)-2)
### BUGGY CODE ###

S = list(input())
original = len(S)
flag = True
while flag:
    flag = False
    i = 0
    while i+1 < len(S):
        if S[i] != S[i+1]:
            flag = True
            del S[i:i+2]
        i += 1
print(original-len(S))


### FIXED CODE ###

S = list(input())
cnt_1 = S.count("1")
cnt_0 = S.count("0")
print(2*min(cnt_1,cnt_0))
### BUGGY CODE ###

import numpy as np
import heapq

H, W = map(int, input().split())
sy, sx = map(lambda x: int(x) - 1, input().split())
ty, tx = map(lambda x: int(x) - 1, input().split())
s, t = sy * W + sx, ty * W + tx
graph = [input() for _ in range(H)]

INF = 1 << 30
dist = np.full(H * W, INF, np.int64)
que = []

def push(v, d):
    if(dist[v] <= d):
        return
    dist[v] = d
    heapq.heappush(que, (d, v))

def move(ny, nx, d):
    if ny < 0 or ny >= H or nx < 0 or nx >= W:
        return
    if graph[ny][nx] == '.':
        push(ny * W + nx, d)

push(s, 0)

while que:
    d, v = heapq.heappop(que)
    if d > dist[v]:
        continue
    if v == t:
        break
    y, x = divmod(v, W)
    for dy in range(-2, 3):
        for dx in range(-2, 3):
            move(y + dy, x + dx, d + (abs(dy) + abs(dx) > 1))

if dist[t] == INF:
    print(-1)
else:
    print(dist[t])


### FIXED CODE ###

import heapq

H, W = map(int, input().split())
sy, sx = map(lambda x: int(x) - 1, input().split())
ty, tx = map(lambda x: int(x) - 1, input().split())
s, t = sy * W + sx, ty * W + tx
graph = [input() for _ in range(H)]

INF = 1 << 30
dist = [INF] * (H * W)
que = []

def push(v, d):
    if(dist[v] <= d):
        return
    dist[v] = d
    heapq.heappush(que, (d, v))

def move(ny, nx, d):
    if ny < 0 or ny >= H or nx < 0 or nx >= W:
        return
    if graph[ny][nx] == '.':
        push(ny * W + nx, d)

push(s, 0)

while que:
    d, v = heapq.heappop(que)
    if d > dist[v]:
        continue
    if v == t:
        break
    y, x = divmod(v, W)
    for dy in range(-2, 3):
        for dx in range(-2, 3):
            move(y + dy, x + dx, d + (abs(dy) + abs(dx) > 1))

if dist[t] == INF:
    print(-1)
else:
    print(dist[t])
### BUGGY CODE ###

MOD = 10**9+7

s=input()
Anum = 0
ABnum = 0
ABCnum = 0
q = 0
for c in s:
    if c == 'A':
        Anum = (Anum+3**q)%MOD
    elif c == 'B':
        ABnum = (ABnum+Anum)%MOD
    elif c == 'C':
        ABCnum = (ABCnum+ABnum)%MOD
    else:
        Anum,ABnum,ABCnum = 3*Anum+3**q,3*ABnum+Anum,3*ABCnum+ABnum
        Anum,ABnum,ABCnum = Anum%MOD,ABnum%MOD,ABCnum%MOD
        q += 1
print(ABCnum)


### FIXED CODE ###

MOD = 10**9+7

s=input()
Anum = 0
ABnum = 0
ABCnum = 0
q = 0
for c in s:
    if c == 'A':
        Anum = (Anum+pow(3,q,MOD))%MOD
    elif c == 'B':
        ABnum = (ABnum+Anum)%MOD
    elif c == 'C':
        ABCnum = (ABCnum+ABnum)%MOD
    else:
        Anum,ABnum,ABCnum = 3*Anum+pow(3,q,MOD),3*ABnum+Anum,3*ABCnum+ABnum
        Anum,ABnum,ABCnum = Anum%MOD,ABnum%MOD,ABCnum%MOD
        q += 1
print(ABCnum)
### BUGGY CODE ###

def main():
    N,M=map(int,input().split())
    job=[[0,0] for i in range(0,N)]
    for i in range(0,N):
        job[i][0],job[i][1]=map(int,input().split())
    s=0
    job=sorted(job,reverse=True)
    for i in range(0,M):
        for j in range(0,N):
            if job[j][0]>M-i:
                job[j][1]=0
        jobsub=[job[k][1] for k in range(0,N)]
        s+=max(jobsub)
        job[jobsub.index(max(jobsub))][1]=0

    print(s)


if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
import heapq

input=sys.stdin.readline

N,M=map(int,input().split())
job={i:[] for i in range(1,M+1)}
for i in range(0,N):
    a,b=map(int,input().split())
    if M>=a:
        job[a].append(b)

ans=0
ablejob=[]
heapq.heapify(ablejob)
for i in range(1,M+1):
    for j in job[i]:
        heapq.heappush(ablejob,-j)
    if ablejob:
        m=-heapq.heappop(ablejob)
        ans+=m

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

import numpy as np
N = int(input())
def chack(s):
    def f(s):
        return s == '5' or s == '3' or s == '7'
    if ('5' in s) & ('3' in s) & ('7' in s) :
        return all([ f(i) for i in s])
    return False
print(np.array([chack(str(i)) for i in range(0,N+1)]).sum())

### FIXED CODE ###

from itertools import product
N = int(input())
ans = 0
for l in range(1, 10):
    for p in product("357", repeat=l):
        v = "".join(p)
        if "3" in v and "5" in v and "7" in v and int(v) <= N:
            ans += 1
            continue
        elif int(v) > N :
            break
print(ans)
### BUGGY CODE ###

R, C, K = map(int, input().split())
item = [[0] * 3010 for _ in range(3010)]
for _ in range(K):
    r, c, v = map(int, input().split())
    item[r][c] = v

dp = [[[0] * 4 for _ in range(3010)] for _ in range(3010)]
for r in range(1, R+1):
    for c in range(1, C+1):
        prer = max(dp[r-1][c])
        dp[r][c][0] = max(prer, dp[r][c-1][0])
        dp[r][c][1] = max(prer, dp[r][c-1][1])
        dp[r][c][2] = max(prer, dp[r][c-1][2])
        dp[r][c][3] = max(prer, dp[r][c-1][3])
        if item[r][c] > 0:
            dp[r][c][1] = max(dp[r][c][1], max(prer, dp[r][c-1][0]) + item[r][c])
            dp[r][c][2] = max(dp[r][c][2], max(prer, dp[r][c-1][1]) + item[r][c])
            dp[r][c][3] = max(dp[r][c][3], max(prer, dp[r][c-1][2]) + item[r][c])

print(max(dp[R][C]))


### FIXED CODE ###

R, C, K = map(int, input().split())
item = {}
for _ in range(K):
    r, c, v = map(int, input().split())
    item[(r, c)] = v

dp = [[0] * 4 for _ in range(3010)]
ndp = [[0] * 4 for _ in range(3010)]
for r in range(1, R+1):
    for c in range(1, C+1):
        prer = max(dp[c])
        ndp[c][0] = max(prer, ndp[c-1][0])
        ndp[c][1] = max(prer, ndp[c-1][1])
        ndp[c][2] = max(prer, ndp[c-1][2])
        ndp[c][3] = max(prer, ndp[c-1][3])
        if item.get((r, c)):
            ndp[c][1] = max(ndp[c][1], max(prer, ndp[c-1][0]) + item[(r,c)])
            ndp[c][2] = max(ndp[c][2], max(prer, ndp[c-1][1]) + item[(r,c)])
            ndp[c][3] = max(ndp[c][3], max(prer, ndp[c-1][2]) + item[(r,c)])
    dp = ndp
    ndp = [[0] * 4 for _ in range(3010)]

#print(dp)
print(max(dp[C]))
### BUGGY CODE ###

INF = 10**12

class Rmin():
	def __init__(self, size):
		#the number of nodes is 2n-1
		self.n = 1 << (size.bit_length())
		self.node = [INF] * (2*self.n-1)

	def Access(self, x):
		return self.node[x+self.n-1]

	def Update(self, x, val):
		x += self.n-1
		self.node[x] = val
		while x > 0:
			x = (x-1)>>1
			self.node[x] = min(self.node[(x<<1)+1], self.node[(x<<1)+2])
		return

	#[l, r)
	def Get(self, l, r):
		L, R = l+self.n, r+self.n
		s = INF
		while L<R:
			if R & 1:
				R -= 1
				s = min(s, self.node[R-1])
			if L & 1:
				s = min(s, self.node[L-1])
				L += 1
			L >>= 1
			R >>= 1
		return s

n, q, a, b = map(int, input().split())
qs = list(map(int, input().split()))
dp_l, dp_r = Rmin(n+1), Rmin(n+1)
dp_l.Update(b, -b)
dp_r.Update(b, b)

total_diff = 0
x = a
for y in qs:
	diff = abs(y - x)
	l_min = dp_l.Get(1, y)
	r_min = dp_r.Get(y, n+1)
	res = min(l_min + y, r_min - y)
	dp_l.Update(x, res - diff - x)
	dp_r.Update(x, res - diff + x)
	total_diff += diff
	x = y

N = dp_l.n
print(total_diff + min(dp_l.node[i+N-1] + i for i in range(1, n+1)))

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
INF = 10**12

class Rmin():
	def __init__(self, size):
		#the number of nodes is 2n-1
		self.n = 1 << (size.bit_length())
		self.node = [INF] * (2*self.n-1)

	def Access(self, x):
		return self.node[x+self.n-1]

	def Update(self, x, val):
		x += self.n-1
		self.node[x] = val
		while x > 0:
			x = (x-1)>>1
			self.node[x] = min(self.node[(x<<1)+1], self.node[(x<<1)+2])
		return

	#[l, r)
	def Get(self, l, r):
		L, R = l+self.n, r+self.n
		s = INF
		while L<R:
			if R & 1:
				R -= 1
				s = min(s, self.node[R-1])
			if L & 1:
				s = min(s, self.node[L-1])
				L += 1
			L >>= 1
			R >>= 1
		return s

n, q, a, b, *qs = map(int, read().split())
dp_l, dp_r = Rmin(n+1), Rmin(n+1)
dp_l.Update(b, -b)
dp_r.Update(b, b)

total_diff = 0
x = a
for y in qs:
	diff = abs(y - x)
	l_min = dp_l.Get(1, y)
	r_min = dp_r.Get(y, n+1)
	res = min(l_min + y, r_min - y)
	dp_l.Update(x, res - diff - x)
	dp_r.Update(x, res - diff + x)
	total_diff += diff
	x = y

N = dp_l.n
print(total_diff + min((l+r)>>1 for l, r in zip(dp_l.node[N:], dp_r.node[N:])))
### BUGGY CODE ###

from bisect import bisect_left

INF = 10**18

A, B, Q = map(int, input().split())
S = [-INF] + [int(input()) for _ in range(A)] + [INF]
T = [-INF] + [int(input()) for _ in range(B)] + [INF]

for _ in range(Q):
    x = int(input())
    si = bisect_left(S,x)
    ti = bisect_left(T,x)
    res = INF
    res = min(res, max(S[si] - x, T[ti] - x))
    res = min(res, max(x - S[si - 1], x - T[ti - 1]))
    res = min(res, x + T[ti] - 2 * S[si - 1])
    res = min(res, -x + 2 * T[ti] - S[si - 1])
    res = min(res, x + S[si] - 2 * T[ti - 1])
    res = min(res, -x + 2 * S[si] - T[ti - 1])
    print(res)

### FIXED CODE ###

import bisect

A,B,Q = map(int,input().split())
shrine = [-float('inf')]+[int(input()) for _ in range(A)]+[float('inf')]
temple = [-float('inf')]+[int(input()) for _ in range(B)]+[float('inf')]
query = [int(input()) for _ in range(Q)]

for q in query:
  s = bisect.bisect(shrine,q)
  t = bisect.bisect(temple,q)
  print(
      min(
        max(shrine[s],temple[t])-q, 
        q - min(shrine[s-1],temple[t-1]),
        (shrine[s]-q)*2+(q-temple[t-1]),
        (temple[t]-q)*2+(q-shrine[s-1]),
        (shrine[s]-q)+(q-temple[t-1])*2,
        (temple[t]-q)+(q-shrine[s-1])*2,
        )
        )
### BUGGY CODE ###

# -*- coding: utf-8 -*-
S = input()
Q = int(input())

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

### FIXED CODE ###


# -*- coding: utf-8 -*-

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

rev = False
S1 = ['0'] * Q
S1i = 0
S2 = ['0'] * Q
S2i = 0

for q in range(Q):
    i = input()
    if i[0] == "1":
        rev = not rev
    elif not rev and i[2] == "1" or rev and i[2] == "2":
        # S = i[4] + S
        S1[S1i] = i[4]
        S1i += 1
    else:
        # S = S + i[4]
        S2[S2i] = i[4]
        S2i += 1

S1 = S1[0:S1i]
S2 = S2[0:S2i]
S1 = S1[::-1]

S = ''.join(''.join(S1) + S + ''.join(S2))

if rev:
    S = S[::-1]

print(S)
### BUGGY CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
dp=[0]*(k+1)
dp[0]=1
mod=10**9+7
for i in range(n):
  for j in range(k,0,-1):
    if j>a[i]:dp[j]-=dp[j-a[i]-1]
  for j in range(k):dp[j+1]=(dp[j+1]+dp[j])%mod
print(dp[k])

### FIXED CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
dp=[0]*(k+1)
dp[0]=1
mod=10**9+7
for i in range(n):
  for j in range(k,0,-1):
    if j>a[i]:dp[j]-=dp[j-a[i]-1]
  for j in range(k):dp[j+1]=(dp[j+1]+dp[j])%mod
print(dp[k])
### BUGGY CODE ###

a,b=map(int,input().split())
for x in range(-~a,-~b):a*=x
print(['Zero','Positive','Negative'][-1if a<0else bool(a)])

### FIXED CODE ###

a,b=map(int,input().split())
if a<=0<=b:c='Zero'
elif 0<a<=b:c='Positive'
elif not abs(abs(a)-abs(b))&1:c='Negative'
else:c='Positive'
print(c)