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

import fractions
from functools import reduce
import math

MOD = 10**9 + 7


def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)


def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)


def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)


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


def pathes(x, y):
    # xf = None
    # yf = None
    # xyf = None
    # temp = 1
    # for i in range(1, x + y + 1):
    #     temp *= i % MOD
    #     if i == x:
    #         xf = temp
    #     if i == y:
    #         yf = temp
    #     if i == x + y:
    #         xyf = temp
    xf = math.factorial(x) % MOD
    yf = math.factorial(y) % MOD
    xyf = math.factorial(x + y) % MOD

    return xyf * modinv(xf * yf % MOD, MOD)


def main():
    r1, c1, r2, c2 = map(int, input().split())

    a = (pathes(r1, c1) - 1) % MOD
    b = (pathes(r1, c2 + 1) - 1) % MOD
    c = (pathes(r2 + 1, c1) - 1) % MOD
    d = (pathes(r2 + 1, c2 + 1) - 1) % MOD

    print((d - c - b + a) % MOD)


main()


### FIXED CODE ###

import fractions
from functools import reduce
import math

MOD = 10**9 + 7


def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)


def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)


def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)


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


# def pathes(x, y):
#     xf = None
#     yf = None
#     xyf = None
#     temp = 1
#     for i in range(1, x + y + 1):
#         temp *= i % MOD
#         if i == x:
#             xf = temp
#         if i == y:
#             yf = temp
#         if i == x + y:
#             xyf = temp
#     # xf = math.factorial(x) % MOD
#     # yf = math.factorial(y) % MOD
#     # xyf = math.factorial(x + y) % MOD

#     return xyf * modinv(xf * yf % MOD, MOD)


def pathes(rf, cf, rcf):
    return rcf * modinv((rf * cf) % MOD, MOD)


def main():
    r1, c1, r2, c2 = map(int, input().split())

    f = [1 for _ in range(r2 + c2 + 2 + 1 + 1)]

    for i in range(1, r2 + c2 + 2 + 1):
        f[i] = f[i - 1] * i % MOD

    a = (pathes(f[r1], f[c1], f[r1 + c1]) - 1) % MOD
    b = (pathes(f[r1], f[c2 + 1], f[r1 + c2 + 1]) - 1) % MOD
    c = (pathes(f[r2 + 1], f[c1], f[r2 + 1 + c1]) - 1) % MOD
    d = (pathes(f[r2 + 1], f[c2 + 1], f[r2 + c2 + 2]) - 1) % MOD

    print((d - c - b + a) % MOD)


main()
### BUGGY CODE ###

# D
N, M = map(int, input().split())
a_list = list(map(int, input().split()))

G = dict()
for i in range(N):
    G[i] = []

for _ in range(M):
    x, y = map(int, input().split())
    G[x].append(y)
    G[y].append(x)
    
res = 0
connec = 0
done_list = [0]*N
conn_list = []

st = 0
while True:
    while st < N:
        if done_list[st] == 0:
            break
        st += 1

    if st == N:
        break

    queue = [st]
    conn = [a_list[st]]
    done_list[st] = 1
    connec += 1

    while len(queue) > 0:
        s = queue.pop()
        for t in G[s]:
            if done_list[t] == 0:
                done_list[t] = 1
                queue.append(t)
                conn.append(a_list[t])
                
    conn.sort()
    res += conn[0]
    conn_list = conn_list + conn[1:]

conn_list.sort()

if connec == 1:
    print(0)
elif len(conn_list) < connec - 2:
    print('Impossible')
else:
    print(res + sum(conn_list[:(connec - 2)]))


### FIXED CODE ###

# D
import numpy as np

N, M = map(int, input().split())
a_list = list(map(int, input().split()))

G = dict()
for i in range(N):
    G[i] = []

for _ in range(M):
    x, y = map(int, input().split())
    G[x].append(y)
    G[y].append(x)
    
res = 0
connec = 0
done_list = [0]*N

