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

from collections import deque
import bisect

a, b, q = [int(x) for x in input().split()]
s = [int(input()) for i in range(a)]
t = [int(input()) for i in range(b)]
x = [int(input()) for i in range(q)]

s_que = deque(s)
s_que.appendleft(-10 ** 12)
s_que.append(10 ** 12)

t_que = deque(t)
t_que.appendleft(-10 ** 12)
t_que.append(10 ** 12)

for i in x:
    k = bisect.bisect_left(s_que, i)
    sb = s_que[k]
    sa = s_que[k-1]
    j = bisect.bisect_left(t_que, i)
    tb = t_que[j]
    ta = t_que[j-1]

    y = []
    for h in [sa, sb]:
        for g in [ta, tb]:
            y.append(abs(i-h) + abs(h-g))
    for h in [ta, tb]:
        for g in [sa, sb]:
            y.append(abs(i-h) + abs(h-g))

    print(min(y))


### FIXED CODE ###

#from collections import deque
import bisect

a, b, q = [int(x) for x in input().split()]
s = [-10**12] + [int(input()) for i in range(a)] + [10**12]
t = [-10**12] + [int(input()) for i in range(b)] + [10**12]
#x = [int(input()) for i in range(q)]

#s_que = deque(s)
#s_que.appendleft(-10 ** 12)
#s_que.append(10 ** 12)

#t_que = deque(t)
#t_que.appendleft(-10 ** 12)
#t_que.append(10 ** 12)

for i in range(q):
    x = int(input())
    k = bisect.bisect_left(s, x)
    sb = s[k]
    sa = s[k-1]
    j = bisect.bisect_left(t, x)
    tb = t[j]
    ta = t[j-1]

    y = []
    for h in [sa, sb]:
        for g in [ta, tb]:
            y.append(abs(x-h) + abs(h-g))
    for h in [ta, tb]:
        for g in [sa, sb]:
            y.append(abs(x-h) + abs(h-g))

    print(min(y))
### BUGGY CODE ###

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

S_ba = []
S_ab = []
for i in range(N):
    if A[i] < B[i]: S_ba.append(B[i] - A[i])
    else: S_ab.append(A[i] - B[i])

if sum(S_ba) > sum(S_ab):
    print(-1)
    exit()
    
ans = len(S_ba)
now = 0
S_ab.sort(reverse=True)
for i in range(len(S_ab)):
    # now += A[i] - B[i]
    if sum(S_ba) <= now: break
    now += S_ab[i]
    ans += 1

print(ans)

### FIXED CODE ###

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

S_ba = []
S_ab = []
for i in range(N):
    if A[i] < B[i]: S_ba.append(B[i] - A[i])
    elif A[i] > B[i]: S_ab.append(A[i] - B[i])

if sum(S_ba) > sum(S_ab):
    print(-1)
    exit()
    
ans = len(S_ba)
now = 0
rem = sum(S_ba)
S_ab.sort(reverse=True)
for i in range(len(S_ab)):
    if rem <= now: break
    now += S_ab[i]
    ans += 1

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

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

a.sort(reverse=True)
attack = 0
#print(min(c[1],c[0]))

for i in range(min(c[1],c[0])):
  a.pop(0)

#print(a)
for i in range(c[0]-c[1]):
  attack += a[i]

print(attack)

### FIXED CODE ###

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

a.sort()
attack = 0

for i in range(c[0]-c[1]):
  attack += a[i]

print(attack)
### BUGGY CODE ###


def get_expected_value(n):

    # expected_value = 0
    # for i in range(1,n+1):
    #     expected_value += i / n
    # return expected_value
    return (1 + n) / 2

def main():
    n, k = map(int,input().split())
    pn = list(map(int,input().split()))
    expected_value_sum_max = 0
    for i in range(n-k+1):
        tmp = 0
        for j in range(k):
            tmp += get_expected_value(pn[i+j])

        if tmp > expected_value_sum_max:
            expected_value_sum_max = tmp

    print(expected_value_sum_max)

if __name__ == '__main__':
  	main()

### FIXED CODE ###

from itertools import accumulate

def main():
    N, K= map(int, input().split())
    p = list(map(int, input().split()))
    # 累積和
    p = [0] + list(accumulate(p))

    # 累積和が最大になる区間、期待値は(1+p)/2、k個分なので以下の式。
    print((max(b - a for a, b in zip(p, p[K:])) + K) / 2)

if __name__ == '__main__':
  	main()

