Harryxun/stf_run huggingface dataset:
from math import factorial
from copy import copy

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

all_patterns = 1
start, end = None, None
for m_i in range(M + 1):
    if m_i < M:
        a_i = int(input())
    if m_i == 0:
        start = 0
        end = a_i - 1
        next_start = a_i + 1
    elif m_i == M:
        start = copy(next_start)
        end = N
    else:
        start = copy(next_start)
        end = a_i - 1
        next_start = a_i + 1
    passdiff = end - start
    num_2 = passdiff // 2
    residue = passdiff % 2

    tmp_patterns_for_range = 0
    for num2to1 in range(num_2 + 1):
        add_n_1 = num2to1 * 2
        tmp_num2 = num_2 - num2to1
        tmp_n_pattern = \
            factorial(tmp_num2 + add_n_1 + residue) \
            // factorial(tmp_num2) \
            // factorial(add_n_1 + residue)
        tmp_patterns_for_range += tmp_n_pattern
    all_patterns *= tmp_patterns_for_range

print(all_patterns % 1000000007)


### FIXED CODE ###

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

if M == 0:
    alist = set()
else:
    alist = set(int(input()) for _ in range(M))

dp = [0] * (N + 1)
dp[0] = 1
dp[1] = 1 if 1 not in alist else 0

MOD = 10**9 + 7
for i in range(2, N + 1):
    if i in alist:
        continue
    dp[i] = (dp[i - 1] + dp[i - 2]) % MOD

print(dp[N])
x = int(input(""))
l = list()
flag = 0
for i in range(0, x):
    temp = input("")
    if temp in l:
        flag = 1
    if temp not in l:
        l.append(temp)
if flag == 1:
    print("NO")
else:
    print("YES")



### FIXED CODE ###

x = int(input(""))
l = list()
flag = 0
arr = [int(x) for x in input().split()]
arr2=set(arr)
l=len(arr)
l2=len(arr2)
if l!=l2:
    print("NO")
else:
    print("YES")
A,B=map(int,input().split())
if A<=2*B:
  print(0)
else A>2*B
  print(A-(2*B))

### FIXED CODE ###

A,B=map(int,input().split())
if A<=2*B:
  print(0)
else :
  print(A-(2*B))
# -*- coding: utf-8 -*-

import sys
import math

def parse_input(lines_as_string = None):

    lines = []
    if lines_as_string is None:
        for line in sys.stdin:
            lines.append(line)
    else:
        lines = [e for e in lines_as_string.split("\n")][1:-1]

    # 出力
    nm = lines[0].split(" ")
    n = int(nm[0])

    rows = []
    for i in range(1, 2):
        rows.append([int(e) for e in lines[i].split(" ")])

    return (n, rows[0])

def solve(n, monsters):

    g = monsters[0]
    for i in range(1, n):
        g = math.gcd(g, monsters[i])


    return g

def main():

    n, m, rows = parse_input()
    print("%d" % solve(n, m, rows))

if __name__ == '__main__':

    main()


### FIXED CODE ###

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

import sys

def gcd(a, b):

    c = min(a, b)
    d = max(a, b)
    r = 0    
    while True:
        r = d % c
        if r == 0:
            break
        d = c
        c = r

    return c

def parse_input(lines_as_string = None):

    lines = []
    if lines_as_string is None:
        for line in sys.stdin:
            lines.append(line)
    else:
        lines = [e for e in lines_as_string.split("\n")][1:-1]

    # 出力
    nm = lines[0].split(" ")
    n = int(nm[0])

    rows = []
    for i in range(1, 2):
        rows.append([int(e) for e in lines[i].split(" ")])

    return (n, rows[0])

def solve(n, monsters):

    g = monsters[0]
    for i in range(1, n):
        g = gcd(g, monsters[i])


    return g

def main():

    print("%d" % solve(*parse_input()))

if __name__ == '__main__':

    main()
a = []
a = input().split()

A = a[0]
B = a[1]

if A > 13 :
  print(B)
if A >= 6 and A <= 12 :
  print(B / 2)
if A <= 5 :
  print(0)


### FIXED CODE ###

a = []
a = input().split()

A = int(a[0])
B = int(a[1])

if A >= 13 :
  print(B)
if A >= 6 and A <= 12 :
  print(int(B / 2))
