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

def cmb(n, r):
	if n - r < r:
		r = n - r
	if r == 0:
		return 1
	if r == 1:
		return n
	
	num = [n - r + k + 1 for k in range(r)] #numerator(分子)
	den = [k + 1 for k in range(r)] #denominator(分母)
	
	for p in range(2, r + 1):
		pivot = den[p - 1]
		if pivot > 1:
			offset = (n - r) % p
			for k in range(p - 1, r, p):
				num[k - offset] /= pivot
				den[k] /= pivot
	
	result = 1
	for k in range(r):
		if num[k] > 1:
			result *= int(num[k])
	
	return result

n,a,b = map(int,input().split())
mod = 10**9+7

print((pow(2,n,mod) - 1 - cmb(n,a) - cmb(n,b)) % mod)

### FIXED CODE ###

def cmb(n, r):
	if n - r < r:
		r = n - r
	if r == 0:
		return 1
	if r == 1:
		return n
	
	num = [n - r + k + 1 for k in range(r)] #numerator(分子)
	den = [k + 1 for k in range(r)] #denominator(分母)
	
	for p in range(2, r + 1):
		pivot = den[p - 1]
		if pivot > 1:
			offset = (n - r) % p
			for k in range(p - 1, r, p):
				num[k - offset] /= pivot
				den[k] /= pivot
	
	result = 1
	for k in range(r):
		if num[k] > 1:
			result *= int(num[k])
			result = result % mod
	
	return result

n,a,b = map(int,input().split())
mod = 10**9+7

print((pow(2,n,mod) - 1 - cmb(n,a) - cmb(n,b)) % mod)
### BUGGY CODE ###

MOD = 1000000007
n = int(raw_input())
d = {}
for i, ai in enumerate(int(_) for _ in raw_input().split()):
    if ai in d:
        stt = d[ai]
        end = i
        break
    d[ai] = i
del d, i, ai

frid = {}
n21 = n // 2 + 1
q = 1
for i in xrange(1, n21 + 1):
    q = q * i % MOD
frid[n21] = pow(q, MOD - 2, MOD)
for j in xrange(n21 - 1, -1, -1):
    frid[j] = frid[j + 1] * (j + 1) % MOD


def ncr(n, r):
    if r * 2 > n:
        return ncr(n, n - r)
    p = 1
    for i in xrange(n - r + 1, n + 1):
        p = p * i % MOD
    return (p * frid[r]) % MOD


l = stt
r = n - end

for k in xrange(1, n + 2):
    a = ncr(n + 1, k) % MOD
    if l + r >= k - 1:
        a -= ncr(l + r, k - 1) % MOD
    print a % MOD


### FIXED CODE ###

MOD = 1000000007
n = int(raw_input())
d = {}
for i, ai in enumerate(int(_) for _ in raw_input().split()):
    if ai in d:
        stt = d[ai]
        end = i
        break
    d[ai] = i
del d, i, ai

fac = {0: 1}
facinv = {}
for i in xrange(1, n + 2):
    fac[i] = fac[i - 1] * i % MOD
facinv[n + 1] = pow(fac[n + 1], MOD - 2, MOD)
for j in xrange(n, -1, -1):
    facinv[j] = facinv[j + 1] * (j + 1) % MOD


def ncr(n, r):
    return (fac[n] * facinv[n - r] * facinv[r]) % MOD


l = stt
r = n - end

for k in xrange(1, n + 2):
    a = ncr(n + 1, k) % MOD
    if l + r >= k - 1:
        a -= ncr(l + r, k - 1) % MOD
    print a % MOD
### BUGGY CODE ###

a, b, x = map(int, input().split())
while b % x:
    b -= 1