'''
5 3
1 2 2 4 5

10 4
17 13 13 12 15 20 10 13 17 11
'''
### BUGGY CODE ###

from math import floor

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

max_x = 0

while n > 0:
    x = floor(a * (n % b) / b)

    max_x = x if x > max_x else max_x

    n -= 1

print(max_x)

### FIXED CODE ###

from math import floor

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

x = min(b - 1, n)

print(floor(a * x / b) - a * floor(x / b))
### BUGGY CODE ###

N = int(input())
A,B = [],[]
for _ in range(N-1):
    array = list(map(int,input().split()))
    A.append(array[0])
    B.append(array[1])
from collections import defaultdict as ddict
children = ddict(list)
for a,b in zip(A,B):
    children[a].append(b)
ans = ddict(int)
col = 0
for child in sorted(children.keys()):
    used = set({ans[child]})
    for j in sorted(children[child]):
        temp = min(set(range(1,max(used)+2))-used)
        ans[j] = temp
        col = max(col,temp)
        used.add(temp)
print(col)
for b in B:
    print(ans[b])

### FIXED CODE ###

N = int(input())
AB = [[]]*(N-1)
for i in range(N-1):
    AB[i] = list(map(int,input().split()))
from collections import defaultdict as ddict
from collections import deque
tree = ddict(list)
B = [0]*(N-1)
for i,ab in enumerate(AB):
    tree[ab[0]].append(ab[1])
    B[i] = ab[1]
# 各エッジの色を格納する変数の初期化
# C[0]は使わない
C = [0]*N
# 幅優先探索用のcue
Q = deque([1])
while Q:
    q = Q.popleft()
    c = 0
    for w in tree[q]:
        # 色をインクリメントした際に親の色とかぶったら更に1を加算する
        # 他は単純なインクリメント
        c += 1 + int(C[q-1] == c+1)
        # エッジの色を格納
        C[w-1] = c
        # 子供をcueに追加
        Q.append(w)
print(max(C))
for b in B:
    print(C[b-1])
### BUGGY CODE ###

n,m = map(int,input().split())
# A_2=0
# B_2=0
list_A=[]
list_B=[]
sum_num=0
for i in range(n):
    A,B = map(int,input().split())
    list_A.append(A)
    list_B.append(B)

for i in range(n):
    minj = i
    for j in range(i,n):
        if list_A[j]<list_A[minj]:
            minj=j
    hokan=list_A[i]
    list_A[i]=list_A[minj]
    list_A[minj]=hokan
    hokan_b=list_B[i]
    list_B[i]=list_B[minj]
    list_B[minj]=hokan_b
m_1=m
for i in range(n):
    m_2=m_1
    m_1=m_1-int(list_B[i])
    if m_1<0:
        sum_num=sum_num + int(list_A[i])*m_2
    else:
        sum_num=sum_num +int(list_A[i])*int(list_B[i])
    # print(sum_num)
    # print("m_1",m_1,"m_2",m_2)
    if m_1<0:
        break

print(sum_num)


### FIXED CODE ###

n,m = map(int,input().split())
# A_2=0
# B_2=0
list_A=[]
list_B=[]
sum_num=0
for i in range(n):
    A,B = map(int,input().split())
    list_A.append(A)
    list_B.append(B)


list_AB = []
for i in range(n):
    list_AB.append( (list_A[i], list_B[i]))

list_AB.sort()
list_A , list_B = zip(*list_AB)
# list_A.sort()
# list_B.sort()
# print(list_A)
# print(list_B)


m_1=m
for i in range(n):
    m_2=m_1
    m_1=m_1-int(list_B[i])
    if m_1<0:
        sum_num=sum_num + int(list_A[i])*m_2
    else:
        sum_num=sum_num +int(list_A[i])*int(list_B[i])
    #print(sum_num)
    #print("m_1",m_1,"m_2",m_2)
    if m_1<0:
        break

print(sum_num)
### BUGGY CODE ###

import numpy as np
N = int(input())
M = np.asarray(input().split(), dtype=int)
print(np.sum([np.sum(M[i+M[i]+1:]==np.arange(1,N-i-M[i])) for i in range(N)]))

### FIXED CODE ###

N = int(input())
M = list(map(int, input().split()))
L = [0] * N
R = [0] * N
for i,m in enumerate(M):
  if i+m >= N:
    continue
  L[i+m] += 1
for i,m in enumerate(M[::-1]):
  if i+m >= N:
    continue
  R[i+m] += 1