if A <= 5 :
  print(0)
A,B,K = map(int, input().split())
L = list(range(A,B+1))
left = L[:K]
right = L[-K:]
N = list(set(left + right))
N = sorted(N)
for i in range(len(N)):
  print(N[i])

### FIXED CODE ###

a,b,k = map(int,input().split())
if (b-a+1) >= (2*k):
  for i in range(k):
    print(a+i)
  for i in reversed(range(0,k)):
    print(b-i)
else:
  for i in range(a,b+1):
    print(i)
N, Q = [int(item) for item in input().split()]

tree_list = [input().split() for _ in range(1,N)]

query_list = [input().split() for _ in range(Q)]
query_list_int = [[int(k) for k in i]  for i in query_list]

val_list = [0 for _ in range(N)]
linkde_node_list = [[] for _ in range(N)]

# 無向グラフのリンクを作成
for a, b in tree_list:
    linkde_node_list[int(a) -1].append(int(b) - 1)
    linkde_node_list[int(b) -1].append(int(a) - 1)


for index, val in query_list_int:
    val_list[index-1] += val

def dfs(node_index, pairent_index):
    for child in linkde_node_list[node_index]:

        if child == pairent_index:
            continue

        val_list[child] += val_list[node_index]
        dfs(child, node_index)

    return val_list

res = dfs(0, -1) #0はルート、-1は親を持っていない事

for i in res:
    print(i)

### FIXED CODE ###

N, Q = [int(item) for item in input().split()]

tree_list = [input().split() for j in range(1, N)]

query_list = [input().split() for k in range(Q)]
query_list_int = [[int(k) for k in i] for i in query_list]

val_list = [0 for _ in range(N)]

linked_node_list = [[] for _ in range(N)]

for a, b in tree_list:
    a, b = int(a)-1, int(b) -1
    linked_node_list[a].append(b)
    linked_node_list[b].append(a)


for index, val in query_list_int:
    val_list[index-1] += val

stack = [0]
parent = [0] * (N+1)

while True:
    v=stack.pop()
    for child in linked_node_list[v]:
        if child != parent[v]:
            parent[child] = v
            stack.append(child)
            val_list[child] += val_list[v]
    if not stack:
        break

print(*val_list)
from scipy.misc import comb
x, y = map(int, input().split())
t = (2*y-x)/3
s = (2*x-y)/3
if not t.is_integer() or t<0 or not s.is_integer() or s<0:
  print(0)
else:
  print(int(comb(s+t, min(s, t))%1000000007))

### FIXED CODE ###

