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

import sys
import numpy as np
def input(): return sys.stdin.readline().rstrip()


def main():
    h, w = map(int, input().split())
    A = np.array([list(map(int, input().split()))
                  for i in range(h)], dtype=int)
    B = np.array([list(map(int, input().split()))
                  for i in range(h)], dtype=int)
    abss = np.abs(A-B)
    kmax = 280
    dp = np.zeros((h, w, kmax), dtype=int)
    dp[0][0][abss[0][0]] = 1
    for i in range(h):
        for j in range(w):
            for k in range(kmax):
                if dp[i][j][k] == 1:
                    if i != h-1:
                        dp[i+1][j][abs(k-abss[i+1][j])] = 1
                        if k+abss[i+1][j] < kmax:
                            dp[i+1][j][k+abss[i+1][j]] = 1
                    if j != w-1:
                        dp[i][j+1][abs(k-abss[i][j+1])] = 1
                        if k+abss[i][j+1] < kmax:
                            dp[i][j+1][k+abss[i][j+1]] = 1
    for k in range(kmax):
        if dp[-1][-1][k] == 1:
            print(k)
            break


if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()


def main():
    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)]
    abss = [[abs(A[i][j]-B[i][j])for j in range(w)] for i in range(h)]
    kmax = 6400
    dp = [[[0]*kmax for j in range(w)]for i in range(h)]
    dp[0][0][abss[0][0]] = 1
    for i in range(h):
        for j in range(w):
            for k in range(kmax):
                if dp[i][j][k] == 1:
                    if i != h-1:
                        dp[i+1][j][abs(k-abss[i+1][j])] = 1
                        if k+abss[i+1][j] < kmax:
                            dp[i+1][j][k+abss[i+1][j]] = 1
                    if j != w-1:
                        dp[i][j+1][abs(k-abss[i][j+1])] = 1
                        if k+abss[i][j+1] < kmax:
                            dp[i][j+1][k+abss[i][j+1]] = 1
    for k in range(kmax):
        if dp[-1][-1][k] == 1:
            print(k)
            break


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

nm = list(map(int, input().split()))
n = nm[0]
m = nm[1]
a = []
b = []

for i in range(n):
    ab = list(map(int, input().split()))
    a.append(ab[0])
    b.append(ab[1])

money = 0
count = 0

while count < m:
    minimum = min(a)
    num = a.index(minimum)
    money = money + minimum * b[num]
    count = count + b[num]
    if count > m:
        money = money - minimum * (count - m)
    del (a[num])
    del (b[num])

print(money)

### FIXED CODE ###

nm = list(map(int, input().split()))
n = nm[0]
m = nm[1]
abs = []

for i in range(n):
    ab = list(map(int, input().split()))
    abs.append(ab)

abs = sorted(abs, key=lambda x: x[0])

money = 0
count = 0

for i in range(n):
    money = money + abs[i][0] * abs[i][1]
    count = count + abs[i][1]
    if count >= m:
        money = money - abs[i][0] * (count - m)
        break

print(money)
### BUGGY CODE ###

from math import floor
a,b,n = map(int,input().split())
if a == 1:
    print(0)
    exit()

prev = 0
for x in range(min(b-1,n),n+1, b):
    val = floor(a*x/b) - a*floor(x/b)
    if val < prev:
        print(prev)
        exit()
    prev = val

val = floor(a*n/b) - a*floor(n/b)
print(max(prev,val))


### FIXED CODE ###

from math import floor
a,b,n = map(int,input().split())
if a == 1 or b == 1:
    print(0)
    exit()

prev = 0

for x in range(min(b-1,n),n+1, b):
    val = floor(a*x/b) - a*floor(x/b)
    if val < prev:
        print(prev)
        exit()
    prev = val

val = floor(a*n/b) - a*floor(n/b)
print(max(prev,val))
### BUGGY CODE ###

N = int(input())
power = 1
for i in range(1,N+1):
    power *= i
print(power%1000000007)

### FIXED CODE ###

N = int(input())
power = 1
for i in range(1,N+1):
    power = power * i % (10**9+7)
print(power)
### BUGGY CODE ###

import sys
readline = sys.stdin.readline
write = sys.stdout.write

# クエリ: "? x1 x2" を出力
def query(x1):
    print(x1, flush=True)
    return readline().split()

n = int(input())
l = 0
r = n-1
mid = r // 2
re = [None] * n
re[0] = query(0)
if re[0] == "Vacant":
  exit()