R = R[::-1]
#print(L)
#print(R)
print(sum([l*r for l,r in zip(L,R)]))
### BUGGY CODE ###

N=int(input())

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

res=1
for x in A:
	res*=x

if res>pow(10,18):
	print('-1')
else:
	print(res)

### FIXED CODE ###

N=int(input())

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

if 0 in A:
	print('0')
	exit()

res=1
for x in A:
	res*=x
	if res>pow(10,18):
		print('-1')
		exit()

else:
	print(res)
### BUGGY CODE ###

m = 10000
g = 5000
s = 1000
n, y = map(int, input().split())
if y > n * m or y < n * s:
    print("-1 -1 -1")
    exit()
if y / n == 10000:
    print(n, "0 0")
    exit()
elif y / n == 5000:
    print("0", n, "0")
    exit()
elif y / n == 1000:
    print("0 0", n)
    exit()
if y / n > 7500:
    for i in range(n):
        for j in range(n - i+1):
            for h in range(n - j+1):
                if i * s + j * g + h * m == y and i + j + h == n:
                    print(h, j, i)
                    exit()
    else:
        print("-1 -1 -1")
elif y/n > 3000:
    for i in range(n):
        for j in range(n - i+1):
            for h in range(n - j+1):
                if i * s + j * m + h * g == y and i + j + h == n:
                    print(j, h, i)
                    exit()
    else:
        print("-1 -1 -1")
else:
    for i in range(n):
        for j in range(n-i+1):
            for h in range(n-j+1):
                if i*m+j*g+h*s==y and i+j+h == n:
                    print(i, j, h)
                    exit()
    else:
        print("-1 -1 -1")

### FIXED CODE ###

n, y = map(int, input().split())
for i in range(n + 1):
    for j in range(n - i + 1):
        if i * 10000 + j * 5000 + (n - i - j) * 1000 == y:
            print(i, j, n - i - j)
            exit()
print("-1 -1 -1")
### BUGGY CODE ###

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

maxx = xlist[-1] if xlist[-1] > a else a
# dp[j][k][s]: x_1...x_jまでのなかからk枚選んで合計をsにする総数
dp = [[[0 for _ in range(maxx * n + 1)] for _ in range(n + 1)] for _ in range(n + 1)]

dp[0][0][0] = 1  # 0枚選んで合計を0にするのは1通り
for j in range(n + 1):
  for k in range(n + 1):
    for s in range(maxx * k + 1):
      if j >= 1:  # x_0は選ばないのと同じなので0のまま更新しない
        if s < xlist[j-1]:
          dp[j][k][s] = dp[j-1][k][s]
        elif k >= 1 and s >= xlist[j-1]:
          dp[j][k][s] = dp[j-1][k][s] + dp[j-1][k-1][s-xlist[j-1]]

print(sum(dp[n][k][k*a] for k in range(1, n + 1)))

### FIXED CODE ###

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

maxx = max(x)
maxx = max(maxx, a)
# dp[j][k][s] : j枚目までからk枚選んで合計をsにする場合の数
dp = [[[0 for _ in range(maxx * n + 1)] for _ in range(n + 1)] for _ in range(n + 1)]
dp[0][0][0] = 1

for j in range(n + 1):
    for k in range(j + 1):
        for s in range(maxx * k + 1):
            if j >= 1 and s < x[j - 1]:
                dp[j][k][s] = dp[j - 1][k][s]
            elif j >= 1 and k >= 1 and s >= x[j - 1]:
                dp[j][k][s] = dp[j - 1][k][s] + dp[j - 1][k - 1][s - x[j - 1]]

ans = 0
for k in range(1, n + 1):
    ans += dp[n][k][k*a]
print(ans)
### BUGGY CODE ###

from sys import stdin
input()
a=map(int,stdin.readline().rstrip().split())
b=int(input())
for i in range(b):
  n,m=map(int,stdin.readline().rstrip().split())
  a=[m if i==n else i for i in a]
  print(sum(a))

### FIXED CODE ###

from sys import stdin
input=stdin.readline
input()
a=list(map(int,input().split()))
ans=sum(a)
b=[0]*(10**5+1)
for i in a:
  b[i]+=1
c=int(input())
for i in range(c):
  n,m=map(int,input().split())
  if b[n]>0:
    x=b[n]
    if x>0:
      b[m]+=x
      b[n]=0
      ans+=(m-n)*x
  print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