st = 0
while True:
    while st < N:
        if done_list[st] == 0:
            break
        st += 1

    if st == N:
        break

    queue = [st]
    conn = [a_list[st]]
    conn_ = [st]
    done_list[st] = 1
    connec += 1

    while len(queue) > 0:
        s = queue.pop()
        for t in G[s]:
            if done_list[t] == 0:
                done_list[t] = 1
                queue.append(t)
                conn.append(a_list[t])
                conn_.append(t)
                
    args = np.argsort(conn)
    res += conn[args[0]]
    a_list[conn_[args[0]]] = 2000000000

a_list.sort()

if connec == 1:
    print(0)
elif len(a_list) < 2*connec - 2:
    print('Impossible')
else:
    print(res + sum(a_list[:(connec - 2)]))
### BUGGY CODE ###

import sys

input = sys.stdin.readline


def binary_search(a, key):
    """Meguru type binary search"""
    ng = -1
    ok = len(a)

    while (ok - ng > 1):
        mid = (ok + ng) // 2
        if a[mid] >= key:
            ok = mid
        else:
            ng = mid

    return ok


def solve(N, L):
    L.sort()
    ans = 0
    for a in range(N - 2):
        for b in range(a + 1, N - 1):
            c = binary_search(L, L[a] + L[b]) - 1
            ans += c - b
    return ans


def main():
    N = int(input())
    L = list(map(int, input().split()))

    ans = solve(N, L)
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
from bisect import bisect_left

input = sys.stdin.readline


def main():
    N = int(input())
    L = list(map(int, input().split()))

    L.sort()
    ans = 0
    for i in range(N - 1):
        a = L[i]
        for j in range(i + 1, N):
            k = bisect_left(L, a + L[j])
            ans += (k - 1 - j)

    print(ans)


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

n,k=[int(c) for c in input().split()]
MOD = 998244353
segs = set()
for _ in range(k):
    a,b=[int(c) for c in input().split()]
    for i in range(a,b+1):
        segs.add(i)

dp =[0 for i in range(n)]
dp[0] = 1
# print(segs)

for i in range(n-1):
    if dp[i] != 0:
        for j in segs:
            if i + j < n:
                dp[i+j] = dp[i+j] + dp[i]
                dp[i+j]%=MOD

# print(dp)
print(dp[-1])



### FIXED CODE ###

n,k=[int(c) for c in input().split()]
MOD = 998244353
segs = []
for _ in range(k):
    a,b=[int(c) for c in input().split()]
    segs.append((a,b))


dp=[0 for i in range(n+5)]
dp[0] = 1

for i in range(n):
    # dp[i] = dp[i] + dp[i-1]
    if dp[i] < 0:
        dp[i]+=MOD
    for a,b in segs:
        if i+a <=n:
            dp[i+a]+=dp[i]
        if i+b+1 <= n:
            dp[i+b+1]-=dp[i]
    dp[i]%=MOD
    if i !=0:
        dp[i+1] = dp[i+1]+dp[i]

print(dp[n-1]%MOD)
### BUGGY CODE ###

L=int(input())
ans=0
tmp=0
d=3
for i in range(L*d):
  for j in range(L*d-i):
    tmp=(i/d)*(j/d)*(L-(i/d)-(j/d))
    ans=max(ans,tmp,0)
print(ans)

### FIXED CODE ###

L=int(input())
print((L**3)/27)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
INF = 10**9
N, K = map(int, input().split())
h = list(map(int, input().split()))

dp = [INF for _ in range(N)]
dp[0] = 0

for i in range(1, N):
    MIN = INF
    for l in range(min(i, K)):
        MIN = min(MIN, dp[i - (l + 1)] + abs(h[i] - h[i - (l + 1)]))
    dp[i] = MIN
print(dp[N - 1])


### FIXED CODE ###

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

dp = [[10**9 for _ in range(K+1)] for _ in range(N)]
dp[0] = [0 for _ in range(K+1)]