from scipy.misc import comb
def modpow(a, n, p):
  if n == 1:
    return a % p 
  elif n % 2 == 1:
    return a * modpow(a, n-1, p) % p
  else:
    return modpow(a, n//2, p) **2 % p
x, y = map(int, input().split())
t = (2*y-x)/3
s = (2*x-y)/3
if not t.is_integer() or t<0 or not s.is_integer() or s<0:
  print(0)
else:
  t = int(t)
  s = int(s)
  bunsi = 1
  for i in range(s+t-s+1, s+t+1):
    bunsi = bunsi * i % 1000000007
  bunbo = 1
  for i in range(1, s+1):
    bunbo = bunbo * i % 1000000007
  ans = bunsi * modpow(bunbo, 1000000007-2, 1000000007) % 1000000007
  print(ans)
import math
n = int(input())
t = map(int, input())
bottle_neck = min(t)
ti = math.ceil(n/bottle_neck)
print(ti+4)

### FIXED CODE ###

import math
n = int(input())
t=[]
for i in range(5):
    t.append(int(input()))
bottle_neck = min(t)
ti = math.ceil(n/bottle_neck)
print(ti + 4)
import math
A,B,C,D = map(int, input().split())

n_c = 0
n_d = 0
n_cd = 0
# for i in range(A,B+1):
#     if(i % C == 0):
#         n_c = i // C
#     n_d = i // D
#     n_cd = i//(C*D)

def lcm(x,y):
    return (x*y) // math.gcd(x,y)

n_c = B//C - A//C
n_d = B//D - A//D
CD = lcm(C,D)
n_cd = B//(CD) - A//(CD)

if(A%C == 0):
    n_c += 1
if(A%D==0):
    n_d += 1
if(A%CD==0):
    n_cd += 1


if (max(C,D)%min(C,D) == 0):
    ans = (B-A+1) - max(n_c, n_d)
else:
    ans = (B-A + 1) - (n_c + n_d - n_cd)

# print(n_c)
# print(n_d)
# print(n_cd)

print(ans)




### FIXED CODE ###

import fractions
A,B,C,D = map(int, input().split())

# n_c = 0
# n_d = 0
# n_cd = 0
# for i in range(A,B+1):
#     if(i % C == 0):
#         n_c = i // C
#     n_d = i // D
#     n_cd = i//(C*D)

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

n_c = B//C - A//C
n_d = B//D - A//D
CD = lcm(C,D)
n_cd = B//(CD) - A//(CD)

if(A%C == 0):
    n_c += 1
if(A%D==0):
    n_d += 1
if(A%CD==0):
    n_cd += 1


if (max(C,D)%min(C,D) == 0):
    ans = (B-A+1) - max(n_c, n_d)
else:
    ans = (B-A + 1) - (n_c + n_d - n_cd)

# print(n_c)
# print(n_d)
# print(n_cd)

print(ans)
import math
from functools import reduce

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

N,X = map(int,input().split())
x = list(map(int,input().split()))

y = [0] * N
for i in range(N):
    y[i] = abs(X-x[i])

print(gcd_list(y))


### FIXED CODE ###

import fractions

N,X = map(int,input().split())
x = list(map(int,input().split()))

y = [0] * N
for i in range(N):
    y[i] = abs(X-x[i])

ans = y[0]
for i in range(1,N):
    ans = fractions.gcd(ans,y[i])
print(ans)
# coding:utf-8
n, k = map(int, input().split())
h = [int(input()) for _ in range(n)]
h.sort()
ans = h[0]

print(min(h[i + k - 1] - h[i] for i in range(n - k + 1))


### FIXED CODE ###

# coding:utf-8
n, k = map(int, input().split())
h = [int(input()) for _ in range(n)]
h.sort()
ans = h[0]

print(min(h[i + k - 1] - h[i] for i in range(n - k + 1)))
n = int(input())
b = list(map(int,input().split()))

a = list()
ans = 0
a.append(b[0])

for i in range(n-2):
  a.append(b[i])
  if(b[i+1]<b[i]):
    a.pop(i+1)
    a.append(b[i+2])

j = max(b[-1],b[-2])
a.append(j)

for i in range(n):
  ans += a[i]

print(ans)


### FIXED CODE ###

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

a = list()
ans = 0
a.append(b[0])

for i in range(n-2):
  j = min(b[i],b[i+1])
  a.append(j)

a.append(b[-1])

for i in range(n):
  ans += a[i]

print(ans)
nk = input()
nk = nk.split()
n = int(n[0])
k = int(n[1])
trees = []
for i in range(n):
  trees.append(int(input()))
trees.sort()
minimum = 1000000000
i = 0
while i<=n-k:
  if trees[i+k-1]-trees[i]<minimum:
    minimum = trees[i+k-1]-trees[i]
  i+=1
print(minimum)

### FIXED CODE ###

nk = input()
nk = nk.split()
n = int(nk[0])
k = int(nk[1])
trees = []
for i in range(n):
  trees.append(int(input()))
trees.sort()
minimum = 1000000000
i = 0
while i<=n-k:
  if trees[i+k-1]-trees[i]<minimum:
    minimum = trees[i+k-1]-trees[i]
  i+=1
print(minimum)
n=int(input())
l=list(map(int,str(bin(n))[2:]))
for i in range(1,len(l)+3): 
    if l[-i] == 2:
        l[-i] = 0
        try:
            l[-(i+1)]+=1
        except:
            l.insert(0,1)
    if i%2==0 and l[-i]==1:
        try: 
            l[-(i+1)]+=1
        except:
            l.insert(0,1)
s = ''.join([str(x) for x in l])
print(s)

### FIXED CODE ###

n=int(input())
flg = 0
if n < 0:
    n *= -1
    flg = 1
l=list(map(int,str(bin(n))[2:]))
for i in range(1,len(l)+3): 
    try:
        if l[-i] == 2:
            l[-i] = 0
            if i == len(l):
                l.insert(0,1)
            else:
                l[-(i+1)]+=1
        if i%2==flg and l[-i]==1:
            if i == len(l):
                l.insert(0,1)
            else:
                l[-(i+1)]+=1
    except:
        pass
s = ''.join([str(x) for x in l])
print(s)
N = int(input())
A = list(map(int, input().split()))

exec_count = 0

while True:
  exist_odd = False
  
  for i in range(N):
    if A[i]%2 == 1:
      exist_odd = True
  if exist_odd == True:
    break
  else:
    exec_count += 1
    for i in range(N):
      A[i] = A[i]/2
      
print(exec_count)

### FIXED CODE ###

a = input()

snum = 0
if a[0] == '1':
  snum += 1
if a[1] == '1':
  snum += 1
if a[2] == '1':
  snum +=1

print(snum)
N = int(input())
P = list(map(int, input().split()))

dist = [P[i-1] - i for i in range(1, N+1)]

count = 0

for i in range(N):
    if dist[i] == 0:
        count += 1
        dist[i] -= 1
        dist[i+1] += 1
    elif i == N-1 and dist[i+1] == 0:
        count += 1
        dist[i] -= 1
        dist[i+1] += 1
        
print(count)

### FIXED CODE ###

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

dist = [P[i-1] - i for i in range(1, N+1)]

count = 0

for i in range(N):
    if dist[i] == 0:
        count += 1
        if i < N-1:
            dist[i] -= 1
            dist[i+1] += 1
        else: # i == N-1
            dist[i] += 1
            dist[i-1] -= 1
    
print(count)
n,m=map(int,input().split())
s=[]
for i in range(m):
    s.append(int(input()))
l=[1]
if s[0]!= 1:l.append(1)
else:l.append(0)
for i in range(2,n+1):
    if i in s:num=0
    else:num = (l[i-2]+l[i-1])%1000000007
    l.append(num)
print(l)

### FIXED CODE ###

n,m = map(int,input().split())
s=set([int(input()) for i in range(m)])
l=[1]+[0]*n
INF=1000000007
if n ==1:
    print(1)
    exit()
if len(s)!=0 and 1 in s:l[1]=0
else:l[1]=1
for i in range(2,n+1):
    if i in s: l[i]=0
    else:l[i] = (l[i-2]+l[i-1])%INF
print(l[-1])
n = int(input())
l = list(map(int,input().split()))
m = max(l)
s = sum(l)
if m < s:
  print(Yes)
else:
  print(No)

### FIXED CODE ###

n = int(input())
l = list(map(int,input().split()))
m = max(l)
s = sum(l)-m
if m < s:
  print("Yes")
else:
  print("No")
n,a=map(int, input().split())
x=list(map(int, input().split()))
x=[i-a for i in x]
d={0:1}
for i in x:
    for j,k in list(d.items()):
        d[i+.j]=d.get(i+j,0)+k
print(d[0]-1)
#sample code

### FIXED CODE ###

n,a=map(int, input().split())
x=list(map(int, input().split()))
x=[i-a for i in x]
d={0:1}
for i in x:
    for j,k in list(d.items()):
        d[i+j]=d.get(i+j,0)+k
print(d[0]-1)
#sample code.
import math
H, W, M = map(int, input().split())

if H <= W:
    for i in range(1, H + 1):
        if W * i => M:
            print(i)

elif:
    for k in range(1, W + 1):
        if H * k => M:
            print(k)

### FIXED CODE ###

H = int(input())
W = int(input())
M = int(input())

if H <= W:
    for i in range(1, H + 1):
        if W * i >= M:
            print(i)
            break
            
else:
    for k in range(1, W + 1):
        if H * k >= M:
            print(k)
            break
import sys
# 整数の入力
N,M=list(map(int, input().split()))
p=[]
q=0
count=0
for i in range(0,M):
  p.append(list(map(int, input().split())))
for i in range(0,M):
  q+=p[i][0]-p[i][1]
if q%2==1:
  print("NO")
else:
  for j in range(1,M,int(M/10)):
    for i in range(0,M):
      if p[i][0]==j or p[i][1]==j:
        count+=1
    if count%2==1:
      print("NO")
      sys.exit()
  else: 
    print("YES")

### FIXED CODE ###

import sys
# 整数の入力
N,M=list(map(int, input().split()))
p=[]
for i in range(0,N):
  p.append(0)
for i in range(0,M):
  count=list(map(int, input().split()))
  p[count[0]-1]+=1
  p[count[1]-1]+=1
for i in range(0,M):
  if p[i]%2==1:
    print("NO")
    sys.exit()
print("YES")
A = input()
B = input()
C = input()
s = A[0]
while(len(A) != 0) and  (len(B) != 0) and (len(B) != 0):
    if s == 'a':
      s = A[0]
      A = A[1:]
    elif s == 'b':
      s = B[0]
      B = B[1:]
    else:
      s = C[0]
      C = C[1:]
print(s.upper())

### FIXED CODE ###

A = input() + ' '
B = input() + ' '
C = input() + ' '
s = A[0]
while(len(A) != 0 and s != ' ' ) and  (len(B) != 0 and s != ' ') and (len(B) != 0 and s != ' '):
  if s == 'a':
    s = A[0]
    A = A[1:]
  elif s == 'b':
    s = B[0]
    B = B[1:]
  else:
    s = C[0]
    C = C[1:]
  if s == ' ':
    break;
  else:
    p = s
print(p.upper())
import math
n, k = map(int, input().split())
a = int(n/k)
if(a < 2):
    b = 0
else:
    b = math.factorial(a) // (math.factorial(a - 2) * 2)
if(a < 3):
    c = 0
else:
    j = math.factorial(a-3)
    c = math.factorial(a) // j * 6
ans = a + b * 6 + c * 6
if(k % 2 == 0):
    t = int(k / 2)
    if(a * k + t > n):
      ans = ans * 2
    else:
      d = a + 1
      if(d < 2):
          e = 0
      else:
          e = math.factorial(d) // j * 2
      if(d < 3):
          f = 0
      else:
          f = math.factorial(d) // (math.factorial(d - 3) * 6)
      ans += (d + e * 6 + f * 6)
print(ans)

### FIXED CODE ###

import math

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

ans = int(math.pow(int(n/k),3))

if(k % 2 == 0):
  m = int( (n+int(k/2))/ k )
  ans += int(math.pow(m,3))

print(ans)
N, M = map(int, input().split())
XYZ = [list(map(int, input().split())) for i in range(M)]

graph = [[]for i in range(N + 1)]

seen = [0] * (N + 1)

for X, Y, Z in XYZ:
    graph[X].append(Y)
    graph[Y].append(X)


def dfs(a):
    if seen[a] == 1:
        return
    else:
        seen[a] = 1
        for i in graph[a]:
            dfs(i)


ans = 0

for i in range(1, N + 1):
    if seen[i] == 1:
        continue
    else:
        dfs(i)
        ans += 1

print(ans)


### FIXED CODE ###

import sys

# 再帰上限の変更(デフォルトは1000)
# 大きくしすぎるとREするらしい
sys.setrecursionlimit(10 ** 9)

N, M = map(int, input().split())
XYZ = [list(map(int, input().split())) for i in range(M)]

# XがわかればYがわかるので、あるAiがわかったときどこまでわかるか?をグラフにしてDFSで探索

graph = [[]for i in range(N + 1)]

seen = [0] * (N + 1)

for X, Y, Z in XYZ:
    graph[X].append(Y)
    graph[Y].append(X)


def dfs(a):
    if seen[a] == 1:
        return
    else:
        seen[a] = 1
        for i in graph[a]:
            dfs(i)


ans = 0

for i in range(1, N + 1):
    if seen[i] == 1:
        continue
    else:
        dfs(i)
        ans += 1

print(ans)
N = int(input())
money =0
for i in range(N):
  a,b = input().split()
  if b == 'JPY':
    money += int(a)
  else:
    money += int(a)*380000.0
print(money)

### FIXED CODE ###

N = int(input())
money =0
for i in range(N):
  a,b = input().split()
  if b == 'JPY':
    money += int(a)
  else:
    money += float(a)*380000.0
print(money)
s=int(input())
t=[]
for i in range(N):
    u,l = map(int,input().split())
    t.append((u-l,u+l-1))
t.sort(key=lambda x: x[1])
d=-10*10
ans=0
for i in range(s):
  a=t[i][0]-t[i][1]
  if d<a:
    ans+=1
    d=a+2*t[i][1]-1
print(ans)

### FIXED CODE ###

s=int(input())
t=[]
for i in range(s):
    u,l=map(int,input().split())
    t.append((u-l,u+l-1))
t.sort(key=lambda x: x[1])
d=-10**10
ans=0
for i in range(s):
  if d<t[i][0]:
    ans+=1
    d=t[i][1]
print(ans)
import itertools
N,M=map(int,input().split())
kslist=[(list(map(int,input().split()))) for i in range(M)]
plist=list(map(int,input().split()))
ls=list((itertools.product(range(2),repeat=N)))
n=0
for tup in ls:
    if [tup[kslist[j][k in range(1,kslist[j][0]+1)]-1]%2 for j in range(M)]==plist:
        n+=1
print(n)     

### FIXED CODE ###

import itertools
N,M=map(int,input().split())
kslist=[(list(map(int,input().split()))) for i in range(M)]
plist=list(map(int,input().split()))
ls=list((itertools.product(range(2),repeat=N)))
n=0
for tup in ls:
    n+=1
    for j in range(M):
        sum1=0
        for k in range(1,kslist[j][0]+1):
            sum1+=tup[kslist[j][k]-1]
        if sum1%2!=plist[j]:
            n=n-1
            break
print(n)
def main():
    import sys
    from collections import deque
    input = sys.stdin.readline
    N = int(input())
    color = [-1] * N
    color[0] = 0
    uvw = []
    edge = [[]for _ in range(N)]
    # append=uvw.append
    for i in range(N-1):
        ui, vi, wi = map(int, input().split())
        ui -= 1
        vi -= 1
        edge[ui].append((vi, wi))
        edge[vi].append((ui, wi))
    stack = [0]
    for i in range(N):
        tmp = deque()
        while stack:
            i = stack.pop()
            for e, w in edge[i]:
                if color[e] == -1:
                    stack.append(e)
                    if color[i] == 0:
                        if w % 2 == 0:
                            color[e] = 0
                        else:
                            color[e] = 1
                    else:
                        if w % 2 == 0:
                            color[e] = 1
                        else:
                            color[e] = 0
                # ここを追加--------------------------------------
                # 矛盾判定
                else:
                    if (color[i] == color[e]) != (w % 2 == 0):
                        print(-1)
                        exit()
                # ^^^^^^^^--------------------------------------
        # print(color)
        stack = tmp
    print(*color, sep="\n")


if __name__ == '__main__':
    main()


### FIXED CODE ###

N, K = map(int, input().split())
S = list(input())
K -= 1
if S[K] == "A":
    S[K] = "a"
elif S[K] == "B":
    S[K] = "b"
elif S[K] == "C":
    S[K] = "c"


print("".join(S))
x, k, d = map(int, input().split())


def is_even(num):
    if num % 2 == 0:
        return True
    else:
        return False


ans = 0

if 2 * x < d:
    ans = x
else:
    t = x // d
    if k > t - 2:
        if (k - t) / 2 == 0:
            t0 = abs(x - (t - 2) * d)
            t1 = abs(x - (t) * d)
            t2 = abs(x - (t + 2) * d)
            ans = min(t0, min(t1, t2))
        else:
            t0 = abs(x - (t - 1) * d)
            t2 = abs(x - (t + 1) * d)
            ans = min(t0, min(t1, t2))
    else:
      ans = abs(x- (k) * d)

print(ans)


### FIXED CODE ###

x, k, d = map(int, input().split())

x = abs(x)

ans = 0

t = x // d
s = x % d

if abs(x) > k * d:
    print(abs(x) - k * d)
elif t % 2 == k % 2:
    print(s)
else:
    print(d - s)
from numpy import*
_,a=open(0)
a=array([0]+list(map(int,a.split()))+[0])
A=abs
c=sum(a[1:]-a[:-1])
for i,j,k in zip(a,a[1:],a[2:]):print(c-A(j-i)-A(k-j)+A(k-i))

### FIXED CODE ###

*l, = map(int, open(0).read().split())
print(min(l[:2])+min(l[2:]))
def downA(chair):
    for i in range(1,n+1):
        if chair[i]=="#":
            chair[i]="A"
            return

def downB(chair):
    for i in range(n,0,-1):
        if chair[i]=="#" and chair[i-1]!="A" and chair[i+1]!="A":
            chair[i]="B"
            return
    else:
        chair[chair.index("#")]="B"

def downC(chair):
    if set(chair[1:-1])==set(['#']):
        if n%2==0:
            chair[n/2+2]="C"
        else:
            chair[(n+1)/2+1]="C"
        return
    for i in range(1,n+1):
        if chair[i]!="#":
            if chair[i+1]=="#":
                chair[i+1]="C"
                return
            elif i-1>=1 and chair[i-1]=="#":
                chair[i-1]="C"
                return


def downD(chair):
    if set(chair[1:-1])==set(["#"]):
        chair[1]="D"
        return
    t=[0]*n
    cnt=0
    for i in range(1,n+1):
        if chair[i]!="#":
            cnt=0
        else:
            cnt+=1
            t[i]=cnt
    cnt=0
    for i in range(n,0,-1):
        if chair[i]!="#":
            cnt=0
        else:
            cnt+=1
            t[i]=min(cnt,t[i])
    maxInt=max(t)
    chair[t.index(maxInt)]="D"

while True:
    n,m=map(int,raw_input().split())
    if n==m==0:break
    chair=["X"]+["#"]*n+["X"]
    for i in range(m):
        p=raw_input()
        if p=="A":
            downA(chair)
        elif p=="B":
            downB(chair)
        elif p=="C":
            downC(chair)
        elif p=="D":
            downD(chair)
    print "".join(chair[1:-1])

### FIXED CODE ###

def downA(C):
    C[C.index("#")]="A"

def downB(C):
    for i in range(n,0,-1):
        if C[i]=="#" and C[i-1]!="A" and C[i+1]!="A":
            C[i]="B"
            return
    C[C.index("#")]="B"

def downC(C):
    if set(C[1:-1])==set(['#']):
        C[n/2+1]="C"
        return
    for i in range(1,n+1):
        if C[i]!="#":
            if C[i+1]=="#":
                C[i+1]="C"
                return
            elif C[i-1]=="#":
                C[i-1]="C"
                return

def getDist(p):
    l,r=0,0
    while C[p+l-1]=="#":l-=1
    if C[p+l-1]=="X":l=-100000
    while C[p+r+1]=="#":r+=1
    if C[p+r+1]=="X":r=100000
    return min(-1*l,r)

def downD(C):
    if set(C[1:-1])==set(["#"]):
        C[1]="D"
        return
    md=-1
    for i in range(1,n+1):
        if C[i]!="#":continue
        d=getDist(i)
        if (d>md):
            md=d
            mi=i
    C[mi]="D"

while True:
    n,m=map(int,raw_input().split())
    if n==m==0:break
    C=["X"]+["#"]*n+["X"]
    for i in range(m):
        p=raw_input()
        if p=="A":downA(C)
        elif p=="B":downB(C)
        elif p=="C":downC(C)
        elif p=="D":downD(C)
    print "".join(C[1:-1])
a, b, c, d = map(int, input().split())
if (b <= c or d <= a): print(0)
elif (b <= d or c <= a): print(max(abs(a - d) - abs(a - c) - abs(b - d), abs(b - c) - abs(a - c) - abs(b - d)))
else: print(max(abs(a - b) - abs(a - c) - abs(b - d), abs(c - d) - abs(a - c) - abs(b - d))


### FIXED CODE ###

a, b, c, d = map(int, input().split())
if (d < a or b < c): print(0)
else: print(min(b, d) - max(a, c))
m = input()
n = int(m.split()[0])
k = int(m.split()[1])
t = []
for i in range(n):
    t.append(int(input()))
t.sort()
a = None
for i in range(len(t)-k+1):
    w = abs(-1*t[i] + t[i+k])
    if i == 0:
        a = w
    elif a > w:
        a = w
print(a)

### FIXED CODE ###

m = input()
n = int(m.split()[0])
k = int(m.split()[1])
t = []
for i in range(n):
    t.append(int(input()))
t.sort()
a = None
for i in range(len(t)-k+1):
    w = abs(-1*t[i] + t[i+k-1])
    if i == 0:
        a = w
    elif a > w:
        a = w
print(a)