def main():
    _ = int(input())
    A = [int(x) for x in input().split()]
    mod = 10 ** 9 + 7

    ans = 0
    for index, i in enumerate(A):
        ans += i * sum(A[index + 1:]) % mod
    print(ans % mod)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
def main():
    _ = int(input())
    A = [int(x) for x in input().split()]
    mod = 10 ** 9 + 7

    lst = [sum(A)]
    for j in A:
        lst.append(lst[-1] - j)
    ans = 0
    for index, i in enumerate(A):
        ans += i * lst[index + 1] % mod
    print(ans % mod)


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

from functools import lru_cache

N,W=map(int,input().split())
weights,profits = [0]*N, [0]*N

@lru_cache(None)
def knapsack_recursive(capacity, currentIndex):
 
  # base checks
    if capacity <= 0 or currentIndex >= len(profits): return 0

    profit1 = 0
    if weights[currentIndex] <= capacity:
        profit1 = profits[currentIndex] + knapsack_recursive(capacity - weights[currentIndex], currentIndex + 1)
 
  # recursive call after excluding the element at the currentIndex
    profit2 = knapsack_recursive(capacity, currentIndex + 1)
 
    return max(profit1, profit2)
  
def main():

    for i in range(N):
        weights[i],profits[i] = map(int,input().split())
    res = knapsack_recursive(W, 0)
 
    print(res)
if __name__ == "__main__":
	main()

### FIXED CODE ###

def main():
  n, w = [int(e) for e in input().split()]
  t = [-1 for i in range(w + 1)]
  t[w] = 0
  for _ in range(n):
    nw, nv = [int(e) for e in input().split()]
    for i in range(nw, w + 1):
      if t[i] == -1:
        continue
      if t[i - nw] < t[i] + nv:
        t[i - nw] = t[i] + nv
  print(max(t))
main()
### BUGGY CODE ###

n, k = map(int, input().split())
p = list(map(lambda x: int(x) - 1, input().split()))
c = list(map(int, input().split()))