for i in range(N):
    for l in range(K):
        if i-(l+1) >= 0:
            dp[i][l] = dp[i - (l + 1)][K] + abs(h[i] - h[i - (l + 1)])
        else:
            dp[i][l] = min(dp[i])
        if l == K-1:
            dp[i][K] = min(dp[i])
print(min(dp[N-1]))
### BUGGY CODE ###

from collections import deque
S=input()
S_list=deque()
for k in range(len(S)):
    S_list.append(S[k])
Q=int(input())
kouho=[input().split() for i in range(Q)]
"""for i in range(Q):
    kari=input().split()
    kouho.append(kari)"""
for j in kouho:
    if j[0]=="1":
        S_list.reverse()
    else:
        if j[1]=="1":
            S_list.appendleft(j[2])
        else:
            S_list.append(j[2])
print(*S_list,sep="")


### FIXED CODE ###

from collections import deque
S=input()
S_list=deque()
for k in range(len(S)):
    S_list.append(S[k])
Q=int(input())
kouho=[input().split() for i in range(Q)]
"""for i in range(Q):
    kari=input().split()
    kouho.append(kari)"""
hanten=[]
count=0
flaag=["sonomama","hantai"]

for j in range(Q):
    flag=flaag[count%2]
    if kouho[j][0]=="1":
        count+=1
    else:
        if flag=="sonomama":
            if kouho[j][1]=="1":
                S_list.appendleft(kouho[j][2])
            else:
                S_list.append(kouho[j][2])
        else:
            if kouho[j][1]!="1":
                S_list.appendleft(kouho[j][2])
            else:
                S_list.append(kouho[j][2])
for k in range(count%2):
    S_list.reverse()
print(*S_list,sep="")
### BUGGY CODE ###

import numpy as np

N = int(input())
L = np.array(list(map(int, input().split())))

ans = 0

L = np.sort(L)

for a in range(N-2):
    for b in range(a+1, N-1):
        ans += sum((L < (L[a]+L[b])) * (L > L[b]))

print(ans)


### FIXED CODE ###

# https://takeg.hatenadiary.jp/entry/2019/11/22/212816

import bisect

def solve():
    N = int(input())
    Ls = list(map(int, input().split()))
    Ls.sort()

    # O(N^2 * logN)の全探索で解く
    ans = 0
    for a_i in range(N):
        for b_i in range(a_i+1, N):
            c_i = bisect.bisect_left(Ls, Ls[a_i]+Ls[b_i])
            if c_i > b_i:
                ans += c_i - b_i - 1
            else:
                pass

    print(ans)

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

import sys

ns = lambda: sys.stdin.readline().rstrip()
ni = lambda: int(ns())
na = lambda: [int(x) for x in ns().split()]
nall = lambda: [int(x) for x in sys.stdin.readlines()]
sall = lambda: sys.stdin.readlines()

def main():
    n, k = na()
    xs = na()

    m = float('inf')
    for i in range(n-k+1):
        vs = xs[i:i+k]
        if vs[0] * vs[-1] < 0:
            l = abs(vs[0]) + abs(vs[-1]) + min(abs(vs[0]), abs(vs[-1]))
        else:
            l = max(abs(vs[0]), abs(vs[-1]))

        m = min(m, l)

    print(m)
    
main()


### FIXED CODE ###

import sys

ns = lambda: sys.stdin.readline().rstrip()
ni = lambda: int(ns())
na = lambda: [int(x) for x in ns().split()]
nall = lambda: [int(x) for x in sys.stdin.readlines()]
sall = lambda: sys.stdin.readlines()

def main():
    n, k = na()
    xs = na()

    m = float('inf')
    for i in range(n-k+1):
        if xs[i] * xs[i+k-1] < 0:
            l = abs(xs[i]) + abs(xs[i+k-1]) + min(abs(xs[i]), abs(xs[i+k-1]))
        else:
            l = max(abs(xs[i]), abs(xs[i+k-1]))

        m = min(m, l)

    print(m)
    
