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

from sys import stdin,stdout,setrecursionlimit
from collections import Counter as C
setrecursionlimit(10**6)
M = 1000000007
input = stdin.readline
def write(n,sep="\n"):
	stdout.write(str(n))
	stdout.write(sep)
def gil():
	return list(map(int, input().split()))
	
n = int(input())
h = gil()


def rp(i, h, n, c, p):
    if i >= n:
        return c + abs(p - h[n-1])
    x = abs(p - h[i])
    return min(rp(i+1, h, n, c + x, h[i]),rp(i+2, h, n, c + x, h[i]))
    
ans = min(rp(1, h, len(h), 0, h[0]),rp(2, h, len(h), 0, h[0]))
print(ans)


### FIXED CODE ###

from sys import stdin,stdout,setrecursionlimit
from collections import Counter as C
setrecursionlimit(10**6)
M = 1000000007
input = stdin.readline
def write(n,sep="\n"):
	stdout.write(str(n))
	stdout.write(sep)
def gil():
	return list(map(int, input().split()))
	
n = int(input())
h = gil()
dp = [1e18]*(n+1)
dp[0] = 0
for i in range(n):
    for j in [i+1, i+2]:
        if j < n:
            dp[j] = min(dp[j], dp[i] + abs(h[i] - h[j]))
print(dp[n-1])
### BUGGY CODE ###

def comb(n, k, mod=10**9 + 7):
    from functools import reduce
    from operator import mul
    k = min(k, n - k)
    x = reduce(mul, range(n - k + 1, n + 1), 1) % mod
    y = reduce(mul, range(1, k + 1), 1) % mod
    return x * pow(y, mod - 2, mod) % mod


def solve(string):
    n, m, k = map(int, string.split())
    mod = 10**9 + 7
    base = n * m * (n + m) * (n * m - 1) // 6 % mod
    return str(base * comb(n * m - 2, k - 2) % mod)


if __name__ == '__main__':
    print(solve(input()))


### FIXED CODE ###

mod = 10**9 + 7


def comb(n, k):
    x, y = 1, 1
    k = min(k, n - k)
    for i in range(k):
        x *= n - i
        x %= mod
        y *= i + 1
        y %= mod
    return x * pow(y, mod - 2, mod) % mod


def solve(string):
    n, m, k = map(int, string.split())
    base = n * m * ((n + 1) * (m + 1) * (n + m - 2) - n**2 - m**2 + 2) // 6 % mod
    return str(base * comb(n * m - 2, k - 2) % mod)


if __name__ == '__main__':
    print(solve(input()))
### BUGGY CODE ###

import sys
X, Y, Z, K = map(int, input().split())
A = list(map(int, sys.stdin.readline().split()))
B = list(map(int, sys.stdin.readline().split()))
C = list(map(int, sys.stdin.readline().split()))
AB = []
for a in A:
    for b in B:
        AB.append(a + b)
AB.sort(reverse = True)
ans = []
AB2 = AB[:min(X * Y + 1, K + 1)]
for ab in AB2:
    for c in C:
        ans.append(ab + c)
ans.sort(reverse = True)
for i in range(K):
    print(ans[i])

### FIXED CODE ###

import sys
X, Y, Z, K = map(int, input().split())
A = list(map(int, sys.stdin.readline().split()))
B = list(map(int, sys.stdin.readline().split()))
C = list(map(int, sys.stdin.readline().split()))
A.sort(reverse = True)
B.sort(reverse = True)
C.sort(reverse = True)
AB = []
ans = []
for a in A:
    for b in B:
        AB.append(a + b)
AB.sort(reverse=True)
AB = AB[:min(3001, X*Y*Z+1)]
for c in C:
    for ab in AB:
        ans.append(c + ab)
ans.sort(reverse=True)
for i in range(K):
    print(ans[i])
### BUGGY CODE ###

N = int(input())
S = []
cnt = 0
for i in range(N):
    tmp = list(input())
    tmp.sort()
    S.append(tmp)
