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

N, K = map(int, input().split()) # 横に2個
L = [list(map(int, input().split())) for _ in range(N-1)]

mod = 10**9+7

neardic = {}
for p in range(1, N+1):
    near = []
    for l in L:
        if p in l:
            other = set(l) - {p}
            near.append(list(other)[0])
    neardic[p] = set(near)

def color(p=1, state=[1], prob=K, checked=set()):
    nears = neardic[p]
    checked.add(p)
    # bottle neck
    unchecked_nears = nears - checked
    A = len(unchecked_nears)
    if A == 0:
        state.pop()
        return prob
    nextprobmax = K-1 if len(state) == 1 else K-2
    for i, near in enumerate(unchecked_nears):
        prob = prob * (nextprobmax - i) % mod
        state.append(near)
        prob = color(near, state, prob, checked)
    return prob

print(color())




### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

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

checked = [False]*N
C = [None]*N
checked[0] = True

def dfs(p, c1, c2, depth):
    C[p] = c1 + c2
    d = 0
    for np in graph[p]:
        if not checked[np]:
            checked[np] = True
            d += 1
            g = 1 if depth > 0 else 0
            dfs(np, d, g, depth+1)
        

dfs(0, 0, 0, 0)
#print(C)

mod = 10**9+7
ans = 1
for n in range(N):
    ans = ans * (K-C[n]) % mod

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

n=int(input())
arr=list(map(int,input().split()))
ans=1
def solve(arr,ans):
    for i in arr:
        ans*=i
    if(ans>10**18):
        return(-1)
    return(ans)
print(solve(arr,ans))


### FIXED CODE ###

n=int(input())
arr=list(map(int,input().split()))
ans=1
arr=sorted(arr)
def solve(arr,ans):
    for i in arr:
        ans*=i
        if(ans>10**18):
            return(-1)
        if(ans==0):
            return(0)
    if(ans>10**18):
        return(-1)
    return(ans)
print(solve(arr,ans))
### BUGGY CODE ###

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

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

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


Swap=[None]*M
for i in range(M):
    Swap[i]=sorted(map(int,input().split()))
 
Swap.sort(key=lambda x:x[0])

judge=1
while judge==1:
    judge=0
    for i in range(M):
        if (Group[Swap[i][1]],Group[Swap[i][0]])!=(min(Group[Swap[i][0]], Group[Swap[i][1]]),min(Group[Swap[i][0]], Group[Swap[i][1]])):
            Group[Swap[i][1]],Group[Swap[i][0]]=min(Group[Swap[i][0]], Group[Swap[i][1]]),min(Group[Swap[i][0]], Group[Swap[i][1]])
            judge=1

    for i in range(M-1,-1,-1):
        if (Group[Swap[i][1]],Group[Swap[i][0]])!=(min(Group[Swap[i][0]], Group[Swap[i][1]]),min(Group[Swap[i][0]], Group[Swap[i][1]])):
            Group[Swap[i][1]],Group[Swap[i][0]]=min(Group[Swap[i][0]], Group[Swap[i][1]]),min(Group[Swap[i][0]], Group[Swap[i][1]])
            judge=1


count=0

for i in range(N):
    if Group[P[i]]==Group[i+1]:
        count+=1


print(count)


### FIXED CODE ###

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

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


Swap=[None]*M
for i in range(M):
    Swap[i]=sorted(map(int,input().split()))

def find(x):
    while Group[x] != x:
        x=Group[x]
    return x

for i in range(M):
    if find(Swap[i][1]) != find(Swap[i][0]):
        Group[find(Swap[i][1])]=min(find(Swap[i][1]),find(Swap[i][0]))
        Group[find(Swap[i][0])]=min(find(Swap[i][1]),find(Swap[i][0]))
        Group[Swap[i][1]]=min(find(Swap[i][1]),find(Swap[i][0]))
        Group[Swap[i][1]]=min(find(Swap[i][1]),find(Swap[i][0]))

count=0

for i in range(N):
    if find(P[i])==find(i+1):
        count+=1


print(count)
### BUGGY CODE ###

Q = int(input())
a = []
for i in range(Q):
    a.append(list(map(int, input().split())))
number = []
prime_number = []
for i in range(1, 100000):
    number.append(i+1)