main()
### BUGGY CODE ###

import numpy as np
from numba import njit

@njit(cache=True)
def main(N, s, dpt, result):
    for i in range(1, N+1):
        for j in range(i+1, N+1):
            if s[j-1] == s[i-1]:
                if j - dpt[i-1][j-1] > i:
                    dpt[i][j] = dpt[i-1][j-1] + 1
            if dpt[i][j] > result:
                result = dpt[i][j]

    return result

if __name__ == '__main__':
    N = int(input())
    s = input()

    dpt = np.zeros((N+1, N+1), dtype='int32')
    result = 0
    print(main(N, s, dpt, result))


### FIXED CODE ###

import numpy as np
from numba import njit
 
@njit(cache=True)
def main(N, s):
    dpt = np.zeros((N+1, N+1), dtype=np.int16)
    for i in range(1, N+1):
        for j in range(i+1, N+1):
            if s[j-1] == s[i-1]:
                if j - dpt[i-1][j-1] > i:
                    dpt[i][j] = dpt[i-1][j-1] + 1
 
    return np.amax(dpt)
 
if __name__ == '__main__':
    N = int(input())
    s = np.array([ord(c) for c in input()]) 
 
    print(main(N, s))
### BUGGY CODE ###

mods = [0]*2019
mods[0] = 1
s = input()
dp = [0 for i in range(len(s)+1)]
for i in range(1,len(s)+1):
    k = len(s) - i
    dp[i] = (dp[i-1] + int(s[k])*(pow(10,i-1)))%2019
    mods[dp[i]] += 1


cnt = 0
for x in mods:
    if x >= 2:
        cnt += x*(x-1)//2
print(cnt)



### FIXED CODE ###

mods = [0]*2019
mods[0] = 1
s = input()
t = 0
u = 1
for i in range(1,len(s)+1):
    t = (t + int(s[-i])*u)%2019
    u = u*10%2019
    mods[t] += 1


cnt = 0
for x in mods:
    if x >= 2:
        cnt += x*(x-1)/2
print(int(cnt))
### BUGGY CODE ###

N, M = map(int, input().split())
A = []
sumcost = 0
for i in range(N):
    a = list(map(int, input().split()))
    A.append(a)
k = 0
A.sort()
while k < M:
    sumcost += A[0][0]
    A[0][1] -= 1
    if A[0][1]<1:
        A.pop(0)
    k += 1



print(sumcost)

### FIXED CODE ###

N, M = map(int, input().split())
A = [list(map(int, input().split())) for i in range(N)]
A.sort()
sumcost = 0
for i in range(M):
    sumcost += A[0][0]
    A[0][1] -= 1
    if A[0][1] < 1:
        A.pop(0)

print(sumcost)
### BUGGY CODE ###

# ABC 065 B

N = int(input())
A = [int(input()) for _ in range(N)]

q = []
i = 0
while i != 1:
    if A[i] in q:
        print(-1)
        break
    q.append(A[i])
    i = A[i] - 1
else:
    print(len(q))

### FIXED CODE ###

# ABC 065 B

N = int(input())
A = [int(input()) for _ in range(N)]

i = 1
s = 0
while i != 2:
    s += 1
    A[i-1], i = 1, A[i-1]
    if i == 1:
        print(-1)
        break
else:
    print(s)
### BUGGY CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf = 10**10
mod = 10**9 + 7

def f():
    n = int(input())
    a = list(map(int, input().split()))
    mi = []
    def g(a, j):
        l = len(a)
        if l == 0:
            return 0
        if l == 1:
            return a[0]
        if a[0] == j:
            return l * j + g(a[1:], j+1)
        if a[-1] == j:
            return l * j + g(a[:l-1], j+1)
        m = min(a)
        i = a.index(m)
        return (i+1) * (l-i) * m + g(a[i+1:], m+1) + g(a[:i], m+1)
    return g(a, 1)

print(f())


### FIXED CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf = 10**10
mod = 10**9 + 7