for i in range(N-1):
    for j in range(i+1,N):
        if S[i]==S[j]:
            cnt+=1
print(cnt)

### FIXED CODE ###

N = int(input())
S = []
ans = 0
for i in range(N):
    tmp = list(input())
    tmp.sort()
    tmp = "".join(tmp)
    S.append(tmp)

S.sort()

cnt = 0
ans = 0

for i in range(N):
    if i == 0 or S[i] == S[i-1]:
        cnt += 1
    else:
        ans += cnt*(cnt-1)//2
        cnt = 1
ans += cnt*(cnt-1)//2
    
print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
B = []
for j in range(1,N):
    B.append(sum(A[j:])%(10**9+7))
count = 0
for i in range(N-1):
    count += (A[i]*B[i])%(10**9+7)
print(count%(10**9+7))

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
B = []
p = sum(A)
for j in range(N-1):
    p -= A[j]
    B.append(p%(10**9+7))
count = 0
for i in range(N-1):
    count += (A[i]*B[i])%(10**9+7)
print(count%(10**9+7))
### BUGGY CODE ###

# N = int(input())
# A = [int(x) for x in input().split()]
# V = [[0] * 100 for _ in range(100)]

N, M = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
A.sort(reverse=True)

CB = []
for i in range(M):
    b, c = [int(x) for x in input().split()]
    CB.append((c, b))
CB.sort(reverse=True)

cnt = 0
L = []
for cb in CB:
    if cnt >= N:
        break
    L.extend([cb[0]] * cb[1])

newA = A + L
newA.sort(reverse=True)

newA = newA[0:N]
ans = sum(newA)

print(ans)


### FIXED CODE ###

# N = int(input())
# A = [int(x) for x in input().split()]
# V = [[0] * 100 for _ in range(100)]

N, M = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
A.sort(reverse=True)

CB = []
for i in range(M):
    b, c = [int(x) for x in input().split()]
    CB.append((c, b))
CB.sort(reverse=True)


L = []
for cb in CB:
    if len(L) >= N:
        break
    L.extend([cb[0]] * cb[1])

newA = A + L
newA.sort(reverse=True)

newA = newA[0:N]
ans = sum(newA)

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

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

s=[None]*D
for i in range(D):
    s[i] = list(map(int,input().split()))
t=[0]*D
for i in range(D):
    t[i]=int(input())
    
m=int(input())
d=[None]*m
q=[None]*m
for i in range(m):
    d[i],q[i] = map(int,input().split())

def calc_score(t):
    last=[0]*26
    satis=0
    pena=0
    for j in range(D):
        ss=s[j]
        tt=t[j]
        satis += ss[tt-1]
        last[tt-1]=j+1
        
        pena += sum(c[i]*(j+1-last[i]) for i in range(26))
    return satis-pena

# calc_score(t)-10**6
for i in range(m):
    t[d[i]-1] = q[i]
    print(calc_score(t))

### FIXED CODE ###

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

s=[None]*D
for i in range(D):
    s[i] = list(map(int,input().split()))
t=[0]*D
for i in range(D):
    t[i]=int(input())
    
m=int(input())
d=[None]*m
q=[None]*m
for i in range(m):
    d[i],q[i] = map(int,input().split())
sumc=sum(c)



def calc_score(t):
    last=[0]*26
    satis=0
    pena=0
    delta_pena=0
    for j in range(D):
        ss=s[j]
        tt=t[j]
        satis += ss[tt-1]
        delta_pena += sumc - c[tt-1]*(j+1-last[tt-1])

        last[tt-1]=j+1   
        pena += delta_pena
    return satis-pena

for i in range(m):
    t[d[i]-1] = q[i]
    print(calc_score(t))
### BUGGY CODE ###