while number != []:
    prime_number.append(min(number))
    number = [x for x in number if x % min(number) != 0]
for i in range(Q):
    like_2017 = []
    for j in range(a[i][0], a[i][1] + 1, 2):        
        if (j in prime_number) and (int((j + 1) / 2) in prime_number):
            like_2017.append(j)
    print(len(like_2017))

### FIXED CODE ###

def prime(n):
    p = []
    flag = [True] * (n - 1)
    for i in range(n - 1):
        if flag[i] == True:
            p.append(i + 2)
            num = i
            while num <= n - 2:
                flag[num] = False
                num += i + 2
    return set(p)

p1 = prime(10 ** 5)
p2 = [0]
for i in range(10 ** 5):
    if i % 2 == 1:
        p2.append(p2[-1])
        continue
    else:
        if i + 1 in p1 and (i + 2) // 2 in p1:
            p2.append(p2[-1] + 1)
        else:
            p2.append(p2[-1])
q = int(input())
for i in range(q):
    l, r = map(int, input().split())
    print(p2[r] - p2[l -1])
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from collections import Counter 
from collections import defaultdict 
def main():
    s = input() 
    n = len(s)
    T = [0]
    dd = defaultdict(int) 
    dd[0] += 1
    for i in range(1, n+1):
        T.append((int(s[-i])*10**(i-1)%2019+T[i-1]%2019)%2019)
        dd[(int(s[-i])*10**(i-1)+T[i-1])%2019] += 1
    ans = 0
    for i in dd.values():
        ans += i*(i-1)//2
    print(ans)
if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from collections import Counter 
from collections import defaultdict 

def main():
    s = input() 
    n = len(s)
    T = [0]
    P = 2019
    dd = defaultdict(int) 
    dd[0] += 1
    for i in range(1, n+1):
        x = (int(s[-i])*pow(10, i-1, P) + T[i-1])%P
        T.append(x)
        dd[x] += 1
    ans = 0
    for i in dd.values():
        ans += i*(i-1)//2
    print(ans)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

N = input()
R = [int(raw_input()) for _ in xrange(N)]
ans = float('-inf')
for i in xrange(N):
    for j in xrange(i+1, N):
        ans = max(ans, R[j]-R[i])
print ans

### FIXED CODE ###

N = input()
R = [int(raw_input()) for _ in xrange(N)]
S = [0 for i in xrange(N)]
S[N-1] = R[N-1]
for i in xrange(N-2, -1, -1):
    S[i] = max(R[i], S[i+1])
ans = float('-inf')
for i in xrange(N-1):
    ans = max(ans, S[i+1]-R[i])
print ans
### BUGGY CODE ###

from collections import deque
def main():
    S = deque([s for s in input()])
    Q = int(input())
    for i in range(Q):
        query = input().split()
        t = int(query[0])
        if t == 1:
            S.reverse()
        else:
            f = int(query[1])
            c = query[2]
            if f == 1:
                S.appendleft(c)
            else:
                S.append(c)
    print(''.join(S))

if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import deque
def main():
    S = deque([s for s in input()])
    Q = int(input())
    order = True
    for i in range(Q):
        query = input().split()
        t = int(query[0])
        if t == 1:
            order = not order
        else:
            f = int(query[1])
            c = query[2]
            left = True
            if f == 1:
                if order:
                    left = True
                else:
                    left = False
            else:
                if order:
                    left = False
                else:
                    left = True
            if left:
                S.appendleft(c)
            else:
                S.append(c)
    if not order:
        S.reverse()
    print(''.join(S))

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

# coding: utf-8
def main():
    N,Q = map(int, input().split())
    s = input()
    Golem_list = [1] * N
    ans = N
    for i in range(Q):
        # 呪文
        t,d = input().split()
        for si in range(len(s)):
            if s[si] == t:#マス目の指定
                ans = move(Golem_list,d,ans,N,si)
    print(ans)


def move(Golem_list,d,ans,N,si):
    if d == 'L':
        if si == 0:
            ans -= Golem_list[0]
            Golem_list[0] = 0
        else :
            Golem_list[si-1] += Golem_list[si]
            Golem_list[si] = 0

    elif d == 'R':
        if si == N-1:
            ans -= Golem_list[N-1]
            Golem_list[N-1] = 0
        else :
            Golem_list[si+1] += Golem_list[si]
            Golem_list[si] = 0
    # print(Golem_list)
    # print("#"+str(ans))
    return ans