def solve(u):
    ans = c[p[u]]
    pos = [-1] * n
    score = [-1] * n
    tk = k
    cur_pos, cur_sum = 0, 0
    while tk > 0 and pos[p[u]] == -1:
        u = p[u]
        cur_pos += 1
        cur_sum += c[u]
        ans = max(ans, cur_sum)
        pos[u] = cur_pos
        score[u] = cur_sum
        tk -= 1
    cycle_length = cur_pos - pos[p[u]] + 1
    cycle_sum = cur_sum - score[p[u]] + c[p[u]]
    # print(cur_sum, ans, cycle_length, cycle_sum) 
    
    if cycle_sum <= 0:
        return ans
    
    cur_sum += cycle_sum * (tk // cycle_length)
    ans = max(ans, cur_sum)
    tk %= cycle_length
    while tk > 0:
        u = p[u]
        cur_sum += c[u]
        ans = max(ans, cur_sum)
        tk -= 1
    return ans

# print(list((solve(i), i) for i in range(n))) 
print(max(solve(i) for i in range(n)))
    
    


### FIXED CODE ###

n, k = map(int, input().split())
p = list(map(lambda x: int(x) - 1, input().split()))
c = list(map(int, input().split()))
    
visited = [False] * n
ans = max(c)

for i in range(n):
    if visited[i]:
        continue
    arr = []
    u = i
    while not visited[u]:
        arr.append(c[u])
        visited[u] = True
        u = p[u]
    s = sum(arr) * (k // len(arr))
    rem = k % len(arr)
    if k // len(arr) >= 1:
        s -= sum(arr)
        rem += len(arr)
        
    arr += arr + arr
    pref_sum = [0]
    for i in arr:
        pref_sum.append(pref_sum[-1] + i)
    # print(pref_sum, s, rem) 
            
    for f in range(len(arr) // 2):
        # ans = max(ans, s + sum(arr[f:f + rem])) 
        for g in range(f + 1, len(pref_sum)):
            if g - f <= k:
                ans = max(ans, pref_sum[g] - pref_sum[f])
            if g - f <= rem:
                ans = max(ans, s + pref_sum[g] - pref_sum[f])
print(ans)
### BUGGY CODE ###

A = sorted( [input()[::-1] for i in range(5)] )
while (A[0][0] == "0"):
  tmp = A.pop(0)
  A.append(tmp)

A = [int(a[::-1]) for a in A][::-1]

def roundUp(n):
  return n if n%10==0 else n + (10-n%10)

print(sum([roundUp(A[i]) for i in range(4)]) + A[4])


### FIXED CODE ###

A = sorted( [input()[::-1] for i in range(5)] )
c = 0
while (A[0][0] == "0" and c<5):
  tmp = A.pop(0)
  A.append(tmp)
  c+=1

A = [int(a[::-1]) for a in A][::-1]

def roundUp(n):
  return n if n%10==0 else n + (10-n%10)

print(sum([roundUp(A[i]) for i in range(4)]) + A[4])
### BUGGY CODE ###

def cns(ls,m,sm):
    global s, n, count
    if m == n:
        if sm == s:
            count += 1
        return
    else:
        l = len(ls)
        for i in range(l):
            rls = ls[:]
            k = rls.pop(i)
            dammy =  cns(rls,m+1,sm+(m+1)*k)
        return


ls = [0,1,2,3,4,5,6,7,8,9]
while True:
    n, s = map(int, raw_input().split())
    count = 0
    dammy = cns(ls,0,0)
    print count

### FIXED CODE ###

def mxmn(ls,m):
	global n
	s1,s2 = 0, 0
	for i in range(m):
		s1 += (n-i)*ls[-i-1]
		s2 += (n-i)*ls[i]
	return s1,s2

def f(ls,m,s):
	global n
	count = 0
	if m > 0:
		mx,mn = mxmn(ls,m)
		if mx < s or mn > s: return 0
		elif mx == s or mn == s: return 1
		for i in range(len(ls)):
			lls = ls[:]
			a = (n-m+1)*lls.pop(i)
			if s-a < 0:	break
			else: count += f(lls,m-1,s-a)
		return count
	else:
		return 1 if s == 0 else 0
			
ls = [i for i in range(10)]
while True:
	try:
		n,s = map(int, raw_input().split())
		print f(ls,n,s)
	except:
		break
### BUGGY CODE ###

class AC:
    @staticmethod
    def inputStr(char):
        return input().split(char)
    
    @staticmethod
    def inputInt(char):
        a = input().split(char)
        for i in range(len(a)):
            a[i] = int(a[i])
        return a

inp = AC.inputInt(" ")
A = inp[0]
B = inp[1]
K = inp[2]

for i in range(K):
    if A > 0 :
        A = A-1
    elif B > 0 :
        B = B-1
print(str(A) + " " + str(B))

### FIXED CODE ###

A,B,K = map(int,input().split(" "))
if A+B < K:print(0,0)
elif A > K:print(A-K,B)
elif A  <= K:print(0,A+B-K)
# Kenparさん、写経させていただきました。ありがとうございます。
# こんな解法があったなんて・・・
### BUGGY CODE ###

import sys

def wfs(queue, S, step, goal):
    next_queue = []
    for q in queue:
        if q == goal:
            return step+1

        i, j = q[0], q[1]
        S[i][j] = '#'

        if S[i+1][j] == '.':
            next_queue.append([i+1, j])
        if S[i-1][j] == '.':
            next_queue.append([i-1, j])
        if S[i][j+1] == '.':
            next_queue.append([i, j+1])
        if S[i][j-1] == '.':
            next_queue.append([i, j-1])

    if len(next_queue) == 0:
        return -1
    else:
        return wfs(next_queue, S, step+1, goal)


def main():
    input = sys.stdin.readline
    H, W = map(int, input().split())
    S = []
    init = 0
    for _ in range(H):
        s = [c for c in input().strip()]
        init += sum([c == '#' for c in s])
        S.append(['#'] + s + ['#'])
    S = [['#'] * (W+2)] + S + [['#'] * (W+2)]
    minstep = wfs([[1,1]], S, 0, [H, W])
    if minstep == -1:
        print(-1)
    else:
        print(H*W - minstep - init)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

def wfs(queue, S, step, goal):
    next_queue = set()
    for q in queue:
        if q == goal:
            return step+1

        i, j = q[0], q[1]
        S[i][j] = '#'

        if S[i+1][j] == '.':
            next_queue.add((i+1, j))
        if S[i-1][j] == '.':
            next_queue.add((i-1, j))
        if S[i][j+1] == '.':
            next_queue.add((i, j+1))
        if S[i][j-1] == '.':
            next_queue.add((i, j-1))

    if len(next_queue) == 0:
        return -1
    else:
        next_queue = list(set(next_queue))
        return wfs(next_queue, S, step+1, goal)


def main():
    input = sys.stdin.readline
    H, W = map(int, input().split())
    S = []
    black = 0
    for _ in range(H):
        s = [c for c in input().strip()]
        black += sum([c == '#' for c in s])
        S.append(['#'] + s + ['#'])
    S = [['#'] * (W+2)] + S + [['#'] * (W+2)]
    init = set([(1, 1)])
    minstep = wfs(init, S, 0, (H, W))
    if minstep == -1:
        print(-1)
    else:
        print(H*W - minstep - black)


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

import heapq

def dijkstra_heap(s,edge):
    
    #始点sから各頂点への最短距離
    d = [10**10] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

################################
N,X,Y = map(int,input().split())
n = N
w = N

edge = tuple([] for i in range(n))
#edge[i] : iから出る道の[重み,行先]の配列
for i in range(w):
    if i == 0:
        edge[i].append([1,i+1])
    elif i == w-1:
        edge[i].append([1,i-1])
    else:
        edge[i].append([1,i+1])
        edge[i].append([1,i-1])
edge[X-1].append([1,Y-1])
edge[Y-1].append([1,X-1])

ans = [0]*(N+1)
tmp = []
for i in range(N):
    tmp.append(dijkstra_heap(i,edge)[i+1:])

for i in range(N):
    for j in tmp[i]:
        ans[j] += 1

for i in range(1,N):
    print(ans[i])

### FIXED CODE ###

import heapq

def dijkstra_heap(s,edge):
    #始点sから各頂点への最短距離
    d = [10**10]*n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

################################
N,X,Y = map(int,input().split())
n = N
w = N

edge = tuple([] for i in range(n))
#edge[i] : iから出る道の[重み,行先]の配列
for i in range(w):
    if i == 0:
        edge[i].append([1,i+1])
    elif i == w-1:
        edge[i].append([1,i-1])
    else:
        edge[i].append([1,i+1])
        edge[i].append([1,i-1])
edge[X-1].append([1,Y-1])
edge[Y-1].append([1,X-1])

ans = [0]*(N+1)
tmp = []
for i in range(N):
    tmp.append(dijkstra_heap(i,edge)[i+1:])

for i in range(N):
    for j in tmp[i]:
        ans[j] += 1

for i in range(1,N):
    print(ans[i])
### BUGGY CODE ###

import sys
input = sys.stdin.buffer.readline
N, C = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = [[0] * (C + 1) for _ in range(N)]
mod = 10 ** 9 + 7
for i in range(N):
  c[i][0] = b[i] - a[i] + 1
for i in range(N):
  for k in range(a[i], b[i] + 1):
    t = 1
    for j in range(C):
      t *= k
      t %= mod 
      c[i][j + 1] += t
      c[i][j + 1] %= mod
dpx = [0] * (C + 1)
dpy = [0] * (C + 1)
dpx[0] = 1
for i in range(N):
  if i % 2:
    dpx = [0] * (C + 1)
  else:
    dpy = [0] * (C + 1)
  for j in range(C + 1):
    for k in range(j, C + 1):
      if i % 2:
        dpx[k] += dpy[j] * c[i][k - j]
        dpx[k] %= mod
      else:
        dpy[k] += dpx[j] * c[i][k - j]
        dpy[k] %= mod
if N % 2:
  print(dpy[-1] % mod)
else:
  print(dpx[-1] % mod)

### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
N, C = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = [0] * (N * (C + 1))
mod = 10 ** 9 + 7
for i in range(N):
  c[i * (C + 1)] = b[i] - a[i] + 1
for i in range(N):
  for k in range(a[i], b[i] + 1):
    t = 1
    for j in range(C):
      t *= k
      t %= mod 
      c[i * (C + 1) + j + 1] += t
      c[i * (C + 1) + j + 1] %= mod
dpx = [0] * (C + 1)
dpy = [0] * (C + 1)
dpx[0] = 1
for i in range(N):
  if i % 2:
    dpx = [0] * (C + 1)
  else:
    dpy = [0] * (C + 1)
  for j in range(C + 1):
    for k in range(j, C + 1):
      if i % 2:
        dpx[k] += dpy[j] * c[i * (C + 1) + k - j]
        dpx[k] %= mod
      else:
        dpy[k] += dpx[j] * c[i * (C + 1) + k - j]
        dpy[k] %= mod
if N % 2:
  print(dpy[-1] % mod)
else:
  print(dpx[-1] % mod)