def bfs(n,e,fordfs):
    d = defaultdict(int)
    P = [-1]*n
    que = deque(); que2 = deque()
    que.append(e)
    P[e] = 0
    while que:
        now = que.popleft()
        for ne in fordfs[now]:
            if P[ne] == -1:
                que.append(ne)
                P[ne] = now + 1
            else:
                P[ne] = now + 1
                que2.append(ne)
    while que2:
        now = que2.popleft()
#        if d[now]:
#            continue
#        d[now] = True
        for ne in fordfs[now]:
            P[ne] = now + 1
            que2.append(ne)
    return P
def examD():
    ans = 0
    N, M = LI()
    V = [[] for _ in range(N)]
    d = defaultdict(bool)
    for i in range(N+M-1):
        a, b = LI()
        #逆に張る
        V[a-1].append(b-1)
        d[b-1] = True
    for i in range(N):
        if not d[i]:
            start = i
            ans = bfs(N, start, V)
            break
    for v in ans:
        print(v)
#    print(V)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

if __name__ == '__main__':
    examD()


### FIXED CODE ###

def examD():
    N, M = LI()
    V = [[] for _ in range(N)]
    ans = [0]*N
    Cnt=[0]*(N+1); Cnt[N]=1
    for i in range(N+M-1):
        a, b = LI()
        V[a-1].append(b-1)
        Cnt[b-1] += 1
    root = Cnt.index(min(Cnt))
    que = [root]
#    print(Cnt)
#    print(root)
    while que:
        v = que.pop()
        for u in V[v]:
            if Cnt[u] == 1:
                ans[u] = v+1
                que.append(u)
            else:
                Cnt[u] -= 1
    print(*ans, sep='\n')
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

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

import sys
input = sys.stdin.readline
n=int(input())
A=[int(i) for i in input().split()]
B=[int(i) for i in input().split()]

from heapq import heappop, heappush
push = lambda x,i: heappush(BB,(-x,i))
BB=[]

for i,b in enumerate(B):
  push(b,i)

ans=0
while BB:
  b,ind=heappop(BB)
  b,ai=-b,A[ind]
  if b<ai:
    ans=-1
    break
  d=B[(ind-1)%n]+B[(ind+1)%n]
  dd=(b-ai)//d
  if dd==0:
    if b==ai:
      continue
    ans=-1
    break
  ans+=dd
  B[ind]-=d*dd
  push(B[ind],ind)
  
print(ans)


### FIXED CODE ###

n=int(input())
A=[int(i) for i in input().split()]
B=[int(i) for i in input().split()]

from heapq import heappop, heappush
push = lambda x,i: heappush(BB,(-x,i))
BB=[]

for i,b in enumerate(B):
  push(b,i)

ans=0
while BB:
  b,ind=heappop(BB)
  b,ai=-b,A[ind]
  if b<ai:
    ans=-1
    break
  d=B[(ind-1)%n]+B[(ind+1)%n]
  dd=(b-ai)//d
  if dd==0:
    if b==ai:
      continue
    ans=-1
    break
  ans+=dd
  B[ind]-=d*dd
  push(b-d*dd,ind)
  
print(ans)
### BUGGY CODE ###

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

L=list(map(int,input().split()))
S=[0]*100010
for i in range(N):
    S[i]=L[i]

DP=[10**12]*100010

DP[0]=0
for i in range(N):
    for j in range(1,M+1):
        if DP[i+j]>DP[i]+abs(S[i+j]-S[i]):
            DP[i+j]=DP[i]+abs(S[i+j]-S[i])



print(DP[N-1])

            

### FIXED CODE ###

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

L=list(map(int,input().split()))
S=[0]*110000
for i in range(N):
    S[i]=L[i]

DP=[10**12]*110000

DP[0]=0
for i in range(N):
    for j in range(1,M+1):
        if DP[i+j]>DP[i]+abs(S[i+j]-S[i]):
            DP[i+j]=DP[i]+abs(S[i+j]-S[i])



print(DP[N-1])
### BUGGY CODE ###

import sys