if __name__ == "__main__":
    main()

### FIXED CODE ###

# coding: utf-8
def main():
    N,Q = map(int, input().split())
    s = input()
    ans = N
    command = []

    # print(char_list)

    for i in range(Q):
        t,d = input().split()
        command.append([t,d])

    r = binary_serch_R(command,s,N)
    #print(r)
    l = binary_serch_L(command,s,N)
    #print(l)
    ans = ans - (N-r) - (l+1)
    if ans < 0:
        ans = 0
    print(ans)

def simulation_R(command,s,now,N):
    for pair in command:
        if pair[0] == s[now]:
            if pair[1] == 'L':
                now -= 1
            elif pair[1] == 'R':
                now += 1
        if now < 0:
            return False
        elif now >= N:
            return True
    return False

def simulation_L(command,s,now,N):
    for pair in command:
        if pair[0] == s[now]:
            if pair[1] == 'L':
                now -= 1
            elif pair[1] == 'R':
                now += 1
        if now < 0:
            return True
        elif now >= N:
            return False
    return False


def binary_serch_R(command,s,N):
    left = 0
    right = N-1
    if simulation_R(command,s,left,N) :
        return -1
    if simulation_R(command,s,right,N) == False:
        return N

    while abs(right - left) > 1:
        mid = int((left+right)/2)
        # print(mid)
        if simulation_R(command,s,mid,N) :
            right = mid
        else :
            left = mid 
    return right

def binary_serch_L(command,s,N):
    left = 0
    right = N-1
    if simulation_L(command,s,left,N) == False :
        return -1
    if simulation_L(command,s,right,N):
        return N
        
    while abs(right-left) > 1:
        mid = int((left+right)/2)
        if simulation_L(command,s,mid,N) :
            left = mid
        else :
            right = mid 
    return left

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

import sys
#from scipy.special import comb
#from scipy.misc import comb

from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

sys.setrecursionlimit(100000)
nCr = {}
def cmb(n, r):
    if r == 0 or r == n: return 1
    if r == 1: return n
    if (n,r) in nCr: return nCr[(n,r)]
    nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
    return nCr[(n,r)]


def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

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

A = [0]*M

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

A.append(N+1)