def f():
    n = int(input())
    a = list(map(int, input().split()))
    l = list(range(n+2))
    r = list(range(n+2))
    b = [0]*(n+2)
    for i, x in enumerate(a, 1):
        b[x] = i
    c = 0
    for i in range(n,0,-1):
        bi = b[i]
        c += i * (r[bi] - bi + 1) * (bi - l[bi] + 1)
        r[l[bi]-1] = r[bi]
        l[r[bi]+1] = l[bi]
    return c

print(f())
### BUGGY CODE ###

# @oj:atcoder
# @id: hitwanyang
# @email: 296866643@qq.com
# @date: 2020-04-20 10:31
# @url:https://atcoder.jp/contests/dp/tasks/dp_b
import sys
def input():
    return sys.stdin.readline().strip()

def main():
    nk=list(map(int,input().split()))
    h=list(map(int,input().split()))
    n=nk[0]
    k=nk[1]
    dp=[10**9]*n
    dp[0]=0
    dp[1]=abs(h[1]-h[0])
    for i in range(2,n):
        for j in range(max(0,i-k),i):
            dp[i]=min(dp[j]+abs(h[i]-h[j]),dp[i])

    print (dp[-1])

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys


def input():
    return sys.stdin.readline().strip()


def main():
    size, jumps = map(int, input().split())
    array = list(map(int, input().split()))
    dp = [999999999] * size
    dp[0]= 0
    dp[1] = abs(array[0]- array[1])
    for i in range(2,size):
        dp[i] = min(abs(array[i] - array[j]) + dp[j] for j in range(max(0, i - jumps), i))
    print(dp[size-1])

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

import numpy as np

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

ans = 0
i = k-1
fil = np.array(range(1,i+1))
for j in range(i,n+k-1):
    cur = np.cumsum(A[j-i:j])
    if len(cur) != len(fil):
        fil = np.array(range(1,len(cur)+1))
    # print(cur)
    # print(cur%k == fil)
    ans += np.count_nonzero(cur%k == fil)
print(ans)

### FIXED CODE ###

import numpy as np
from queue import Queue
n,k = map(int,input().split())
A = [a-1 for a in list(map(int,input().split()))]
A = np.cumsum(+np.array([0]+A))%k

dic = {}
ans = 0
Q = Queue()
for a in A:
    Q.put(a)
    if a in dic:
        ans += dic[a]
        dic[a] += 1
    else:
        dic[a] = 1
    if Q.qsize() == k:
        q = Q.get()
        dic[q] -= 1
    # print(dic)
print(ans)
### BUGGY CODE ###

from operator import mul
from functools import reduce
from collections import defaultdict

def combination(n, r):
    if not 0 <= r <= n: return 0
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom

S = input()
L = len(S)
res = 0

T = [0]

for i in range(1,L+1):
    T.append(int(S[L-i:]))

reminder = defaultdict(int)
for i in range(L+1):
    reminder[T[i]%2019] += 1

for c in reminder.values():
    res += combination(c,2)

print(res)

### FIXED CODE ###

# https://atcoder.jp/contests/abc164/tasks/abc164_d

from operator import mul
from functools import reduce
from collections import defaultdict

def combination(n, r):
    if not 0 <= r <= n: return 0
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom

S = input()

res = 0

T = [0]
x = 0
L = len(S)
for i, s in zip(range(L),reversed(S)):
    """ 累積和 """
    x = (int(s)*pow(10,i,2019) + x)%2019
    T.append(x)

reminder = [0]*2019
for i in range(L+1):
    reminder[T[i]%2019] += 1

for c in reminder:
    res += combination(c,2)