input = sys.stdin.readline

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

es = []
for _ in range(N):
    s, t, x = map(int, input().split())
    es.append((s - x, 1, x))
    es.append((t - x, 0, x))

for _ in range(Q):
    d = int(input())
    es.append((d, 2, -1))

es.sort(key=lambda x: (x[0], x[1]))
st = set()
cur_min_stop = -1
check_needed = True
for i, (time, typ, pos) in enumerate(es):
    # print(es)
    # print(st)
    # print(i, (time, typ, pos))
    if typ == 1:
        st.add(pos)
        if cur_min_stop == -1 or pos < cur_min_stop:
            cur_min_stop = pos
    elif typ == 0:
        st.remove(pos)
        if pos == cur_min_stop:
            check_needed = True
    else:
        if check_needed:
            if st:
                cur_min_stop = min(st)
            else:
                cur_min_stop = -1
            check_needed = False
        print(cur_min_stop)


### FIXED CODE ###

# 理解する時間がなかったので、とりあえず写経
from bisect import bisect_left
from operator import itemgetter

N, Q = [int(i) for i in input().split()]
Construction = [tuple(int(i) for i in input().split()) for j in range(N)]
D = [int(input()) for _ in range(Q)]

ans = [-1] * Q
skip = [-1] * Q

Construction.sort(key=itemgetter(2))

for s, t, x in Construction:
    l = bisect_left(D, s - x)
    r = bisect_left(D, t - x)
    t = l
    while t < r:
        if skip[t] == -1:
            ans[t] = x  # lからr-1の時刻に出発した人は座標xの工事に引っかかる
            skip[t] = r  # lからr-1の時刻に出発した人はもう調べないようにする
            t += 1
        else:
            t = skip[t]  # tが指定する人はもう調べ終わっているので飛ばす
print(*ans, sep='\n')
### BUGGY CODE ###

h,w = map(int, input().split())
a = [list(map(int, input().split())) for i in range(h)]
b = [list(map(int, input().split())) for i in range(h)]

MAX_VAL = 80*80+5
dp = [[[False]*(MAX_VAL) for _ in range(w+1)] for _ in range(h+1)]

bias = MAX_VAL//2
icost = a[0][0] - b[0][0]
dp[1][1][icost + bias] = True

dp[1][1][-icost + bias] = True

for i in range(1,h+1):
    for j in range(1,w+1):
        cost = a[i-1][j-1] - b[i-1][j-1]
        for k in range(MAX_VAL):
            if dp[i-1][j][k]:
                if 0 <= k+cost < MAX_VAL:
                    dp[i][j][k+cost] = True
                if 0 <= k-cost < MAX_VAL:
                    dp[i][j][k-cost] = True
            if dp[i][j-1][k]:
                if 0 <= k+cost < MAX_VAL:
                    dp[i][j][k+cost] = True
                if 0 <= k-cost < MAX_VAL:
                    dp[i][j][k-cost] = True

ans = 10010001001
for i in range(MAX_VAL):
    if dp[h][w][i]:
        ans = min(ans,abs(i-bias))
print(ans)

### FIXED CODE ###

h, w = map(int, input().split())
lsa = [list(map(int, input().split())) for i in range(h)]
lsb = [list(map(int, input().split())) for i in range(h)]
ls = [[abs(lsa[i][j] - lsb[i][j]) for j in range(w)] for i in range(h)]
bias = 80*80*80

dp = [[0 for _ in range(w)] for _ in range(h)]

dp[0][0] = 1 << ls[0][0]+bias

for i in range(h):
    for j in range(w):

        if j != 0:  
            dp[i][j] |= dp[i][j-1] << ls[i][j]
            dp[i][j] |= dp[i][j-1] >> ls[i][j]

        if i != 0:
            dp[i][j] |= dp[i-1][j] << ls[i][j]
            dp[i][j] |= dp[i-1][j] >> ls[i][j]