re[mid] = query(mid)
while re[mid] != "Vacant":
  if re[l] == re[mid]:
    if (mid - l) % 2:
      r = mid
    else:
      l = mid
  else:
    if (mid - l) % 2:
      l = mid
    else:
      r = mid
  mid = (l + r) // 2
  re[mid] = query(mid)
exit()

### FIXED CODE ###

import sys

n = int(input())
l = 0
r = n-1
mid = r // 2
re = [None] * n
print(0, flush=True)
re[0] = input()
if re[0] == "Vacant":
  sys.exit()
print(n-1, flush=True)
re[n-1] = input()
if re[n-1] == "Vacant":
  sys.exit()
print(mid, flush=True)
re[mid] = input()
while re[mid] != "Vacant":
  if re[l] == re[mid]:
    if (mid - l) % 2:
      r = mid
    else:
      l = mid
  else:
    if (mid - l) % 2:
      l = mid
    else:
      r = mid
  mid = (l + r) // 2
  print(mid, flush=True)
  re[mid] = input()
else:
  sys.exit()
### BUGGY CODE ###

"""
最大公約数をもっとも落としている数Xを削る（＝見ないことにする）、という発想に置き換える。
方針１：
Xを特定する。
どうやって特定する？
各Aを素因数分解する。このとき、他の

方針２：
約数をカウントする。すべてのAの約数をカウントして総和する。
このとき、カウントがN個になる約数は初期状態での公約数である。
一方で、カウントがN-1個の約数は、その約数をもたない数が一つだけ存在するということなので、
そのような数Aを削ったときに、公約数になる。
したがって、カウントがN-1個以上の約数のうち最大のものが、数Xを削ったときの最大公約数である。
問題はどうやって約数をカウントするかだ。愚直にやるとO(N√max(A))かかるため間に合わない。
ただ、約数の数自体はせいぜい1000個くらいのはず。いったん素因数分解してから、各素因数を何個累乗させるかで考えればよいか。
"""
def main():
    from collections import Counter
    N = int(input())
    A = list(map(int,input().split()))
    count = {}

    for a in A:
        tmp = []
        d = 2
        while d*d <= a:
            while a%d == 0:
                tmp.append(d)
                a //= d
            d += 1
        if a != 1:
            tmp.append(a)
        divides = [1]
        for k,v in Counter(tmp).items():
            M = len(divides)
            for i in range(1,v+1):
                for j in range(M):
                    divides.append(divides[j]*pow(k,i))
        
        for d in divides:
            if d not in count:
                count[d] = 0
            count[d] += 1

    ans = 0
    for k,v in count.items():
        if v >= N-1:
            ans = max(ans,k)
    print(ans)
main()

### FIXED CODE ###

"""
問題文を言い換えると、「最大公約数が最大になるように数字を一つ書き換えろ」ということ。
さらに言い換えると、「最大公約数が最大になるように数字を一つ消せ」ということ。
単純な線形探索でできるか？→NO

最大公約数を小さくする要因となっている数字を一つ消す。
どういう数字が最大公約数を小さくする要因になっているか？
他の数字と共通する素因数が少ない、小さい、次数が小さい。ただ、この3つを総合的に判断するのは難しすぎる。
素因数分解はやめて、単純に約数で探せばよいか。
各Aの約数を昇順で列挙しておく。
まずA1は必ず残すと仮定して、A1の約数の大きい方から順番に、ほかのAの約数になるかどうかを調べる。
その約数を含んでいないAが一つだけ存在するとき、そのAを消せば、その約数が最大公約数となる。

次に、A1を消す場合の最大公約数も求めて、A1を含める場合の最大公約数と比較して大きい方を採用する。
"""

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

#A1を必ず入れる場合の最大公約数を求める。
yakusu = []