def step_comb(L):
    c = 0
    if L==1 or L == 0:
        c = 1
    else:
        for i in range(L//2 +1):
            j = L - 2*i
            #c += comb(j+i, i, exact=True)
            c += cmb(j+i, i)
    return c

total_comb = 1
NOW = 0
for a in A:
    if NOW == a:
        print(0)
        sys.exit()
    L = a-1-NOW
    total_comb *= step_comb(L)
    NOW = a + 1
    
print(total_comb % 1000000007 )


### FIXED CODE ###

import sys
sys.setrecursionlimit(100000000)

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

if M == 0:
    A = []
else:
    A = [0]*M
    for i in range(M):
        A[i] = int(input())

A.append(N+1)

# DP version
DP = [0]*(N+1)
DP[0] = 1
# １段の階段を登るやり方の数
DP[1] = 1
# 2段の階段を登るやり方の数
#DP[2] = 2

for i in range(2,N+1):
    DP[i] = DP[i-1] + DP[i-2]

def step_comb(L):
    if DP[L]>0:
        return DP[L]
    DP[L] = step_comb(L-1) + step_comb(L-2)
    return DP[L]
    
total_comb = 1
NOW = 0
for a in A:
    if NOW == a:
        print(0)
        sys.exit()
    L = a-1-NOW
    total_comb *= step_comb(L)
    NOW = a + 1
    if NOW == N:
        break
    
print(total_comb % 1000000007 )
### BUGGY CODE ###

N, M = map(int, input().split())
t = 100 * N + 1800 * M
total = 0
i = 1
p = 1 / 2**M
while True:
    d = i * (1-p)**(i-1) * p * t
    total += d
    if d < 0.001:
        break
print(total)

### FIXED CODE ###

N, M = map(int, input().split(" "))
t = 100 * N + 1800 * M
print(t * (2**M))
### BUGGY CODE ###

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

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

Bs = []
Cs = []
for i in range(M):
	inputs = list(map(int,input().split()))
	Bs.append(inputs[0])
	Cs.append(inputs[1])

for j in range(1, M + 1):
	for n in range(Bs[j - 1]):
		minIndex = As.index(min(As))
		if As[minIndex] < Cs[j - 1]:
			As[minIndex] = Cs[j - 1]
print(sum(As))


### FIXED CODE ###

import numpy as np

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

As = sorted(list(map(int,input().split())))
BCs = []

for i in range(M):
	inputs = list(map(int,input().split()))
	BCs.append(inputs)
BCs = sorted(BCs, reverse = True, key=lambda x: x[1])

index = 0
for bc in BCs:
	b = bc[0]
	c = bc[1]

	for n in range(b):
		try:
			if As[index] < c:
				As[index] = c
				index += 1
			else:
				break
		except:
			break
print(sum(As))
### BUGGY CODE ###

N,M = map(int,input().split())
a = [0]*M
for i in range(M):
    a[i] = int(input())

step = [0]*(N+1)
step[0] = 1
if 1 in a:
    step[1] = 0
else:
    step[1] = 1

for i in range(2,N+1):
    if i in a:
        step[i] = 0
    else:
        step[i] = (step[i-1] + step[i-2])%(10**9+7)

print(step[N])

#再起関数供養
def count_step(a,n):
    if n == 0:
        return 1
    if n == 1 and 1 not in a:
        return 1
    if n in a:
        return 0
    return (count_step(a,n-1)+count_step(a,n-2))%(10**9+7)

### FIXED CODE ###

N,M = map(int,input().split())
a = [0]*M
for i in range(M):
    a[i] = int(input())

step = [0]*(N+1)
step[0] = 1

for i in range(M):
    step[a[i]] = -1

if 1 in a:
    step[1] = 0
else:
    step[1] = 1

for i in range(2,N+1):
    if step[i] == -1:
        step[i] = 0
    else:
        step[i] = (step[i-1] + step[i-2])%(10**9+7)

print(step[N])

#再起関数供養
def count_step(a,n):
    if n == 0:
        return 1
    if n == 1 and 1 not in a:
        return 1
    if n in a:
        return 0
    return (count_step(a,n-1)+count_step(a,n-2))%(10**9+7)
### BUGGY CODE ###

#D in [S_i-X_i,T_i-X_i) → Xiで止まる
import sys
input = sys.stdin.readline
from heapq import heappush,heappop

N,Q = map(int,input().split())
q = []

STX = [[int(x) for x in input().split()] for _ in range(N)]
for s,t,x in STX:
  heappush(q,(s-x,1,x)) # xで死ぬ
  heappush(q,(t-x,0,x)) # xで死ななくなる

for i in range(Q):
  d = int(input())
  heappush(q,(d,2,i))
answer = [-1]*Q

se = []
remove_task = []

while q:
  a,c,b = heappop(q)
  if not c:
    heappush(remove_task,b)
  elif c&1:
    heappush(se,b)
  else:
    while remove_task and (se[0] == remove_task[0]):
      heappop(se)
      heappop(remove_task)
    if se:
      answer[b] = se[0]
  #print(a,c,b,se,remove_task)
print('\n'.join(map(str,answer)))


### FIXED CODE ###

#D in [S_i-X_i,T_i-X_i) → Xiで止まる
import sys
input = sys.stdin.readline

N,Q = map(int,input().split())
q = []

STX = [[int(x) for x in input().split()] for _ in range(N)]
for s,t,x in STX:
  q.append((s-x,1,x)) # xで死ぬ
  q.append((t-x,0,x)) # xで死ななくなる

for i in range(Q):
  d = int(input())
  q.append((d,2,i))
answer = [-1]*Q

se = set() # 引っかかってる場所

q.sort()

min_se = 10**18
flag = False # min_seが正しい

for a,c,b in q:
  if not c:
    se.remove(b)
    if min_se == b:
      flag = False
  elif c&1:
    se.add(b)
    if b < min_se:
      min_se = b
      flag = True
  else:
    if se:
      if not flag:
        min_se = min(se)
        flag = True
      answer[b] = min_se

print('\n'.join(map(str,answer)))
### BUGGY CODE ###


def parse():
  H, W = map(int, input().split(" "))
  grid = []
  for y in range(H):
    grid.append(list(input()))
  return H, W, grid

def print_grid(grid):
  H = len(grid)
  print("grid:")
  for line in grid:
    for c in line:
      print(c, end="")
    print("")

def main():
  H, W, grid = parse()
  # print(H, W)
  # print_grid(grid)

  visited = [[W * H if grid[y][x] == "." else 0 for x in range(W)] for y in range(H)]
  # for y in range(H):
  #   visited.append([])
  #   for x in range(W):
  #     if grid[y][x] == ".":
  #       visited[y].append(H * W)
  #     else:
  #       visited[y].append(0)
    # print(visited[y])
  
  for y in range(H):  # ↓
    for x in range(1, W):  # →
      visited[y][x] = min(visited[y][x - 1] + 1, visited[y][x])
    for x in range(W - 2, -1, -1):  # ←
      visited[y][x] = min(visited[y][x], visited[y][x + 1] + 1)

  # for y in range(H):  # ↓
  #   for x in range(1, W):  # →
  #     visited[y][x] = min(visited[y][x - 1] + 1, visited[y][x])
  # for y in range(H):  # ↓
  #   for x in range(W - 2, -1, -1):  # ←
  #     visited[y][x] = min(visited[y][x], visited[y][x + 1] + 1)
  
  for x in range(W):  # →
    for y in range(1, H):  # ↓
      visited[y][x] = min(visited[y - 1][x] + 1, visited[y][x])
    for y in range(H - 2, -1, -1):  # ↑
      visited[y][x] = min(visited[y][x], visited[y + 1][x] + 1)

  # for x in range(W):  # →
  #   for y in range(1, H):  # ↓
  #     visited[y][x] = min(visited[y - 1][x] + 1, visited[y][x])
  # for x in range(W):  # →
  #   for y in range(H - 2, -1, -1):  # ↑
  #     visited[y][x] = min(visited[y][x], visited[y + 1][x] + 1)
  
  max_len = 0
  for y in range(H):
    max_len = max_len if max_len > max(visited[y]) else max(visited[y])
  print(max_len)

if __name__ == "__main__":
  main()

### FIXED CODE ###


import numpy as np

def parse():
  H, W = map(int, input().split(" "))
  grid = [list(input()) for y in range(H)]
  return H, W, grid

def print_grid(grid):
  H = len(grid)
  print("grid:")
  for line in grid:
    for c in line:
      print(c, end="")
    print("")

def main():
  H, W, grid = parse()
  # print(H, W)
  # print_grid(grid)

  # visited = [[W * H if grid[y][x] == "." else 0 for x in range(W)] for y in range(H)]
  visited = np.zeros((H, W), int)
  for y in range(H):
    # visited.append([])
    for x in range(W):
      if grid[y][x] == ".":
        visited[y][x] = H * W

  for y in range(1, H):  # ↓
    # 要素ごとの処理
    # print(visited)
    visited[y][:] = np.minimum(visited[y][:], visited[y - 1][:] + 1)
    # print(visited)
    # input()
    # print(visited[y])
    # exit(0)

  for y in range(H - 2, -1, -1):
    visited[y, :] = np.minimum(visited[y, :], visited[y + 1][:] + 1)

  for x in range(1, W):
    visited[:, x] = np.minimum(visited[:, x], visited[:, x - 1] + 1)

  for x in range(W - 2, -1, -1):
    visited[:, x] = np.minimum(visited[:, x], visited[:, x + 1] + 1)

  # print(visited)
  # exit(0)

  # max_len = 0
  # for y in range(H):
  #   max_val = max(visited[y])
  #   max_len = max_len if max_len > max_val else max_val
  # print(max_len)
  print(np.max(visited))

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

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

count = 0
for j in range(n):
    print(li.count(j+1))

### FIXED CODE ###

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

ans = [0] * n
for i in li:
    j = i - 1
    ans[j]  = ans[j] + 1
    
for i in ans:
    print(i)
### BUGGY CODE ###

N=int(input())
listA=list(map(int,input().split()))
ans=0
L=[]
R=[]
for i in range(N):
  L+=[i+listA[i]]
  R+=[i-listA[i]]
setL=set(L)  
setR=set(R)
for i in range(N):
  if i in setL and i in setR:
    ans+=L.count(i)*R.count(i)
print(ans)    

### FIXED CODE ###

N=int(input())
listA=list(map(int,input().split()))
ans=0
L=[]
R=[]
L1=[0]*N
R1=[0]*N
for i in range(N):
  L+=[i+listA[i]]
  R+=[i-listA[i]]
  try:
    L1[i+1+listA[i]]+=1
  except:
    pass
  try:
    if i-listA[i]>0:
      R1[i+1-listA[i]]+=1
  except:
    pass
for i in range(N):
  ans+=L1[i]*R1[i]
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline


n = int(input())
up = 10**18
l = list(map(int, input().split()))

if 0 in l:
    print(0)
else:
    ans = 1
    for i in l:
        ans *= i
    
    if ans > up:
        print(-1)
    else:
        print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline


n = int(input())
up = 10**18
l = list(map(int, input().split()))

if 0 in l:
    print(0)
else:
    ans = 1
    for i in l:
        ans *= i
        if ans > up:
            print(-1)
            break
    else:
        print(ans)
### BUGGY CODE ###

def main():
    A, B, N = (int(x) for x in input().split())
    mini = 0
    if N >= B:
        for x in range(B-1, N+1, B):
            k = x / B
            ans = int(A*k) - int(k)
            if ans > mini:
                mini = ans
    else:
        for x in range(1, N+1):
            k = x / B
            ans = int(A * k)
            if ans > mini:
                mini = ans
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    A, B, N = (int(x) for x in input().split())
    mini = 0
    if N >= B:
        ans = int(A*(B-1)/B)
    else:
        ans = int(A*(N)/B)
    print(ans)


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

import math
a,b,n=map(int,input().split())
max=-2
if n<b:
    max=math.floor(a*n/b)
else:
    #b<=n
    max=math.floor(a*(b-1)/b)
    for i in range(b,n+1):
        s2=math.floor(a*((1/b)-i//b))
        if max<s2:
            max=s2

print(max)

### FIXED CODE ###

import math
a,b,n=map(int,input().split())
max=-2
if n<b:
    max=math.floor(a*n/b)
else:
    #b<=n
    max=math.floor(a*(b-1)/b)
    

print(max)
### BUGGY CODE ###

class Fenwick:
    def __init__(self, size):
        self.arr = [0]*size
    
    def update(self, i, val):
        while i < len(self.arr): self.arr[i] += val; i |= i+1
    
    def getsum(self, i):
        res = 0
        while i >= 0: res+= self.arr[i]; i = (i&(i+1))-1
        return res

def paramin(F, l, r):
    while l <= r:
        mid = (l+r)//2
        if F(mid): ans, r = mid, mid-1
        else: l = mid+1
    return ans

from itertools import accumulate
def medleq(i):
    x = vals[i]
    M = [(y<=x)*2-1 for y in L]
    MA = list(accumulate(M))
    cnt = sum(y>0 for y in MA)
    F = Fenwick(2*n+3)
    for y in MA:
        c = y+n+1
        cnt+= F.getsum(c-1)
        F.update(c, 1)
    return cnt >= target

n = int(input())
L = list(map(int,input().split()))
tot = n + n*(n-1)//2
target = tot//2 + 1
vals = sorted(set(L))
print(vals[paramin(medleq, 0, len(vals)-1)])

### FIXED CODE ###

class Fenwick:
    def __init__(self, size):
        self.arr = [0]*size
    
    def update(self, i, val):
        while i < len(self.arr): self.arr[i] += val; i |= i+1
    
    def getsum(self, i):
        res = 0
        while i >= 0: res+= self.arr[i]; i = (i&(i+1))-1
        return res

def paramin(F, l, r):
    while l <= r:
        mid = (l+r)//2
        if F(mid): ans, r = mid, mid-1
        else: l = mid+1
    return ans

from itertools import accumulate
def medleq(x):
    M = [(y<=x)*2-1 for y in L]
    MA = list(accumulate(M))
    cnt = sum(y>0 for y in MA)
    F = Fenwick(2*n+3)
    for y in MA:
        c = y+n+1
        cnt+= F.getsum(c-1)
        F.update(c, 1)
    return cnt >= target

n = int(input())
L = list(map(int,input().split()))
tot = n + n*(n-1)//2
target = tot//2 + 1
print(paramin(medleq, min(L), max(L)))