ans = dp[h-1][w-1] >> bias
idx = 0
while(1):
    if 1 << idx & ans:
        break
    idx += 1
print(idx)
### BUGGY CODE ###

# ABC068c
import collections
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
n, m = map(int, input().split())
INF = 10**12


class Edge:  # 通常の辺
    def __init__(self, to, cost):
        self.to = to
        self.cost = cost


class Dijkstra:  # ダイクストラ法 O(E * logV)
    def __init__(self, n):
        self.n = n
        self.dist = [INF for _ in range(n)]
        self.edges = [list() for _ in range(n)]
        self.q = collections.deque()

    def calcShortest(self, start):
        self.q.append((start, 0))
        while(len(self.q) != 0):
            v, cost = self.q.popleft()
            if self.dist[v] < cost:
                continue
            self.dist[v] = cost
            for edge in self.edges[v]:
                self.q.append((edge.to, cost+edge.cost))

    def addEdge(self, st, gl, cost):
        self.edges[st].append(Edge(gl, cost))


v = Dijkstra(n)
for _ in range(m):
    a, b = map(int, input().split())
    v.addEdge(a-1, b-1, 1)
    v.addEdge(b-1, a-1, 1)

v.calcShortest(0)
if v.dist[n-1] <= 2:
    print('POSSIBLE')
    exit(0)
print('IMPOSSIBLE')


### FIXED CODE ###

# ABC068c
import collections
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
n, m = map(int, input().split())
INF = 10**12


class Edge:  # 通常の辺
    def __init__(self, to, cost):
        self.to = to
        self.cost = cost


class Dijkstra:  # ダイクストラ法 O(E * logV)
    def __init__(self, n):
        self.n = n
        self.dist = [INF for _ in range(n)]
        self.edges = [list() for _ in range(n)]
        self.q = collections.deque()

    def calcShortest(self, start):
        self.q.append((start, 0))
        while(len(self.q) != 0):
            v, cost = self.q.popleft()
            if cost > 3:
                continue
            if self.dist[v] <= cost:
                continue
            self.dist[v] = cost
            for edge in self.edges[v]:
                self.q.append((edge.to, cost+edge.cost))

    def addEdge(self, st, gl, cost):
        self.edges[st].append(Edge(gl, cost))


v = Dijkstra(n)
for _ in range(m):
    a, b = map(int, input().split())
    v.addEdge(a-1, b-1, 1)
    v.addEdge(b-1, a-1, 1)

v.calcShortest(0)
if v.dist[n-1] <= 2:
    print('POSSIBLE')
    exit(0)
print('IMPOSSIBLE')
### BUGGY CODE ###

def main():
    X = input()
    count = 0
    for i in range(10**3):
        count += X.count("ST")
        X = X.replace("ST","")
    print(len(X))


if __name__ == '__main__':
    main()

### FIXED CODE ###

from collections import deque
def main():
    X = input()
    stack = deque([])
    for i in range(len(X)):
        if X[i] == "S":
            stack.append(X[i])
        else:
            if len(stack) != 0:
                tmp = stack.pop()
                if tmp == "T":
                    stack.append(tmp)
                    stack.append(X[i])
            else:
                stack.append(X[i])
    print(len(stack))
if __name__ == '__main__':
    main()
### BUGGY CODE ###

def dp_fn():
  N, W = map(int, input().split())
  WV = (map(int, input().split()) for _ in range(N))
  
  DP = {0:0}
  
  for w, v in WV:
    keys = sorted(list(DP.keys()), reverse=True)
    for i in keys:
      if i + w <= W:
        if i+w in DP:
          DP[i+w] = max(DP[i] + v, DP[i+w])
        else:
          DP[i+w] = DP[i] + v
  return max(DP.values())
  
print(dp_fn())


### FIXED CODE ###

import sys
input = sys.stdin.readline