print(res)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(100000)
while True:
  n,m,h,k = map(int,input().split())
  if not n: break
  s_lst = [int(input()) for _ in range(n)]
  b_lst = [tuple(map(int,input().split())) for _ in range(m)]
  b_lst = sorted(b_lst,key=lambda x:-x[1])
  def amida(b_lst, s_lst, used, k):
    if not b_lst:
      return sum(s_lst[0:k])
    elif used:
      for bar in b_lst:
        a = bar[0]
        temp = s_lst[a]
        s_lst[a] = s_lst[a - 1]
        s_lst[a - 1] = temp
      return sum(s_lst[0:k])
    else:
      save_s_lst = [i for i in s_lst]
      a = b_lst[0][0]
      temp = s_lst[a]
      s_lst[a] = s_lst[a - 1]
      s_lst[a - 1] = temp
      return min(amida(b_lst[1:], s_lst, 0, k), amida(b_lst[1:], save_s_lst, 1, k))

  print(amida(b_lst, s_lst, 0, k))



### FIXED CODE ###

while True:
  n,m,h,k = map(int,input().split())
  if not n: break
  s_lst = [int(input()) for _ in range(n)]
  i_lst = [i for i in range(n)]
  b_lst = [tuple(map(int,input().split())) for _ in range(m)]
  b_lst = sorted(b_lst,key=lambda x:x[1])
  pare_lst = []
  for bar in b_lst:
    ind = bar[0]
    temp = i_lst[ind]
    i_lst[ind] = i_lst[ind - 1]
    i_lst[ind - 1] = temp
    pare_lst.append((i_lst[ind], i_lst[ind - 1]))
#  print(i_lst)
  new_s_lst = [0] * n
  for i in range(n):
    new_s_lst[i_lst[i]] = s_lst[i]
#  print(s_lst)
  ans = sum(new_s_lst[:k])
#  print(ans)
#  print(pare_lst)
  max_dec = 0
  for pare in pare_lst:
    a = pare[0]
    b = pare[1]
#    print(a,b,s_lst[a],s_lst[b])
    if a < k and b >= k and new_s_lst[a] - new_s_lst[b] > max_dec:
      max_dec = new_s_lst[a] - new_s_lst[b]
    if b < k and a >= k and new_s_lst[b] - new_s_lst[a] > max_dec:
      max_dec = new_s_lst[b] - new_s_lst[a]
  print(ans - max_dec)
### BUGGY CODE ###

# sys.stdin.readline()
import math
import sys


def decision(s,td,index):
    #index番目の文字が落ちるかどうかを判別
    #右に落ちるときは1，左に落ちるときは-1，落ちないときは0を返す
    global N,Q
    qi = 0
    j = index
    for qi in range(Q):
        if j < 0 or j >= N:
            break
        if s[j] == td[qi][0]:
            if td[qi][1] == 'L':
                j -= 1
            elif td[qi][1] == 'R':
                j += 1
    if j == -1:
        return -1
    elif j == N:
        return 1
    else:
        return 0
 
N,Q = map(int,input().split())
s = sys.stdin.readline()
 
td = [0] * Q
for i in range(Q):
    td[i] = (sys.stdin.readline().split())
    
#td[i][j]:i番目の文字(j=0)と方向(j=1)
    
    
RN = math.ceil(math.log2(N))
#2分探索
left = 0
right = N-1
#右側のボーダー
for i in range(RN):
    mid = int((right+left)/2)
    state = decision(s,td,mid)
    if state < 1:
        left = mid
    else:
        right = mid
    if (right - left) == 1:
        break
if right == N-1 and decision(s,td,right) == 0:
    right += 1
border_r = right
    
left = 0
right = N-1
#左側のボーダー
for i in range(RN):
    mid = int((right+left)/2)
    state = decision(s,td,mid)
    if state > -1:
        right = mid
    else:
        left = mid
    if (right - left) == 1:
        break
if left == 0 and decision(s,td,left) == 0:
    right -= 1
border_l = right
print(border_r-border_l)
 

### FIXED CODE ###

# sys.stdin.readline()
import math
import sys
input = sys.stdin.readline