if a == 0:
    print(b // x + 1)
else:
    print((b // x) - ((a - 1) // x))


### FIXED CODE ###

a, b, x = map(int, input().split())
if a == 0:
    print(b // x + 1)
else:
    print((b // x) - ((a - 1) // x))
### BUGGY CODE ###

N,Q = map(int,input().split())
S = input()
A = [list(map(int,input().split())) for _ in range(Q)]
AC_list = []
for i in range(N-1):
    if S[i] == 'A' and S[i+1] == 'C':
        AC_list.append(1)
    else:
        AC_list.append(0)
for a in A:
    check = AC_list[a[0]-1:a[1]-1]
    print(sum(check))

### FIXED CODE ###

import numpy as np
N,Q = map(int,input().split())
S = np.array(list('_' + input()), dtype='U2')
A = (S == 'A')
C = (S == 'C')
AC = (A[:-1] & C[1:])
AC_cum = AC.cumsum()

for _ in range(Q):
    L,R = map(int,input().split())
    print(AC_cum[R-1] - AC_cum[L-1])
### BUGGY CODE ###

from collections import deque

def bfs(maze, h, w, si, sj, gi, gj):
    memo = [[0] * w for i in range(h)]
    q = deque([[si, sj]])
    score = [[0] * w for i in range(h)]

    pattern = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    while len(q) > 0:
        i, j = q.popleft()
        if i == gi and j == gj:
            return score[gi][gj]
        for move in pattern:
            ni, nj= i + move[0], j + move[1]
            if ni < 0 or h <= ni or nj < 0 or w <= nj:
                continue
            p = maze[ni][nj]
            if p == '#':
                continue
            if p == '.' and not score[ni][nj]:
                score[ni][nj] = score[i][j] + 1
                q.append([ni, nj])

h, w = map(int, input().split())
maze = [input() for i in range(h)]
scores = []
for si in range(h):
    for sj in range(w):
        if maze[si][sj] == "#":
            continue
        for gi in range(h):
            for gj in range(w):
                if maze[gi][gj] == "#" or (si == gi and sj == gj):
                    continue
                scores.append(bfs(maze, h, w, si, sj, gi, gj))
print(max(scores))


### FIXED CODE ###

from collections import deque

def bfs(maze, h, w, si, sj):
    q = deque([[si, sj]])
    score = [[-1] * w for i in range(h)]
    score[si][sj] = 0
    pattern = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    while len(q) > 0:
        i, j = q.popleft()
        for move in pattern:
            ni, nj= i + move[0], j + move[1]
            if ni < 0 or h <= ni or nj < 0 or w <= nj:
                continue
            p = maze[ni][nj]
            if p == '#':
                continue
            if p == '.' and score[ni][nj] == -1:
                score[ni][nj] = score[i][j] + 1
                q.append([ni, nj])
    return max(map(max, score))

h, w = map(int, input().split())
maze = [input() for i in range(h)]
scores = []
for si in range(h):
    for sj in range(w):
        if maze[si][sj] == "#":
            continue
        scores.append(bfs(maze, h, w, si, sj))
print(max(scores))
### BUGGY CODE ###

import bisect
import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
ans = int(0)

N = I()
color = []
a = I()
maxcolor =[]
maxcolor.append(a)
lena = 1
for i in range(N-1):
    a = I()
    minmaxcolor = maxcolor[0]
    if a<=minmaxcolor:
        maxcolor.insert(0,a)
#        maxcolor.append(a)
        lena += 1
    else:
        acandi = bisect.bisect_left(maxcolor, a)
        maxcolor[acandi-1] = a
        """
        aupper = lena-1
        alower = int(0)
        acandi = aupper//2
        
        for _ in range(aupper+1):
            if maxcolor[acandi]>=a:
                alower = acandi
                acandi = (aupper+acandi+1)//2
            else:
                if aupper - alower <= 1:
                    maxcolor[acandi] = a
                    break
                else:
                    aupper = acandi
                    acandi = (acandi + alower) // 2
        """

#print(maxcolor)
ans = len(maxcolor)
print(ans)


### FIXED CODE ###

from collections import deque
import bisect
import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
ans = int(0)

N = I()
color = []
a = I()
maxcolor =deque()
maxcolor.append(a)
lena = 1
for i in range(N-1):
    minmaxcolor = maxcolor[0]
    a = I()
    if a<=minmaxcolor:
        maxcolor.appendleft(a)
#        maxcolor.append(a)
        lena += 1
    else:
        acandi = bisect.bisect_left(maxcolor, a)
        maxcolor[acandi-1] = a
        """
        aupper = lena-1
        alower = int(0)
        acandi = aupper//2
        
        for _ in range(aupper+1):
            if maxcolor[acandi]>=a:
                alower = acandi
                acandi = (aupper+acandi+1)//2
            else:
                if aupper - alower <= 1:
                    maxcolor[acandi] = a
                    break
                else:
                    aupper = acandi
                    acandi = (acandi + alower) // 2
        """

#print(maxcolor)
ans = len(maxcolor)
print(ans)
### BUGGY CODE ###

N = int(input())
S = input()
ans = 3 * 10**5
if S[0] =='W':
    left = 1
else:
    left = 0
for index, num in enumerate(S):
    ans = min(ans, S[index+1:].count('E')+S[:index].count('W'))

print(ans)

### FIXED CODE ###

N = int(input())
S = input()
l = 0
r = S[1:].count('E')
ans = l+r

for i in range(1, N):
    if S[i-1] == 'W':
        l += 1
    
    if S[i] == 'E':
        r -= 1
    ans = min(ans, r+l)

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

n = int(input())
p = list(map(int, input().split()))
cnt = 0
for i in range(n):
    if p[i] <= min(p[:i+1]):
        cnt += 1
print(cnt)


### FIXED CODE ###

n = int(input())
p = list(map(int, input().split()))
cnt = 0
m = float('inf')
for i in range(n):
    m = min(p[i], m)
    if p[i] <= m:
        cnt += 1
print(cnt)
### BUGGY CODE ###

import numpy as np
n = int(input())
a = np.array([int(i) for i in input().split()])
a_sum = a.sum()
#y = sum - x
ans = 10**15
for i in range(1,n):
    x = a[:i].sum()
    aa = abs(2 * x - a_sum)
    ans = min(ans,aa)
print(ans)

### FIXED CODE ###

import numpy as np
n = int(input())
a = np.array([int(i) for i in input().split()])
a_c = a.cumsum()
a_t = a_c[-1]
diff = np.abs(2 * a_c - a_t)
ans = diff[:-1].min()
print(ans)
### BUGGY CODE ###


def bisect(a,B,lo,hi):
    if hi-lo==1:
        return hi
    elif B[(hi+lo)//2]>=a:
        return bisect(a,B,(hi+lo)//2,hi)
    else:
        return bisect(a,B,lo,(hi+lo)//2)

N = int(input())

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

B = [A[0]]

for i in range(1,N):
    if B[-1]>=A[i]:
        B.append(A[i])
    else:
        if B[0]<A[i]:
            B[0]=A[i]
        else: 
            B[bisect(A[i],B,0,len(B))]=A[i]
print(len(B))

### FIXED CODE ###


def bisect(a,B,lo,hi):
    if hi-lo<=1:
        return hi
    elif B[(hi+lo)//2]>=a:
        return bisect(a,B,(hi+lo)//2,hi)
    else:
        return bisect(a,B,lo,(hi+lo)//2)

N = int(input())

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

B = [A[0]]

for i in range(1,N):
    if B[-1]>=A[i]:
        B.append(A[i])
    else:
        if B[0]<A[i]:
            B[0]=A[i]
        else: 
            B[bisect(A[i],B,0,len(B)-1)]=A[i]
print(len(B))
### BUGGY CODE ###

def is_anagram(s1: str, s2: str) -> bool:
    size1, size2 = len(s1), len(s2)
    if size1 != size2:
        return False

    d1, d2 = dict(), dict()

    for i in range(size1):
        c1, c2 = s1[i], s2[i]
        count1, count2 = d1.get(c1), d2.get(c2)
        if count1 is None:
            d1[c1] = 1
        else:
            d1[c1] = count1 + 1
        if count2 is None:
            d2[c2] = 1
        else:
            d2[c2] = count2 + 1

    return d1 == d2

n = int(input())
ss = [input() for _ in range(n)]

counter = 0

for index1 in range(n):
    for index2 in range(index1 + 1, n):
        if is_anagram(ss[index1], ss[index2]):
            counter += 1

print(counter)



### FIXED CODE ###

from math import factorial


def combination2(num: int) -> int:
    return int(factorial(num) / (2 * factorial(num - 2)))


n = int(input())
ss = [input() for _ in range(n)]

dictionary = {}

for s in ss:
    sorted_string = "".join(sorted(s))
    count = dictionary.get(sorted_string)
    if count is None:
        dictionary[sorted_string] = 1
    else:
        dictionary[sorted_string] = count + 1

counter = 0

for count in dictionary.values():
    if count > 1:
        counter += combination2(count)

print(counter)
### BUGGY CODE ###

import sys
from collections import defaultdict

sys.setrecursionlimit(4000)

n = int(input())
arr = map(int, input().split())
arr = tuple(sorted(enumerate(arr), key=lambda tpl: -tpl[1]))

dp = defaultdict(int)

for ln in range(n + 1):
  for rn in range(n + 1 - ln):
    if ln + rn > n or dp[ln, rn]:
      continue

    p, a = arr[ln + rn - 1]
    val_l = dp[ln - 1, rn] + a * abs(p - (ln - 1)) if ln > 0 else 0
    val_r = dp[ln, rn - 1] + a * abs(p - (n - rn)) if rn > 0 else 0

    dp[ln, rn] = max(val_l, val_r)

print(max([dp[i, n - i] for i in range(n + 1)]))


### FIXED CODE ###


def main():

  n = int(input())
  arr = map(int, input().split())
  arr = tuple(sorted(enumerate(arr), key=lambda tpl: -tpl[1]))

  dp = [[0] * (n + 1) for _ in range(n + 1)]
  for i, (p, a) in enumerate(arr):
    for l in range(i + 1):
      dp[i + 1][l] = max(dp[i + 1][l], dp[i][l] + a * abs(p - (n - (i - l) - 1)))
      dp[i + 1][l + 1] = max(dp[i + 1][l + 1], dp[i][l] + a * abs(p - l))

  print(max(dp[n]))

main()
### BUGGY CODE ###

import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n = ni()

print(0)
k = ns()

ok,ng = n,-1

def is_ok(p):
    print(p)
    q = ns()
    return not p%2 ^ (q == k)

while (abs(ok - ng) > 1):
    mid = (ok + ng) // 2
    if is_ok(mid):
        ok = mid
    else:
        ng = mid


### FIXED CODE ###

import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n = int(input())
print(0)
l = input()
r = l
if l == "Vacant":
    exit()

ng,ok = 0,n
while True:
    mid = (ng + ok) // 2
    print(mid)
    q = input()
    if q == "Vacant":
        exit()
    if (q == l) ^ ((mid - ng)%2 == 1):
        ng = mid
        l = q
    else:
        ok = mid
        r = q
### BUGGY CODE ###

import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from collections import defaultdict, deque

# 入力・隣接リスト作成
n,m = li()
graph = defaultdict(set)
geta = pow(10,7)

for _ in range(m):
    p,q,c = li()
    
    graph[p + c*geta].add(q + c*geta)
    graph[q + c*geta].add(p + c*geta)
    
    graph[p + c*geta].add(p)
    graph[q + c*geta].add(q)
    
    graph[p].add(p + c*geta)
    graph[q].add(q + c*geta)
    
que = deque()
que.append((0, 1))
visited = set()

ans = -1

while que:
    (cost, node) = que.popleft()
    
    if node in visited:
        continue
    
    elif node % geta == n:
        ans = cost
        break
    
    visited.add(node)
    
    
    for nex in graph[node]:
        if nex in visited:
            continue
        
        elif node <= n and nex > n:
            que.append((cost+1, nex))
            
        else:
            que.appendleft((cost, nex))
    
print(ans)

### FIXED CODE ###

import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**7) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from collections import deque, defaultdict

n,m = li()
mod = 10**7

table = defaultdict(set)
visit = defaultdict(int)

for i in range(m):
    a,b,c = li()
    
    table[a].add(a + c*mod)
    table[b].add(b + c*mod)
    table[a + c*mod].add(a)
    table[b + c*mod].add(b)
    table[a + c*mod].add(b + c*mod)
    table[b + c*mod].add(a + c*mod)
    
    visit[a] = 0
    visit[b] = 0
    visit[b + c*mod] = 0
    visit[a + c*mod] = 0
    
que = deque()
que.append((1,0))

visit[1] = 1
ans = mod

while que:
    x, cost = que.popleft()
    visit[x] = 1
    
    if x == n:
        ans = min(ans, cost)
        break
    
    for y in table[x]:
        if visit[y] == 1:
            continue
        
        if x <= 10**5 and mod <= y:
            que.append((y, cost+1))
            
        else:
            que.appendleft((y, cost))
        
print(-1 if ans == mod else ans)
### BUGGY CODE ###



def submit():
    s = input()
    t = input()

    next_char = {}
    char_list = {}

    for i in reversed(range(len(s))):
        c = s[i]
        if c not in next_char.keys():
            next_char[c] = i
            char_list[(c, i)] = -1
        else:
            char_list[(c, i)] = next_char[c]
            next_char[c] = i

    
    init_next_char = next_char.copy()
    loop = 0
    curr = 0
    for c in t:
        # 実現不可能
        if c not in next_char.keys():
            print(-1)
            return

        while 0 <= next_char[c] < curr:
            next_char[c] = char_list[(c, next_char[c])]
        
        if next_char[c] < 0:
            loop += 1
            curr = 0
            next_char = init_next_char.copy()
        
        curr = next_char[c]
        next_char[c] = char_list[(c, next_char[c])]
    print(loop * len(s) + curr + 1)
        

submit()

### FIXED CODE ###



def submit():
    s = input()
    t = input()
    char_set = set(s)
    next_char = {c: -1 for c in char_set}
    char_list = {(c, len(s)): -1 for c in char_set}

    for i in reversed(range(len(s))):
        for c in char_set:
            if c == s[i]:
                char_list[(c, i)] = i
            else:
                char_list[(c, i)] = char_list[(c, i + 1)]
            
    loop = 0
    curr = 0
    for c in t:
        # 実現不可能
        if c not in char_set:
            print(-1)
            return
        if char_list[(c, curr)] < 0:
            loop += 1
            curr = 0
        curr = char_list[(c, curr)] + 1
    print(loop * len(s) + curr)
        

submit()
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
b = list((x,i) for i,x in enumerate(a))
b.sort(reverse=True)
dp = [[0]*(n+1) for i in range(n+1)]
for i in range(n):
    for j in range(i+1):
        k = i-j
        x,idx = b[i]
        if dp[j+1][k] < dp[j][k] + x*(idx-j):
            dp[j+1][k] = dp[j][k] + x*(idx-j)
        if dp[j][k+1] < dp[j][k] + x*((n-1-k)-idx):
            dp[j][k+1] = dp[j][k] + x*((n-1-k)-idx)
ans = 0
for i in range(n+1):
    if ans < dp[i][n-i]:
        ans = dp[i][n-i]
print(ans)


### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
b = list((x,i) for i,x in enumerate(a))
b.sort(reverse=True)
dp = [[0]*(n+1-i) for i in range(n+1)]
for i in range(n):
    x,idx = b[i]
    for j in range(i+1):
        k = i-j
        if dp[j+1][k] < dp[j][k] + x*(idx-j):
            dp[j+1][k] = dp[j][k] + x*(idx-j)
        if dp[j][k+1] < dp[j][k] + x*((n-1-k)-idx):
            dp[j][k+1] = dp[j][k] + x*((n-1-k)-idx)
ans = 0
for i in range(n+1):
    if ans < dp[i][n-i]:
        ans = dp[i][n-i]
print(ans)
### BUGGY CODE ###

N = int(input(""))
A = list(map(int, input("").split()))
n = 1

for i in range(N):
    n = n * A[i]

if n > 10 ** 18:
    n = -1

print(n)

### FIXED CODE ###

N = int(input(""))
A = list(map(int, input("").split()))
n = 1

if 0 in A:
    print(0)
else:
    for i in range(N):
        n = n * A[i]
        if n > 10 ** 18:
            n = -1
            break

    print(n)
### BUGGY CODE ###

from itertools import product
import sys

input = sys.stdin.readline

INF = float('inf')

def floyd_warshall(V, E):
    dist = {u: {v: INF for v in V} for u in V}
    for v in V:
        dist[v][v] = 0
        for u in E[v]: dist[v][u] = 1
    for k in V:
        for i, j in product(V, repeat=2):
            temp = dist[i][k] + dist[k][j]
            if dist[i][j] > temp:
                dist[i][j] = temp
    for v in V:
        if dist[v][v] < 0: return None
    return dist

H, W = map(int, input().split())
maze = [input() for _ in range(H)]
V = []
E = {}
for i, j in product(range(H), range(W)):
    if maze[i][j] == '#': continue
    V += [(i, j)]
    check = [(i+dx, j+dy) for dx, dy in [(1, 0), (0, 1)] if i+dx <= H-1 and j+dy <= W-1]
    for x, y in check:
        if maze[x][y] == '.':
            E.setdefault((i, j), [])
            E.setdefault((x, y), [])
            E[(i, j)].append((x, y))
            E[(x, y)].append((i, j))
dist = floyd_warshall(V, E)
ans = 0
for D in dist.values():
    ans = max(ans, max(D.values()))
print(ans)

### FIXED CODE ###

from collections import deque
from itertools import product

H, W = map(int, input().split())
maze = [input() for _ in range(H)]
V = []
E = {}
for i, j in product(range(H), range(W)):
    if maze[i][j] == '#': continue
    V += [(i, j)]
    check = [(i+dx, j+dy) for dx, dy in [(1, 0), (0, 1)] if i+dx <= H-1 and j+dy <= W-1]
    for x, y in check:
        if maze[x][y] == '.':
            E.setdefault((i, j), [])
            E.setdefault((x, y), [])
            E[(i, j)].append((x, y))
            E[(x, y)].append((i, j))

def bfs(s):
    q = deque([(s, 0)])
    dist = {v: -1 for v in V}
    while q:
        v, d = q.popleft()
        if dist[v] >= 0: continue
        dist[v] = d
        for u in E[v]:
            if dist[u] < 0:
                q.append((u, d+1))
    return dist

ans = 0
for v in V:
    dist = bfs(v)
    ans = max(ans, max(dist.values()))
print(ans)
### BUGGY CODE ###

K, S = [int(n) for n in input().split()]
c = 0
for X in range(K+1):
  for Y in range(K+1):
    for Z in range(K+1):
      if X+Y+Z == S:
        c += 1
print(c)

### FIXED CODE ###

K, S = [int(n) for n in input().split()]
print(sum([1 for X in range(K+1) for Y in range(K+1) if 0<=S-X-Y<=K]))
### BUGGY CODE ###

#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin, maxint
import heapq


def main():
    num = int(stdin.readline())

    L = []
    for _ in xrange(num):
        it = iter(int(s) for s in stdin.readline().split()[1:])
        L.append([(next(it), next(it)) for _ in xrange(next(it))])

    weight = [[maxint, i] for i in xrange(num)]
    weight[0][0] = 0
    V = set(xrange(1, num))
    W = weight[1:]
    index = 0

    while V:
        swap = False
        for v, cost in L[index]:
            if v not in V:
                continue
            cost += weight[index][0]
            if weight[v][0] > cost:
                weight[v][0] = cost
                swap = True

        if swap:
            heapq.heapify(W)
        index = heapq.heappop(W)[1]
        V.remove(index)

    for d, i in weight:
        print(i, d)


main()

### FIXED CODE ###

#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin, maxsize


def main():
    num = int(stdin.readline())

    edges = []
    for _ in range(num):
        ns = [int(s) for s in stdin.readline().split()]
        for i in range(ns[1]):
            edges.append((ns[0], ns[2*i+2], ns[2*i+3]))

    dis = [maxsize] * num
    dis[0] = 0

    while 1:
        update = False
        for from_, to, cost in edges:
            if dis[from_] < maxsize and dis[to] > cost + dis[from_]:
                dis[to] = cost + dis[from_]
                update = True

        if not update:
            break

    for i, d in enumerate(dis):
        print(i, d)


main()
### BUGGY CODE ###

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

ids = list(range(1, N+1))

for _ in range(M):
    (L, R) = map(int, input().split(" "))
    ids = list(filter(lambda x: (L <= x) and (x <= R), ids))

print(len(ids))

### FIXED CODE ###

# coding: utf-8

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

ids = list(range(1, N+1))

L_max = 0
R_min = 10000000000000000000
for _ in range(M):
    (L, R) = map(int, input().split(" "))
    if L > L_max:
        L_max = L
    if R < R_min:
        R_min = R

ids = [i for i in ids if L_max <= i <= R_min]
print(len(ids))
### BUGGY CODE ###

[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = []
for i in range(N-L+1) : ans.append(min(A[i:i+L]))
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])