def dp_fn():
  N, W = map(int, input().split())
  WV = (map(int, input().split()) for _ in range(N))
  
  DP = {0:0}
  
  for w, v in WV:
    keys = sorted(DP.keys(), reverse=True)
    for i in keys:
      j = DP[i]
      if j+w <= W:
        if i+v in DP:
          DP[i+v] = min(DP[i+v], j+w)
        else:
          DP[i+v] = j+w
  return max(DP.keys())
  
print(dp_fn())
### BUGGY CODE ###

import math
from functools import reduce

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

k = int(input())
sum_ans = 0
for a in range(1, k+1):
    for b in range(1, k+1):
        for c in range(1, k+1):
            gcd_abc = gcd(a, b, c)
            sum_ans += gcd_abc
print(sum_ans)

### FIXED CODE ###

import math

k = int(input())
ans = 0
for a in range(1, k+1):
    for b in range(1, k+1):
        gcd_ab = math.gcd(a, b)
        for c in range(1, k+1):
            ans += math.gcd(gcd_ab, c)
print(ans)
### BUGGY CODE ###

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

num_counts = {}
if len(set(num_lists)) <= k:
  ans = 0
else:
  for i in set(num_lists):
    num_counts[i] = num_lists.count(i)
    numbers = list(num_counts.values())
    numbers.sort()
    ans = 0
  for i in range(len(set(num_lists)) - k):
    ans += numbers[i]

print(ans)

### FIXED CODE ###

from collections import Counter

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

num_counts = dict()
length = len(set(num_lists))
ans = 0

if length > k:
  d = Counter()
  d.update(num_lists)
  count_sorted = list(d.values())
  count_sorted.sort()
  for i in range(length - k):
    ans += count_sorted[i]

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

from collections import deque


H, W = map(int, input().split())
Ch, Cw = map(lambda x: int(x) - 1, input().split())
Dh, Dw = map(lambda x: int(x) - 1, input().split())
maze = [input() for _ in range(H)]

INF = 10 ** 12
path = [[INF] * W for _ in range(H)]  # path: 各マスへの移動コスト

# walk:移動A, warp:移動B
walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

q = deque()
path[Ch][Cw] = 0
q.append((Ch, Cw, 0))

while q:
    x, y, s = q.popleft()
    for dx, dy in walk:  # 移動A
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s:
            path[nx][ny] = s
            q.appendleft((nx, ny, s))  # 移動Aの場合はコスト0. キューの先頭に追加する.
    for dx, dy in warp:  # 移動B
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s + 1:
            path[nx][ny] = s + 1
            q.append((nx, ny, s + 1))  # 移動Bの場合はコスト1. キューの最後尾に追加する.
    
ans = path[Dh][Dw] if path[Dh][Dw] < INF else '-1'
print(ans)

### FIXED CODE ###

from collections import deque

h, w = map(int, input().split())
c = list(map(int, input().split()))
d = list(map(int, input().split()))
s = [list(input()) for _ in range(h)]

c = [i-1 for i in c]
d = [i-1 for i in d]

t0 = [(0, 1), (0, -1), (1, 0), (-1, 0)]
t1 = []
for i in range(-2, 3):
    for j in range(-2, 3):
        t1.append((i, j))
for i in t0:
    t1.remove(i)
t1.remove((0, 0))

check = [[-1]*w for _ in range(h)]
q = deque()
q.appendleft((c[0], c[1], 0))

while q:
    y, x, b = q.pop()
    if x == d[1] and y == d[0]:
        print(b)
        exit()
    if check[y][x] == -1:
        check[y][x] = b
        for dy, dx in t0:
            ydy, xdx = y+dy, x+dx
            if (0 <= xdx < w) and (0 <= ydy < h):
                if s[ydy][xdx] == '.' and check[ydy][xdx] == -1:
                    q.append((ydy, xdx, b))
        for dy, dx in t1:
            ydy, xdx = y+dy, x+dx
            if (0 <= xdx < w) and (0 <= ydy < h):
                if s[ydy][xdx] == '.' and check[ydy][xdx] == -1:
                    q.appendleft((ydy, xdx, b+1))
