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

n = int(input())

t = []

for i in range(n):
    t.append(int(input()))

buy = t[0]
sell = max(t[1:])
val = sell - buy

for i in range(n-1):
    m = max(t[i+1:])
    val2 = m - t[i]
    if val2 > val:
        buy = t[i]
        sell = m
        val = val2

print(val)



### FIXED CODE ###

n = int(input())

t = []

for i in range(n):
    t.append(int(input()))

buy = t[0]
val = t[-1] - buy

for i in range(1, n):
    if t[i] - buy > val:
        val = t[i] - buy
    if t[i] < buy:
        buy = t[i]

print(val)
### BUGGY CODE ###

N=int(input())
L= list(map(int,input().split()))
L_sorted=sorted(L,reverse=False)#昇順
count=0
for i in range(N):
    for j in range(i+1,N):
        a=L_sorted[i]
        b=L_sorted[j]
        n=a+b
        fin=N
        sta=0
        while sta+1<fin:
            m=((fin-sta)//2)+sta
            if L_sorted[m]<n:
                sta=m       
            else:
                fin=m   
        count+=sta-j
print(count)

### FIXED CODE ###

N=int(input())
L= list(map(int,input().split()))
L_sorted=sorted(L,reverse=False)#昇順
count=0
for i in range(N):
    for j in range(i+1,N):
        a=L_sorted[i]
        b=L_sorted[j]
        n=a+b
        fin=N
        sta=0
        while sta+1<fin:
            m=((fin-sta)//2)+sta
            if L_sorted[m]<n:
                sta=m       
            else:
                fin=m   
        count+=sta-j
print(count)
### BUGGY CODE ###

s = input()
K = int(input())
substrings = {s[i:j]:0 for i in range(len(s)) for j in range(i+1, len(s)+1) if len(s[i:j]) <= K}
print(sorted(substrings)[K-1])


### FIXED CODE ###

s = input()
K = int(input())
substrings = {s[i:j]:0 for i in range(len(s)) for j in range(i+1, min(i+1+K, len(s)+1))}
print(sorted(substrings)[K-1])
### BUGGY CODE ###

mod=10**9+7

n,a,b=map(int,input().split())
res=pow(2,n,mod)
res=(res-1)%mod

up=1
down=1
for i in range(1,b+1):
	up*=(n-i+1)
	up%mod
	down*=i
	if i==a:
		upa=up
		downa=down

nca=upa%mod
nca*=pow(downa,mod-2,mod)
nca%=mod
ncb=(up%mod)
ncb*=pow(down,mod-2,mod)
ncb%=mod
print((res-nca-ncb)%mod)

### FIXED CODE ###

mod=10**9+7

n,a,b=map(int,input().split())
res=pow(2,n,mod)
res=(res-1)%mod

ncb=1
for i in range(1,b+1):
	ncb*=(n-i+1)*pow(i,mod-2,mod)
	ncb%=mod
	if i==a:
		nca=ncb
		
print((res-nca-ncb)%mod)
### BUGGY CODE ###

from collections import deque
import sys
input = sys.stdin.readline

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

graph = [[] for i in range(N)]
dis = [[None]*N for i in range(N)]

for i in range(M):
    L,R,D = map(int,input().split())
    L -= 1
    R -= 1
    graph[L].append(R)
    graph[R].append(L)
    dis[L][R] = D
    dis[R][L] = (-1)*D

data = [None]*N

for i in range(N):
    if data[i] != None:
        continue
    data[i] = 0
    stack = deque()
    stack.append(i)
    while stack:
        x = stack.popleft()
        for y in graph[x]:
            if data[y] == None:
                data[y] = data[x] + dis[x][y]
                stack.append(y)
            else:
                if data[y] - data[x] != dis[x][y]:
                    print("No")
                    sys.exit()
    
print("Yes")



### FIXED CODE ###

from collections import deque
import sys
input = sys.stdin.readline

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

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

for i in range(M):
    L,R,D = map(int,input().split())
    L -= 1
    R -= 1
    graph[L].append([R,D])
    graph[R].append([L,-D])
    
data = [None]*N

for i in range(N):
    if data[i] != None:
        continue
    data[i] = 0
    stack = deque()
    stack.append(i)
    while stack:
        x = stack.popleft()
        for y in graph[x]:
            if data[y[0]] == None:
                data[y[0]] = data[x] + y[1]
                stack.append(y[0])
            else:
                if data[y[0]] - data[x] != y[1]:
                    print("No")
                    sys.exit()
    
print("Yes")
### BUGGY CODE ###

def main():
    N = int(input())
    L = list(map(int, input().split()))
    sort_L = sorted(L)
    cnt = 0
    for i in range(N):
        for j in range(i+1,N):
            if i == j:
                continue
            for k in range(N-1,max(i,j),-1):
                if sort_L[i] + sort_L[j] > sort_L[k]:
                    cnt += 1

    print(cnt)

    

if __name__ == "__main__":
    main()

### FIXED CODE ###

import bisect

def main():
    N = int(input())
    L = list(map(int, input().split()))
    sort_L = sorted(L)
    cnt = 0
    for i in range(N-2):
        for j in range(i+1,N-1):
            tmp = bisect.bisect_left(sort_L,sort_L[i] + sort_L[j])
            if tmp - 1 > j:
                cnt += tmp - j - 1
    print(cnt)

    

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

n, m = map(int, input().split())
h = list(map(int, input().split()))

edges = [[0 for _ in range(n)] for _ in range(n)]

for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    edges[a][b] = 1
    edges[b][a] = 1

ans = 0

for own in range(n):
    is_good = True
    for pair in range(n):
        if edges[own][pair] == 1:
            if h[own] <= h[pair]:
                is_good= False
    if is_good:
        ans += 1

print(ans)

### FIXED CODE ###

n, m = map(int, input().split())
h = list(map(int, input().split()))

edges = [[] for _ in range(n)]

for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    edges[a].append(b)
    edges[b].append(a)

ans = 0

for own in range(n):
    is_good = True
    for pair in edges[own]:
        if h[own] <= h[pair]:
            is_good= False
    if is_good:
        ans += 1

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

def main():
  s = input()
  divisor = 10 ** 9 + 7
  lut = [i % 13 for i in range(133)]
  m = [i * 10 % 13 for i in range(13)]
  dp = [[0] * 13 for _ in range(len(s) + 1)]
  dp[0][0] = 1
  list10 = list(range(10))
  list13 = list(range(13))
  for i in range(len(s)):
    dpi = dp[i]
    dpi1 = dp[i + 1]
    if s[i] == '?':
      for j in list10:
        for k in list13:
          dpi1[lut[m[k] + j]] += dpi[k]
    else:
      t = int(s[i])
      for k in list13:
        dpi1[lut[m[k] + t]] += dpi[k]
    for k in range(13):
      dpi1[k] %= divisor
  print(dp[len(s)][5])
main()


### FIXED CODE ###

s = ''.join(reversed(input()))
multiplier = 1
divisor = 10 ** 9 + 7
p = [0 for i in range(13)]
if s[0] != '?':
  p[int(s[0])] = 1
else:
  for j in range(10):
    p[j] = 1
for i in range(1, len(s)):
  multiplier = (10 * multiplier) % 13
  np = [0 for j in range(13)]
  if s[i] != '?':
    r = int(s[i]) * multiplier
    for j in range(13):
      np[(j + r) % 13] = p[j]
  else:
    for j in range(10):
      r = j * multiplier
      for k in range(13):
        np[(k + r) % 13] += p[k]
  for j in range(13):
    p[j] = np[j] % divisor
print(p[5] % divisor)
### BUGGY CODE ###

class SegmentTree():
    def __init__(self, S):
        self.size = 19
        self.array = [set()] * (2**(self.size + 1) - 1)
        for i, c in enumerate(S):
            self.array[i + 2**self.size - 1] = {c}
        for i in range(2**self.size - 1)[::-1]:
            self.array[i] = self.array[2 * i + 1] | self.array[2 * i + 2]

    def subquery(self, l, r, k, i, j):
        # 区間[i,j)の中で区間[l,r)の文字列の集合を返す
        if j <= l or r <= i:
            return set()
        elif l <= i and j <= r:
            return self.array[k]
        else:
            l_set = self.subquery(l, r, 2 * k + 1, i, (i + j) // 2)
            r_set = self.subquery(l, r, 2 * k + 2, (i + j) // 2, j)
            return l_set | r_set

    def query(self, l, r):
        # [l,r)に含まれる文字の種類数
        return len(self.subquery(l, r, 0, 0, 2**self.size))

    def update(self, i, c):
        tmp = i + 2**self.size - 1
        self.array[tmp] = {c}
        while tmp > 0:
            tmp = (tmp - 1) // 2
            self.array[tmp] = self.array[2 * tmp + 1] | self.array[2 * tmp + 2]


def main():
    N = int(input())
    S = [ord(_) - 97 for _ in list(input())]
    Q = int(input())
    tree = SegmentTree(S)
    for q in range(Q):
        t, i, c = input().split()
        if t == '1':
            i = int(i) - 1
            tree.update(i, ord(c) - 97)
        else:
            l, r = int(i) - 1, int(c)
            print(tree.query(l, r))


if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline


class SegmentTree():
    def __init__(self, S):
        self.size = 19
        self.array = [set()] * (2**(self.size + 1) - 1)
        for i, c in enumerate(S):
            self.array[i + 2**self.size - 1] = {c}
        for i in range(2**self.size - 1)[::-1]:
            self.array[i] = self.array[2 * i + 1] | self.array[2 * i + 2]

    def subquery(self, l, r, k, i, j):
        # 区間[i,j)の中で区間[l,r)の文字列の集合を返す
        if j <= l or r <= i:
            return set()
        elif l <= i and j <= r:
            return self.array[k]
        else:
            l_set = self.subquery(l, r, 2 * k + 1, i, (i + j) // 2)
            r_set = self.subquery(l, r, 2 * k + 2, (i + j) // 2, j)
            return l_set | r_set

    def query(self, l, r):
        # [l,r)に含まれる文字の種類数
        return len(self.subquery(l, r, 0, 0, 2**self.size))

    def update(self, i, c):
        tmp = i + 2**self.size - 1
        self.array[tmp] = {c}
        while tmp > 0:
            tmp = (tmp - 1) // 2
            self.array[tmp] = self.array[2 * tmp + 1] | self.array[2 * tmp + 2]


def main():
    N = int(input())
    S = [ord(_) - 97 for _ in list(input())]
    Q = int(input())
    tree = SegmentTree(S)
    for q in range(Q):
        t, i, c = input().split()
        if t == '1':
            i = int(i) - 1
            tree.update(i, ord(c) - 97)
        else:
            l, r = int(i) - 1, int(c)
            print(tree.query(l, r))


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

from collections import Counter
n = int(input())
s = input()
c = Counter(s)
rgb = set(['R', 'G', 'B'])
ans = c['R']*c['G']*c['B']
for i in range(n-2):
    for j in range(i+1, n-1):
        if n <= 2*j-i:
            continue
        if {s[i], s[j], s[2*j-i]} == rgb:
            ans -= 1

print(ans)


### FIXED CODE ###

from collections import Counter
from operator import mul
n = int(input())
s = input()
c = Counter(s)
if n < 3:
    print(0)
    exit()
elif len(c.keys()) < 3:
    print(0)
    exit()
ans = 0
for i in range(n):
    x = s[i]
    ans += mul(*[v for k, v in c.items()if k != x])
    c[x] -= 1
    for j in range(i+1, n):
        y = s[j]
        if x == y:
            continue
        idx_diff = j-i
        if n <= j+idx_diff:
            continue
        z = s[j+idx_diff]
        if x != z and y != z:
            ans -= 1
print(ans)
### BUGGY CODE ###

N=int(input())
A=list(map(int, input().split()))
A=sorted(A)
import math
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr
if A==[1]*N:
  print('pairwise coprime')
  exit()
a=A[0]
d=a
if A[0]!=1:
  D={}
  x=0
  for i in range(N):
    d=math.gcd(d,A[i])
    c=A[i]
    F=factorization(A[i])
    for a,b in F:
      if a not in D:
        D[a]=1
      else:
        x=1
      #互いに素じゃない二組がある  

  if x==1 and d==1:
    print('setwise coprime')
  elif x==0 and d==1:
    print('pairwise coprime')
  else:
    print('not coprime')
else:
  D={}
  x=0
  for i in range(N):
    if A[i]!=1:
      F=factorization(A[i])
      for a,b in F:
        if a not in D:
          D[a]=1
        else:
          x=1
    
  if x==1:
    print('setwise coprime')
  else:
    print('pairwise coprime')

### FIXED CODE ###

N=int(input())
A=list(map(int, input().split()))
A=sorted(A)
import math
import bisect
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr
if A==[1]*N:
  print('pairwise coprime')
  exit()
a=A[0]
d=a
if A[0]!=1:
  D={}
  x=0
  for i in range(N):
    if d!=1:
      d=math.gcd(d,A[i])
    c=A[i]
    if x==0:
      F=factorization(A[i])
      for a,b in F:
        if a not in D:
          D[a]=1
        else:
          x=1
        #互いに素じゃない二組がある  
    if x==1 and d==1:
      break

  if x==1 and d==1:
    print('setwise coprime')
  elif x==0 and d==1:
    print('pairwise coprime')
  else:
    print('not coprime')
else:
  l=bisect.bisect_right(A,1)
  A=A[l:]
  D={}
  x=0
  for i in range(len(A)):
    F=factorization(A[i])
    for a,b in F:
      if a not in D:
        D[a]=1
      else:
        x=1
    if x==1:
      break
    
  if x==1:
    print('setwise coprime')
  else:
    print('pairwise coprime')
### BUGGY CODE ###

R,G,B,N=[int(c) for c in input().split()]

C=sorted([R,G,B])

count=0
for i in range(N//C[2]+1):
	for j in range(N//C[1]+1):
		if(N-C[2]*i-C[1]*j>=0 and (N-C[2]*i-C[1]*j)%C[0]==0):
			count+=1
print(count)




### FIXED CODE ###



R,G,B,N=[int(c) for c in input().split()]

C=sorted([R,G,B])



if(C==[1,1,1]):
	print((N+2)*(N+1)//2)
	exit()






count=0
for i in range(N//C[2]+1):
	for j in range(N//C[1]+1):
		if(N-C[2]*i-C[1]*j>=0 and (N-C[2]*i-C[1]*j)%C[0]==0):
			count+=1
print(count)
### BUGGY CODE ###

import numpy as np
n, q = (int(_) for _ in input().split())  
arr = np.array([[1 if i == j else 0 for i in range(n)] for j in range(n)])
output = np.array([0 for i in range(n)])
ab = []
for i in range(n-1):
  a, b = (int(_) for _ in input().split()) 
  ab.append([a, b])
  
for x in reversed(ab):
  a = x[0]
  b = x[1]
  arr[a-1] = arr[a-1] | arr[b-1]

for i in range(q):
  p, q = (int(_) for _ in input().split()) 
  output += arr[p-1] * q
    
print(' '.join([str(x) for x in output]))

### FIXED CODE ###

n,q=map(int,input().split())
a=[0]*(n-1)
c=[0 for i in range(n)]
for i in range(n-1):
  a[i]=list(map(int,input().split()))

a.sort()

for i in range(q):
  x,y=map(int,input().split())
  c[x-1]+=y

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

print(*c)
### BUGGY CODE ###

import numpy as np

N,M = map(int, input().split())
X = [list(map(int, input().split()))+[1] for _ in range(M)]
X = np.array(X, dtype=int)
for i in range(1,N+1):
    a = X[:,0]==i
    X[a, 2] = np.argsort(np.argsort(X[a, 1]))+1
for x in X:
    print('{:06}{:06}'.format(x[0], x[2]))

### FIXED CODE ###

import numpy as np

N,M = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(M)]
order = [[] for _ in range(N)]
for p,y in X:
    order[p-1].append(y)
#X = np.array(X, dtype=int)
for i in range(N):
    order[i] = np.argsort(np.argsort(order[i]))
cnts = [0 for _ in range(N)]
for i in range(M):
    p = X[i][0]
    print('{:06}{:06}'.format(p, order[p-1][cnts[p-1]]+1) )
    cnts[p-1] += 1
### BUGGY CODE ###

import sys
sys.setrecursionlimit(100000)

N,K=map(int,input().split())
SIZE=10**5+1; MOD=10**9+7 #998244353 #ここを変更する
 
SIZE += 1
inv = [0]*SIZE  # inv[j] = j^{-1} mod MOD
fac = [0]*SIZE  # fac[j] = j! mod MOD
finv = [0]*SIZE # finv[j] = (j!)^{-1} mod MOD
inv[1] = 1
fac[0] = fac[1] = 1
finv[0] = finv[1] = 1
for i in range(2,SIZE):
  inv[i] = MOD - (MOD//i)*inv[MOD%i]%MOD
  fac[i] = fac[i-1]*i%MOD
  finv[i]= finv[i-1]*inv[i]%MOD

def narabekae(n,r): #nPr mod MOD の計算
  if n-r<0:
    return 0
  return fac[n]*finv[n-r]%MOD

branch=[[] for _ in range(N)]
for i in range(N-1):
  a,b=map(int,input().split())
  branch[a-1].append(b-1)
  branch[b-1].append(a-1)

ans=1

def draw(parent,nord):
  global ans
  children=len(branch[nord])-(parent !=-1)
  if children==0:
    return
  #(K-2)*(K-1)*... をchildrenの数だけ掛ける。
  ans=ans*narabekae(K-1-(parent !=-1),children)%MOD
  for b in branch[nord]:
    if b != parent:
      draw(nord,b)

draw(-1,0)
print(ans*K%MOD)

### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)

N,K=map(int,input().split())
MOD=10**9+7
branch=[[] for _ in range(N)]
for i in range(N-1):
  a,b=map(int,input().split())
  branch[a-1].append(b-1)
  branch[b-1].append(a-1)

if K==1:
  if N==1:
    print(1)
  else:
    print(0)
  exit()
  
P=[0]*(K-1)
P[K-2]=K-2
for i in range(K-3,0,-1):
  P[i]=P[i+1]*i%MOD
  
def PPP(start,num):
  if start<num:
    return 0
  if start==K-2:
    return P[start-num+1]
  if start==K-1:
    return P[start-num+2]*(K-1)%MOD
  
ans=1

def draw(parent,nord):
  global ans
  children=len(branch[nord])-(parent !=-1)
  if children==0:
    return
  #(K-2)*(K-1)*... をchildrenの数だけ掛ける。
  ans=ans*PPP(K-1-(parent !=-1),children)%MOD
  for b in branch[nord]:
    if b != parent:
      draw(nord,b)

for i in range(len(branch[0])+1):
  ans=ans*(K-i)%MOD
for bra in branch[0]:
  draw(0,bra)
print(ans)
### BUGGY CODE ###

import collections

h, w = map(int, input().split())

ss = [input() for _ in range(h)]
start = [0,0]
goal = [w-1,h-1]
wall_count = 0
for s in ss:
    wall_count += s.count("#")

min_count = h*w
dx = [1,-1,0,0]
dy = [0,0,1,-1]

stack = collections.deque([start])
visited = [[h*w for _ in range(h)] for _ in range(w)]
visited[start[0]][start[1]] = 1

while len(stack) > 0:
    pos = stack.pop()
    
    for x,y in zip(dx, dy):
        next = [pos[0]+x, pos[1]+y]
        
        if next[0]<0 or w-1<next[0] or next[1]<0 or h-1<next[1]:
            continue
        if ss[next[1]][next[0]] == "#":
            continue
        if visited[next[0]][next[1]] < visited[pos[0]][pos[1]] + 1:
            continue
        stack.append(next)
        visited[next[0]][next[1]] = visited[pos[0]][pos[1]] + 1

if visited[w-1][h-1] == h*w:
    print("-1")
else:
    score = (h*w) - wall_count - visited[w-1][h-1]
    print(score)

### FIXED CODE ###

import collections

h, w = map(int, input().split())

ss = [input() for _ in range(h)]
start = [0,0]
goal = [w-1,h-1]
wall_count = 0
for s in ss:
    wall_count += s.count("#")

dx = [1,-1,0,0]
dy = [0,0,1,-1]

stack = collections.deque([start])
visited = [[-1 for _ in range(h)] for _ in range(w)]
visited[start[0]][start[1]] = 1

while len(stack) > 0:
    pos = stack.pop()
    if pos == goal:
        break
    
    for x,y in zip(dx, dy):
        next_pos = [pos[0]+x, pos[1]+y]
        
        if next_pos[0]<0 or (w-1)<next_pos[0] or next_pos[1]<0 or (h-1)<next_pos[1]:
            continue
        if ss[next_pos[1]][next_pos[0]] == "#":
            continue
        if visited[next_pos[0]][next_pos[1]] != -1:
            continue
        stack.appendleft(next_pos)
        visited[next_pos[0]][next_pos[1]] = visited[pos[0]][pos[1]] + 1

if visited[w-1][h-1] == -1:
    print("-1")
else:
    score = (h*w) - wall_count - visited[w-1][h-1]
    print(score)
### BUGGY CODE ###

N=int(input())

P=[]

for i in range(N):
    A=input()
    if A in P:
        P.remove(A)
    else:
        P.append(A)
        
print(len(P))

### FIXED CODE ###

N=int(input())

P=set()

for i in range(N):
    A=input()
    if A in P:
        P.remove(A)
    else:
        P.add(A)
        
print(len(P))
### BUGGY CODE ###

N = map(int, input().split())
A = list(map(int, input().split()))
ans = A[0]
for a in A[1:]:
    ans *= a
if ans > 10**18:
    ans = -1
print(ans)

### FIXED CODE ###

N = map(int, input().split())
A = list(reversed(sorted(list(map(int, input().split())))))
if A[-1] == 0:
    ans = 0
else:
    ans = A[0]
    for a in A[1:]:
        ans *= a
        if ans > 10**18:
            ans = -1
            break
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline

 
N, K = list(map(int, input().split()))
ab = []
for i in range(N-1):
    ab.append(list(map(int, input().split())))
 
ki = []
 
for i in range(N):
    ki.append(dict())
    ki[-1]["eda"] = []
 
for i in range(N-1):
    ki[ab[i][0] - 1]["eda"].append([ab[i][0] - 1, ab[i][1] - 1])
    ki[ab[i][1] - 1]["eda"].append([ab[i][1] - 1, ab[i][0] - 1])
 
def P(m ,n):
    if m <= 0 or n <= 0:
        return 0
    else:
        num = 1
        for i in range(n):
            num *= m-i
        return num
 
def saiki(i, base, ki):
    num = 1
    eda_num = len(ki[i]["eda"])-1
    if eda_num == 0:
        return num
    num *= P(K-2, eda_num)
 
    for edge in ki[i]["eda"]:
        if edge[1] != base:
            num *= saiki(edge[1], i, ki)
            num = num % 1000000007
            #print(num)
 
    return num
 
total_num = K
if len(ki[0]["eda"]) != 0:
    total_num *= P(K-1, len(ki[0]["eda"]))
    for edge in ki[0]["eda"]:
        total_num *= saiki(edge[1], 0, ki)
        total_num = total_num % 1000000007
        if total_num == 0:
            break
 
print(total_num)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
INF=10**9+7
def LI(): return list(map(int, sys.stdin.readline().split()))
 
def main():
    n, k = LI()
    graph=[[] for i in range(n)]
    for i in range(n-1):
        a,b=LI()
        graph[a-1].append(b-1)
        graph[b-1].append(a-1)
    ans=1
    check=[False]*n
    stack=[0]
    ans=1
    while len(stack)>0:
        x=stack.pop()
        check[x]=True
        count=0
        for i in graph[x]:
            if not check[i]:
                count+=1
                stack.append(i)
        if x==0:
            temp=1
            for i in range(count):
                temp=temp*(k-1-i)%INF
            ans=ans*temp%INF
        else:
            temp=1
            for i in range(count):
                temp=temp*(k-2-i)%INF
            ans=ans*temp%INF
    print((ans*k)%INF)
 
 
if __name__ == "__main__":
    main()
### BUGGY CODE ###

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

s = input()
q = int(input())
qs = [list(input().split()) for i in range(q)]

q1_cnt = 0
for qi in qs:
    if qi[0]=="1":
        q1_cnt+=1
    else:
        if q1_cnt%2==0:
            if qi[1]=="1":
                s = qi[2]+s
            else:
                s = s+qi[2]
        else:
            if qi[1]=="1":
                s = s+qi[2]
            else:
                s = qi[2]+s

if q1_cnt%2==1:
    s = s[::-1]
print(s)

### FIXED CODE ###

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

s = input()
q = int(input())
qs = [list(input().split()) for i in range(q)]

pls_vec = []
pls_append = pls_vec.append

mns_vec = []
mns_append = mns_vec.append

q1_vec = 1
for qi in qs:
    if qi[0]=="1":
        q1_vec*=(-1)
    else:
        if q1_vec==1:
            if qi[1]=="1":
                mns_append(qi[2])
            else:
                pls_append(qi[2])
        else:
            if qi[1]=="1":
                pls_append(qi[2])
            else:
                mns_append(qi[2])

ret = "".join(mns_vec[::-1]) + s + "".join(pls_vec)
if q1_vec==-1:
    ret=ret[::-1]
print(ret)
### BUGGY CODE ###

N, k = map(int, input().split())
S = list(map(int, input().split()))
S_unique = list(set(S))
S_unique_count = []

for i in range(len(S_unique)):
    tmp = S.count(S_unique[i])
    S_unique_count.append(tmp)

S_unique_count.sort()

ans = sum(S_unique_count[0:len(S_unique_count)-k])
print(ans)

### FIXED CODE ###

import collections

N, k = map(int, input().split())
S = list(map(int, input().split()))
S_unique_count = list(collections.Counter(S).values())

S_unique_count.sort()

ans = sum(S_unique_count[0:len(S_unique_count)-k])
print(ans)
### BUGGY CODE ###

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

for i in range(M):
    B, C = map(int, input().split())
    As.sort()
    for j in range(B):
        if As[j] < C:
            As[j] = C
print(sum(As))

### FIXED CODE ###

N, M = map(int, input().split())
As = list(map(int, input().split()))
adic = {}
for a in As:
    adic[a] = adic.get(a, 0) + 1

Ds = []
for a in adic:
    Ds.append([a, adic[a]])
for i in range(M):
    B, C = map(int, input().split())
    Ds.append([C,B])

Ds.sort(reverse=True)

count, sum = 0,0
for D in Ds:
    c = D[1] if D[1] + count <= N else N - count
    sum += c * D[0]
    count += c
    if count == N:
        break

print(sum)
### BUGGY CODE ###

l, r = map(int, input().split())

ans = 2019
for i in range(l, r + 1):
    for j in range(r, l-1, -1):
        if i == j:
            break
        mod = (i * j) % 2019
        if mod < ans:
            ans = mod

print(ans)


### FIXED CODE ###

l, r = map(int, input().split())
ans = 2019

if r-l >= 2018:
    print(0)
else:
    for i in range(l, r):
        for j in range(r, l, -1):
            ans = min(ans, i*j % 2019)
    
    print(ans)