def decision(s,td,j):
    #index番目の文字が落ちるかどうかを判別
    #右に落ちるときは1，左に落ちるときは-1，落ちないときは0を返す
    global N,Q
    for [qi,v] in td:
        if j < 0 or j >= N:
            break
        if s[j] == qi:
            if v == 'L':
                j -= 1
            else:
                j += 1
    if j == -1:
        return -1
    elif j == N:
        return 1
    else:
        return 0
 
N,Q = map(int,input().split())
s = input()
td = [input().split() for _ in range(Q)]
    
#td[i][j]:i番目の文字(j=0)と方向(j=1)
    
    
RN = math.ceil(math.log2(N))
#2分探索
left = 0
right = N-1
#右側のボーダー
for i in range(RN):
    mid = (right+left)//2
    state = decision(s,td,mid)
    if state < 1:
        left = mid
    else:
        right = mid
    if (right - left) == 1:
        break
if right == N-1 and decision(s,td,right) == 0:
    right += 1
border_r = right
    
left = 0
right = N-1
#左側のボーダー
for i in range(RN):
    mid = ((right+left)//2)
    state = decision(s,td,mid)
    if state > -1:
        right = mid
    else:
        left = mid
    if (right - left) == 1:
        break
if left == 0 and decision(s,td,left) == 0:
    right -= 1
border_l = right
print(border_r-border_l)
### BUGGY CODE ###

from itertools import product
n = int(input())
v = list(map(int, input().split()))
c = list(map(int, input().split()))

a = list(product([0, 1], repeat=n))
m = 0
xsum = 0
ysum = 0

for i in range(len(a)):
    for j in range(n):
        if a[i][j] == 1:
            xsum += v[j]
            ysum += c[j]
    difxy = xsum - ysum
    if difxy > m:
        m = difxy
    xsum = 0
    ysum = 0

print(m)


### FIXED CODE ###

n = int(input())
v = list(map(int, input().split()))
c = list(map(int, input().split()))

m = 0
for i in range(n):
    difxy = v[i] - c[i]
    if difxy > 0:
        m += difxy

print(m)
### BUGGY CODE ###

import sys
from numpy import array
inp = sys.stdin.readline
read = lambda: list(map(int, inp().strip().split()))


def solve():
    n, k =read(); arr = read()
    dp = array([-1 for i in range(n)]); dp[0] = 0
    for i in range(n):
    	for j in range(1, k+1):
    		if i-j >-1:
    			tem = dp[i-j]+abs(arr[i-j] - arr[i])
    			if dp[i] == -1:
    				dp[i] = tem
    			else:
    				dp[i] = min(dp[i], tem)
    print(dp[-1])

    

if __name__ == "__main__":
	solve()

### FIXED CODE ###

import sys
# import numpy as np
inp = sys.stdin.readline
read = lambda: list(map(int, inp().strip().split()))
# import profile

def solve():
    n, k =read(); arr = read()
    dp = [-1]*n; dp[0] = 0
    for i in range(n):
    	for j in range(1, k+1):
    		if i-j >-1:
    			tem = dp[i-j]+abs(arr[i-j] - arr[i])
    			if dp[i] == -1:
    				dp[i] = tem
    			elif dp[i] > tem:
    				dp[i] = tem
    				# dp[i] = min(dp[i], tem)
    print(dp[-1])

def one():
	l = [0]*10**7
def two():
	l = [0 for i in range(10**7)]

if __name__ == "__main__":
	solve()
	# cProfile.run(solve())
	# profile.run(one())
	# cProfile.run()
### BUGGY CODE ###

n = int(input())
D = list(map(int,input().split()))
m = int(input())
T = list(map(int,input().split()))
for i in range(m):
    if T[i] in D:
        del D[D.index(T[i])]
    else:
        print("NO")
        exit()
print("YES")

### FIXED CODE ###

import collections
n = int(input())
d = list(map(int, input().split()))
m = int(input())
t = list(map(int, input().split()))
dc = collections.Counter(d)
tc = collections.Counter(t)
for i in tc:
    if tc[i] > dc[i]:
        print("NO")
        exit()
print("YES")