a = A[0]
d = 1
while d*d < a:
    if a % d == 0:
        yakusu.append(d)
        yakusu.append(a//d)
    d += 1
if d*d == a:
    yakusu.append(d)
yakusu.sort(reverse=True)

ans = 1
for v in yakusu:
    cnt = 0
    for i in range(1,N):
        if A[i]%v != 0:
            cnt += 1
    if cnt <= 1:
        ans = v
        break

#A1を入れない場合の最大公約数を求める。
import math
g = A[1]
for i in range(2,N):
    g = math.gcd(g,A[i])

ans = max(ans,g)

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

s = input()
t = input()

dp = [0] * (len(s)+1)
dps = [''] * (len(s)+1)
for i in range(1, len(t)+1):
    ti = t[i-1]
    for j in range(1, len(s)+1):
        sj = s[j-1]
        if ti == sj:
            dp[j] = dp[j-1] + 1
            dps[j] = dps[j-1] + ti
        else:
            if dp[j-1] >= dp[j]:
                dp[j] = dp[j-1]
                dps[j] = dps[j-1]
print(dps[-1])

### FIXED CODE ###

s = input()
t = input()
dp = [[0] * (len(s)+1) for _ in range(len(t)+1)]
for i in range(1, len(t)+1):
    ti = t[i-1]
    dp[i] = dp[i-1][:]
    for j in range(1, len(s)+1):
        if ti == s[j-1]:
            dp[i][j] = dp[i-1][j-1] + 1
        else:
            dp[i][j] = max(dp[i][j-1], dp[i-1][j])

ans = ''
sl = len(s)
tl = len(t)
while sl > 0 and tl > 0:
    if s[sl-1] == t[tl-1]:
        sl -= 1
        tl -= 1
        ans = s[sl] + ans
        continue
    if dp[tl][sl] == dp[tl][sl-1]:
        sl -= 1
    elif dp[tl][sl] == dp[tl-1][sl]:
        tl -= 1
print(ans)
### BUGGY CODE ###

k = int(input())

def gcd(a, b, c):
    mini = a
    if a > b:
        mini = b
    if b > c:
        mini = c
    if (a % mini == 0) & (b % mini == 0) & (c % mini == 0):
        return mini
    for i in range((mini + 1)//2 + 1, 1, -1):
        if (a % i == 0) & (b % i == 0) & (c % i == 0):
            return i
    return 1

s = 0
for i in range(1, k + 1):
    for j in range(1, k + 1):
        for l in range(1, k + 1):
            a = gcd(i, j, l)
            s += int(a)

print(s)

### FIXED CODE ###

k = int(input())

def gcd(a, b, c):
    mini = a
    if a > b:
        mini = b
    if b > c:
        mini = c
    if (a % mini == 0) & (b % mini == 0) & (c % mini == 0):
        return mini
    if mini % 2 == 0:
        h = mini / 2
        if (a % h == 0) & (b % h == 0) & (c % h == 0):
            return h
    for i in range((mini + 1)//3 + 1, 1, -1):
        if (a % i == 0) & (b % i == 0) & (c % i == 0):
            return i
    return 1

s = 0
for i in range(1, k + 1):
    for j in range(1, k + 1):
        for l in range(1, k + 1):
            if i <= j <= l:
                if i < j < l:
                    a = gcd(i, j, l) * 6
                    s += int(a)
                elif ((i == j) & (j != l)) | ((i != j) & (j == l)):
                    a = gcd(i, j, l) * 3
                    s += int(a)
                else:
                    a = gcd(i, j, l) 
                    s += int(a)
            else:
                continue

print(s)
### BUGGY CODE ###

from itertools import combinations

N, K = map(int,input().split())
lists = combinations(range(N),K)
s = list(map(int,input().split()))
min_result = 1000000000000
for li in lists:
    total = 0
    for l in li:
        total += s[l]
    min_result = min(min_result,total)

print(min_result)

### FIXED CODE ###

N, K = map(int,input().split())
s = list(map(int,input().split()))
s.sort()
print(sum(s[:K]))
### BUGGY CODE ###

import heapq
import collections


def main():
    INF = 10**30
    T = int(input())
    cases = [list(map(int, input().split())) for _ in range(T)]
    for case in cases:
        N, A, B, C, D = case
        coins = collections.defaultdict(lambda : INF)
        coins[0] = 0
        frontier = [(0, 0)]
        ans = 0
        while len(frontier) > 0:
            c, node = heapq.heappop(frontier)
            if node == N:
                ans = c
                break
            candidates = [
                (c + A, 2 * node),
                (c + B, 3 * node),
                (c + C, 5 * node),
                (c + D, node + 1),
                (c + D, node - 1)
            ]
            for cand in candidates:
                if cand[1] > 0 and cand[0] < coins[cand[1]]:
                    heapq.heappush(frontier, cand)
        print(ans)


if __name__ == '__main__':
    main()

### FIXED CODE ###

from collections import defaultdict


def calc(case):
    # /2, /3, /5, +-1
    N, A, B, C, D = case
    memo = defaultdict(int)
    x = N
    def dp(n):
        if n == 0:
            return 0
        elif n == 1:
            return D
        elif n == 2:
            return D + min([A, D])
        for k in [2, 3, 5]:
            for i in [0, 1]:
                if memo[n // k + i] == 0:
                    memo[n // k + i] = dp(n // k + i)
        ret = min([
            n * D, 
            A + (n % 2) * D + memo[n // 2],
            A + (2 - n % 2) * D + memo[n // 2 + 1],
            B + (n % 3) * D + memo[n // 3],
            B + (3 - n % 3) * D + memo[n // 3 + 1],
            C + (n % 5) * D + memo[n // 5],
            C + (5 - n % 5) * D + memo[n // 5 + 1]
        ])
        return ret
    return dp(N)


def main():
    T = int(input())
    cases = [list(map(int, input().split())) for _ in range(T)]
    for case in cases:
        print(calc(case))


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

N = int(input())
S = input()
p = 0
def check(l):
  global p
  for i in range(p, N-l):
    s = S[i:i+l]
    if not S.find(s, i+l) < 0:
      p = i
      return True
  return False
a = 1
b = N
while a < b:
  i = (a + b)//2
  if not check(i):
    b = i
  else:
    if a == i:
      break
    a = i
r = b-1
print(r)


### FIXED CODE ###

N = int(input())
S = input()
r = 0
i = j = 0
while j < N:
  t = S[i:j]
  if t in S[j:]:
    r = max(r, j-i)
    j += 1
  else:
    i += 1
print(r)
### BUGGY CODE ###


import sys
input = lambda : sys.stdin.readline().rstrip()
# 小さすぎても怒られるので
from collections import defaultdict
n = int(input())
sys.setrecursionlimit(max(1000, 2*n))

cs = [0] + [int(c) for c in input().split()]
ns = defaultdict(set)
for _ in range(n-1):
    a,b = [int(c) for c in input().split()]
    ns[a].add(b)
    ns[b].add(a)

def dfs(ns, prev, now, toru, results):
    end = defaultdict(int)
    k = cs[now]
    end[k] = 1
    s = 1 # nowで終わるパスの種類
    tmp_s2_sum = 0
    usList = defaultdict(lambda: [0,0,0]) # sum(v), sum(v*s), sum(v**2)
    for u in ns[now]:
        if u==prev:
            continue
        tmp_end, tmp_toru, tmp_s = results[u]  # dfs(ns, now, u, toru)
        for kk,vv in tmp_end.items():
            if kk!=k:
                end[kk] += vv
                usList[kk][0] += vv # .append((vv, tmp_s))
                usList[kk][1] += (vv*tmp_s)
                usList[kk][2] += vv**2
        end[k] += tmp_s
        s += tmp_s
        tmp_s2_sum += tmp_s**2
    for kk,vv in usList.items():
        if kk!=k:
            toru[kk] += (s - 1) * vv[0] - vv[1] - (vv[0]**2 - vv[2]) / 2
            toru[kk] += vv[0]
#             x_sum = 0
#             x2_sum = 0
#             for item in vv:
#                 toru[kk] += (s - item[1]) * item[0]
#                 x_sum += item[0]
#                 x2_sum += item[0]**2
#             toru[kk] -= (x_sum**2 - x2_sum) / 2
    toru[k] += (1 + ((s-1)**2 - tmp_s2_sum)/2 + (s-1))
#     print(now, prev, end, toru, s, usList)
    results[now] = end, toru, s

toru = [0] * (n+1)
q = [(1, -1)] # now, prev
args = []
while q:
    u, prev = q.pop()
    args.append((u,prev))
    for v in ns[u]:
        if prev==v:
            continue
        q.append((v, u))
results = {}
for arg in args[::-1]:
    dfs(ns, arg[1], arg[0], toru, results)

for item in toru[1:]:
    print(int(item))

### FIXED CODE ###


import sys
# 小さすぎても怒られるので
from collections import defaultdict
n = int(input())
sys.setrecursionlimit(max(1000, 2*n))

cs = [0] + [int(c) for c in input().split()]
ns = defaultdict(set)
for _ in range(n-1):
    a,b = [int(c) for c in input().split()]
    ns[a].add(b)
    ns[b].add(a)

ans = [0] * (n+1) # kを通らないパスの総数
minus = [0] * (n+1) # uの部分木のうち
minus0 = defaultdict(int)
st = {k: [] for k in range(1, n+1)}
nextu = {}
def dfs(u, prev, ans):
    global minus, st, minus0
    k = cs[u]
    st[k].append(u)
    ss = 1
    for v in ns[u]:
        if v==prev:
            continue
        nextu[u] = v
        s = dfs(v, u, ans)
        ss += s
        tmp = s - minus[v]
        ans[k] += (int(tmp * (tmp - 1) / 2) + tmp)
    st[k].pop()
    if st[k]:
        minus[nextu[st[k][-1]]] += ss
    else:
        minus0[k] += ss
#     print(ss)
    return ss

dfs(1, -1, ans)
for k in range(1, n+1):
    tmp = n - minus0[k]
    ans[k] += (int(tmp * (tmp - 1) / 2) + tmp)
    
total = int(n * (n+1) / 2)
for i in range(1, n+1):
    print(total - ans[i])
### BUGGY CODE ###

n = int(input())

for i in range(1,3501):
    for j in range(1,3501):
        if 4*i*j-n*(i+j) != 0:
            w = (n*i*j)/(4*i*j-n*(i+j))
            if w > 0 and int(w)==w:
                print(i,end=' ')
                print(j,end=' ')
                print(int(w))
                exit()


### FIXED CODE ###

n = int(input())

for i in range(1,3501):
    for j in range(1,3501):
        if 4*i*j-n*(i+j) != 0:
            w = (n*i*j)/(4*i*j-n*(i+j))
            if w > 0 and int(w)==w:
                print(i,end=' ')
                print(j,end=' ')
                print(int(w))
                exit()
### BUGGY CODE ###

from collections import deque

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

maze = [input() for i in range(h)]

ans = 0
INF = 1e100
for j in range(h):
    for i in range(w):
        if maze[j][i] == ".":
            cnt = [[INF] * w for _ in range(h)] 
            cnt[j][i] = 0
            q = deque([(j,i)])
            while q:
                y,x = q.popleft()
                for by,bx in ((0,1),(0,-1),(1,0),(-1,0)):
                    by += y
                    bx += x 
                    if 0 <= by < h and 0 <= bx < w:
                        if maze[by][bx] == "#": continue
                        ct = cnt[y][x] + 1
                        if ct > cnt[by][bx]: continue 
                        q += [(by,bx)] 
                        cnt[by][bx] = ct
                        ans = max(ans, cnt[by][bx])


print(ans)

### FIXED CODE ###

from collections import deque

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

maze = [input() for i in range(h)]

ans = 0
for j in range(h):
    for i in range(w):
        if maze[j][i] == ".":
            cnt = [[0] * w for _ in range(h)] 
            q = deque([(j,i)])
            while q:
                y,x = q.popleft()
                for by,bx in ((0,1),(0,-1),(1,0),(-1,0)):
                    ny = y + by
                    nx = x + bx
                    if 0 <= ny < h and 0 <= nx < w:
                        if maze[ny][nx] == "." and cnt[ny][nx] == 0:
                            q += [(ny,nx)]
                            cnt[ny][nx] += cnt[y][x] + 1
                            ans = max(ans, cnt[ny][nx])
                if y == j and x == i:
                    cnt[y][x] = -1


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

import math

K = int(input())
cnt = 0
for a in range(1,K+1):    
    for b in range(1,K+1):
        for c in range(1,K+1):
            cnt+=math.gcd(a,math.gcd(b,c))
        
print(cnt)

### FIXED CODE ###

from math import gcd
k = int(input())+1
ans = 0
for i in range(1,k):
    for j in range(1,k):
        for l in range(1,k):
            ans+=gcd(gcd(i,j),l)
print(ans)
### BUGGY CODE ###

n = int(input())
r_s = [int(input()) for i in range(n)]

maxsub = r_s[1] - r_s[0]
mini = r_s[0]

for i in range(n-1):
    if r_s[i] > mini:
        continue

    mini = r_s[i]
    for j in range(i+1, n):
        if maxsub < (r_s[j] - r_s[i]):
            maxsub = r_s[j] - r_s[i]

print(maxsub)

### FIXED CODE ###

n = int(input())
r_s = [int(input()) for i in range(n)]

minv = r_s[0]
maxv = r_s[1] - r_s[0]
for i in range(1, n):
    maxv = max(maxv, r_s[i]-minv)
    minv = min(minv, r_s[i])

print(maxv)
### BUGGY CODE ###

from bisect import bisect_left, bisect_right

N, K = map(int, input().split())
As = sorted(map(int, input().split()))

def check(t):
    "if the number of the pairs (i, j) that satisfies Ai * Aj <= t is < K, return True"
    count = 0
    for i, A in enumerate(As):
        if A > 0:
            index = bisect_right(As, t//A, lo = i+1) - (i+1)
        elif A < 0:
            index = N - bisect_left(As, -(t//(-A)), lo = i+1)
        else:
            if t < 0:
                index = 0
            else:
                index = N - i - 1
        count += index
        if count > K:
            return False
    return (count < K)
        

l = - (10 ** 18 + 10)
r = 10 ** 18 + 10
while r - l > 1:
    mid = (l + r) // 2
    if check(mid):
        l = mid
    else:
        r = mid

print(r)

### FIXED CODE ###

from bisect import bisect_left, bisect_right

N, K = map(int, input().split())
As = sorted(map(int, input().split()))
        
l = - (10 ** 18 + 10)
r = 10 ** 18 + 10
while True:
    mid = (l + r) // 2
    count = 0
    for i, A in enumerate(As):
        if A > 0:
            count += bisect_right(As, mid//A, lo = i+1) - (i+1)
        elif A < 0:
            count += N - bisect_left(As, -((-mid)//A), lo = i+1)
        else:
            if mid >= 0:
                count += N - i - 1
    if count < K:
        l = mid
    else:
        r = mid
    if r - l == 1:
        break

print(r)
### BUGGY CODE ###

import sys
from collections import defaultdict
from collections import deque
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return list(map(int, sys.stdin.readline().split()))
def II(): return int(sys.stdin.readline())
def LS(): return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]

def main():
    n, k = LI()
    g = defaultdict(set)
    for i in range(n-1):
        a, b = LI()
        g[a].add(b)
        g[b].add(a)

    s = 1
    Q = deque([s])
    ans = k
    Qappend = Q.append
    searched = [0 for i in range(n+1)]
    searched[s] = 1
    while len(Q) != 0:
        v = Q.popleft()
        if v == s:
            cand = k - 1
        else:
            cand = k - 2
        for i in g[v]:
            if searched[i] == 1:
                continue
            if cand == 0:
                print(0)
                return
            searched[i] = 1
            ans *= cand % MOD
            cand -= 1
            Qappend(i)
    print(ans % MOD)






if __name__ == "__main__":
    main()

### 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 ###

a,b,k=map(int,input().split())
l=[i for i in range(1,b+1)]
l=l[a-1:]
l=l[:k]+l[-k:]
l=list(set(l))
l.sort()
for i in l:
    print(i)

### FIXED CODE ###

a,b,k=map(int,input().split())
l=[i for i in range(a,min(a+k,b+1))]
s=[i for i in range(max(a,b-k+1),b+1)]
l=l+s
l=list(set(l))
l.sort()
for i in l:
    print(i)
### BUGGY CODE ###

n  = int(input())
arr = [int(i) for i in input().split()]
arr.sort()

works= lambda a,b,c : (a<(b+c)) and (b<(a+c)) and (c<(b+a))

total = 0

for i in range(n):
    aI = arr[i]
    for j in range(i+1,n):
        aJ = arr[j]
        for k in range(j+1,n):
            if works(arr[k],aI,aJ):
                total+=1
            else:
                break

print(total)


### FIXED CODE ###

n  = int(input())
arr = [int(i) for i in input().split()]
arr.sort()

total = 0

for i in range(n-2):
    aI = arr[i]
    k = i + 2
    
    for j in range(i+1,n):
        mySum = aI+arr[j]

        while (k<n) and arr[k]<mySum:
            k+=1
            
        if k>j:
            total+= k-j-1

print(total)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
n,m=map(int,input().split())
a=[]
mod=1000000007
for _ in range(m):
    a.append(int(input()))
if 1 in a:
    ans=[1]+[0]+[0]*(n-1)
else:
    ans=[1]+[1]+[0]*(n-1)
for i in range(2,n+1):
    if i in a:
        ans[i]=0
    else:
        ans[i]=(ans[i-1]+ans[i-2])%mod
print(ans[n])

### FIXED CODE ###

# -*- coding: utf-8 -*-
n,m=map(int,input().split())
a=[]
mod=1000000007
for _ in range(m):
    a.append(int(input()))
a=set(a)
ans=[1]+[0]*(n)
for i in range(1,n+1):
    if i in a:
        ans[i]=0
    else:
        ans[i]=(ans[i-1]+ans[i-2])%mod
print(ans[n])