print(-1)
### BUGGY CODE ###

a,b,k=map(int,input().split())
l=[]
ll=[]
for i in range(a,b+1):
    l.append(i)
i=0
j=0
while True:
    print(l[0])
    l.pop(0)
    j+=1
    if len(l)==0 or j==k:
        break
while True:   
    if len(l)==0 or i==k:
        break    
    ll.append(l[-1])
    l.pop()
    i+=1
ll.sort()
for i in range(len(ll)):
    print(ll[i])

### FIXED CODE ###

a,b,k=map(int,input().split())
if k*2>b:
    for i in range(a,b+1):
        if i<a+k:
            print(i)
        elif b-k<i:
            print(i)
else:
    for i in range(a,min(a+k,b+1)):
        print(i)
    for i in range(max(a+k,b-k+1),b+1):
        print(i)
### BUGGY CODE ###

S = input()
from collections import Counter
def solve(S):
    n = len(S)
    cum = [0]*(n+1)
    for i in range(n):
        cum[i+1] = (cum[i]+int(S[n-1-i])*10**i)%2019
    c = Counter(cum)
    ans = 0
    for v in c.values():
        ans += v*(v-1)//2
    return ans
print(solve(S))

### FIXED CODE ###

S = [int(i) for i in input()]

def solve(S):
    n = len(S)
    cum = [0]*(n+1)
    mods = [0]*n
    mods[0] = 1
    for i in range(1,n):
        mods[i] = mods[i-1]*10%2019
    for i in range(n):
        cum[i+1] = (cum[i]+S[n-1-i]*mods[i])%2019
    c = [0]*2019
    for i in range(n+1):
        c[cum[i]] += 1
    ans = 0
    for v in c:
        ans += v*(v-1)//2
    return ans
print(solve(S))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
C - Dice and Coin
https://atcoder.jp/contests/abc126/tasks/abc126_c

"""
import sys


from decimal import *
from math import log2, ceil

def solve(N, K):
    getcontext().prec = 50
    ans = Decimal(0)
    for i in range(1, N+1):
        if i >= K:
            t = Decimal (1/N)
        else:
            t = Decimal(1/N/2**ceil(log2(K/i)))
        ans += t
    return ans


def main(args):
    N, K = map(int, input().split())
    ans = solve(N, K)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])


### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
C - Dice and Coin
https://atcoder.jp/contests/abc126/tasks/abc126_c

"""
import sys


from decimal import *
from math import log2, ceil

#TLE
def __solve(N, K):
    getcontext().prec = 30
    ans = Decimal(0)
    for i in range(1, N+1):
        if i >= K:
            t = Decimal (1/N)
        else:
            t = Decimal(1/N/2**ceil(log2(K/i)))
        ans += t
    return ans


def solve(N, K):
    ans = 0
    for i in range(1, N+1):
        if i >= K:
            t = 1 / N
        else:
            t = 1/N/2**ceil(log2(K/i))
        ans += t
    return ans


def main(args):
    N, K = map(int, input().split())
    ans = solve(N, K)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])
### BUGGY CODE ###

N, T = map(int, input().split())
A = [int(i) for i in input().split()]

c = 0
MAX = 0
for i in range(N-1):
    for j in range(N-1-i):
        if MAX == A[i+1+j] - A[i]:
            c += 1
        elif MAX < A[i+1+j] - A[i]:
            MAX = A[i+1+j] - A[i]
            c = 1
print(c)


### FIXED CODE ###

N, T = map(int, input().split())
A = [int(i) for i in input().split()]

c = 0
MAX = 0
a1 = A[0]
for i in range(N-1):
    if A[i] <= a1:
        a1 = A[i]
    a2 = A[i+1]
    if MAX == a2 - a1:
        c += 1
    elif MAX < a2 - a1:
        MAX = a2 - a1
        c = 1
print(c)