Harryxun/stf_run huggingface dataset:
MOD=1000000007
n,k=map(int,input().split())
a=[int(i) for i in input().split()]
pos=[]
neg=[]
nzero=0
for i in a:
    if i>0:
        pos.append(i)
    elif i<0:
        neg.append(-i)
    else:
        nzero+=1
if nzero+k>n:
    print(0)
elif nzero+k==n:
    if len(neg)%2:
        print(0)
    else:
        res=1
        for i in pos+neg:
            res*=i
            res%=MOD
        print(res)
elif len(pos)==0:
    res=1
    if k%2 and nzero>0:
        print(0)
    elif k%2:
        neg.sort()
        for i in range(k):
            res*=MOD-neg[i]
            res%=MOD
        print(res)
    else:
        neg.sort(reverse=True)
        for i in range(k):
            res*=MOD-neg[i]
            res%=MOD
        print(res)
elif len(neg)==0:
    res=1
    pos.sort(reverse=True)
    for i in range(k):
        res*=pos[i]
        res%=MOD
    print(res)
else:
    3/0


### FIXED CODE ###

MOD=1000000007
n,k=map(int,input().split())
a=[int(i) for i in input().split()]
pos=[]
neg=[]
nzero=0
for i in a:
    if i>0:
        pos.append(i)
    elif i<0:
        neg.append(-i)
    else:
        nzero+=1
if nzero+k>n:
    print(0)
elif nzero+k==n and len(pos)>0 and len(neg)>0:
    if nzero==0:
        res=1
        for i in pos+neg:
            res*=i
            res%=MOD
        if len(neg)%2:
            res*=-1
            res+=MOD
        print(res)
    elif len(neg)%2:
        print(0)
    else:
        res=1
        for i in pos+neg:
            res*=i
            res%=MOD
        print(res)
elif len(pos)==0:
    res=1
    if k%2 and nzero>0:
        print(0)
    elif k%2:
        neg.sort()
        for i in range(k):
            res*=MOD-neg[i]
            res%=MOD
        print(res)
    else:
        neg.sort(reverse=True)
        for i in range(k):
            res*=MOD-neg[i]
            res%=MOD
        print(res)
elif len(neg)==0:
    res=1
    pos.sort(reverse=True)
    for i in range(k):
        res*=pos[i]
        res%=MOD
    print(res)
else:
    pos.sort(reverse=True)
    neg.sort(reverse=True)
    ruip=[1 for i in range(len(pos)+1)]
    ruin=[1 for i in range(len(neg)+1)]
    for i in range(len(pos)):
        ruip[i+1]=ruip[i]*pos[i]
        ruip[i+1]%=MOD
    for i in range(len(neg)):
        ruin[i+1]=ruin[i]*neg[i]
        ruin[i+1]%=MOD
    np=0
    if len(pos)>=k:
        np=k
    elif (k-len(pos))%2:
        np=len(pos)-1
    else:
        np=len(pos)
    while np>=2 and (pos[np-1]*pos[np-2]<neg[k-np+1]*neg[k-np]):
        np-=2
        if len(neg)-1<k-np+1:
            break
    print((ruip[np]*ruin[k-np])%MOD)
h,w=map(int,input().split())
mass=[]
frame=[["."]*(w+2) for i in range(h+2)]
for i in range(h):
    mass.append(list(input()))
for i in range(h):
    for j in range(w):
        frame[i+1][j+1]=mass[i][j]
for i in range(1,h):
        for j in range(1,w):
            if frame[i][j]=="#" and frame[i][j]!=frame[i][j+1] and frame[i][j]!=frame[i+1][j] and frame[i][j]!=frame[i][j-1] and frame[i][j]!=frame[i-1][j]:
                    print("No")
                    exit()
print("Yes")	


### FIXED CODE ###

a,b=map(int,input().split())
if a>12 or b>31 :
    print("none")
else:
    if a>b:
        print(a-1)
    else:
        print(a)
n=int(input())
h=[int(i) for i in input().split()]
memo=[-1]*(n+1)
def flog(n):
    if n<=0:
        memo[0]=0
        return 0
    if n==1:
        memo[1]=abs(h[0]-h[1])
        return memo[n]
    if memo[n]!=-1:
        return memo[n]
    else:
        memo[n]=min(flog(n-1)+abs(h[n]-h[n-1]),flog(n-2)+abs(h[n]-h[n-2]))
        return memo[n]
print(flog(n-1))

### FIXED CODE ###

n=int(input())
h=[int(i) for i in input().split()]
dp=[0]*n
dp[1]=abs(h[0]-h[1])
for i in range(2,n):
    dp[i]=min(dp[i-1]+abs(h[i]-h[i-1]),dp[i-2]+abs(h[i]-h[i-2]))
print(dp[-1])
n = int(input())
a = list(map(int,input().split()))
b = []

for i in range(n):
  for j in range(n):
    if a[j] == i + 1:
      b.append(i+1)
      break

print(' '.join(b))

### FIXED CODE ###

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

for i in range(n):
      b[a[i] - 1] = str(i + 1)

print(' '.join(b))
S = input()
#複数の定義はまとめられる
cntA, cntB = 0, 0

for i, t in enumerate(S):
    if i%2 == 0:
        if t == '0': #標準入力Sはstr型だから0ではなく'0'のようにする
            cntA += 1
        else:
            cntB += 1
    else:
        if t == '1':
            cntA += 1
        else:
            cntB += 1
print (min(ci, c2)) 

### FIXED CODE ###

S = input()
#複数の定義はまとめられる
cntA, cntB = 0, 0

for i, t in enumerate(S):
    if i%2 == 0:
        if t == '0': #標準入力Sはstr型だから0ではなく'0'のようにする
            cntA += 1
        else:
            cntB += 1
    else:
        if t == '1':
            cntA += 1
        else:
            cntB += 1
print (min(cntA, cntB))
import math

A, B = map(int,input().split())

pricemax_A = math.floor((A+1)/0.08)
pricemin_A = math.floor(A/0.08)

pricemax_B = math.floor((B+1)/0.1)
pricemin_B = math.floor(B/0.1)

if pricemin_A >= pricemax_B or pricemax_A =< pricemin_B:
    print(-1)
elif pricemin_A >= pricemin_B:
    print(pricemin_A)
elif pricemin_A < pricemin_B:
    print(pricemin_B)

### FIXED CODE ###

import math

A, B = map(int,input().split())

pricemax_A = math.floor((A+1)/0.08)
pricemin_A = math.ceil(A/0.08)

pricemax_B = math.floor((B+1)/0.1)
pricemin_B = math.ceil(B/0.1)

if pricemin_A >= pricemin_B and pricemin_A < pricemax_B:
    print(pricemin_A)
elif pricemin_A <= pricemin_B and pricemax_A > pricemin_B:
    print(pricemin_B)
else:
    print(-1)
a, b = map(int, input().split())
if (a + b) % 2 == 0 :
  print((a + b) / 2)
else
  print("IMPOSSIBLE")


### FIXED CODE ###

a, b = map(int, input().split())
if (a + b) % 2 == 0 :
  print((a + b) // 2)
else :
  print("IMPOSSIBLE")
import string
alphabet = [chr(i) for i in range(97, 97+26)]
s = set(input())
result = set(alphabet) - s
result = sorted(list(result))
print(result[0])

### FIXED CODE ###

import string
alphabet = [chr(i) for i in range(97, 97+26)]
s = set(input())
result = set(alphabet) - s
result = sorted(list(result))
if len(result) == 0:
  print("None")
else:
  print(result[0])
a,b,c,d = int(input().split())
ans_list= []
ans_list.append(a*c)
ans_list.append(a*d)
ans_list.append(b*c)
ans_list.append(b*d)
print max(ans_list)


### FIXED CODE ###

a,b,c,d = input().split()
ans_list= []
ans_list.append(int(a)*int(c))
ans_list.append(int(a)*int(d))
ans_list.append(int(b)*int(c))
ans_list.append(int(b)*int(d))
print(max(ans_list))
from sys import stdin

def main():
    import numpy as np
    from scipy import linalg
    input = stdin.readline

    n = int(input())
    a = [[] for _ in range(n)]
    for i in range(n - 1):
        a[i] = [0] * i + [1, 1] + [0] * (n - i - 2)
    a[n - 1] = [1] + [0] * (n - 2) + [1]
    A = np.array(a)
    b = np.array(list(map(int, input().split())))
    LU = linalg.lu_factor(A)
    x = linalg.lu_solve(LU, b) * 2
    print(' '.join(map(str, map(int, x))))
main()

### FIXED CODE ###

from sys import stdin

def main():
    input = stdin.readline

    n = int(input())
    a = list(map(int, input().split()))
    ans = [0] * n
    for i in range(n):
        if i % 2 == 0:
            ans[0] += a[i]
        else:
            ans[0] -= a[i]
    for i in range(1, n):
        ans[i] = 2 * a[i - 1] - ans[i - 1]
    print(' '.join(map(str, ans)))
main()
import sys

dList = list()

for i,d in sys.stdin:
  if i <> 0: #1行目の行数情報はいらないので読み飛ばす
    dList.append(d)

print(len(set(dList)))

### FIXED CODE ###

n = int(input())

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

print(len(set(dList)))
a,b,c,d = input().split()
a,b,c,d = int(a),int(b),int(c),int(d)

import math

def div(x):
    if(a%x == 0):
        return (b//x-a//x)*(x-1)+(b%x)
    else:
        return (b//x-a//x)*(x-1)+(b%x)-(a%x-1)

ans = div(c)+div(d)-div(int(c*d/math.gcd(c,d)))
print(ans)

### FIXED CODE ###

a,b,c,d = input().split()
a,b,c,d = int(a),int(b),int(c),int(d)

from fractions import gcd

def div(x):
    if(a%x == 0):
        return (b//x-a//x)*(x-1)+(b%x)
    else:
        return (b//x-a//x)*(x-1)+(b%x)-(a%x-1)

ans = div(c)+div(d)-div(int(c*d//gcd(c,d)))
print(ans)
k = []
for i in range(4):
    k.append(int(input()))
print(min(k[0],k[1])+min(k[2]+k[3]))


### FIXED CODE ###

k = []
for i in range(4):
    k.append(int(input()))
a = min(k[0],k[1]) + min(k[2],k[3])
print(a)
def DFS(graph,start,mark_dict):
    mark_dict[start] = True
    for target in graph[start]:
      if target not in mark_dict:
        mark_dict[target] = True
        DFS(graph,target,mark_dict)

N,M,K = (int(x) for x in input().split())

friend = {}
for i in range(N):
  friend[i+1] = []
for i in range(M):
  a,b = (int(x) for x in input().split())
  friend[a].append(b)
  friend[b].append(a)

neighbor = [0]*N
for i in range(N):
  dic = {}
  DFS(friend,i+1,dic)
  neighbor[i] = len(dic)

for i in range(K):
  c,d = (int(x) for x in input().split())
  friend[c].append(d)
  friend[d].append(c)
  
for i in range(N):
  neighbor[i] -= len(friend[i+1]) + 1

print(' '.join(map(str, neighbor)))

### FIXED CODE ###

import sys

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

N,M,K = map(int,input().split())
friend =[0]*N
block = {}
for i in range(N):
  block[i] = []
uf = UnionFind(N)
for i in range(M):
  a,b = map(int,input().split())  
  a -= 1;b-=1
  friend[a]+=1
  friend[b]+=1
  uf.union(a,b)
  
for i in range(K):
  c,d = map(int,input().split())
  c -= 1
  d -= 1
  block[c].append(d)
  block[d].append(c)
res = [0]*N
for i in range(N):
  ans = uf.size(i)-1-friend[i]
  for u in block[i]:
    if uf.same(i,u):
      ans -= 1
      
  res[i] = ans
  
print(*res)
n = int(input())
a = 1
flag = False
for _ in range(n):
  d = int(input())
  a *= d
  if a > 10**18:
    flag = True
    break
if flag:
  print(-1)
else:
  print(a)

### FIXED CODE ###

n = int(input())
d = list(map(int, input().split()))
c_nega = 0
flag = False
for i in range(n):
  if d[i] == 0:
    flag = True
    break

if flag:
  print(0)
else:
  a = 1
  for i in range(n):
    a *= d[i]
    if a > 10**18:
      flag = True
      break
  if flag:
    print(-1)
  else:
    print(a)
s = input()
if s = "RSR":
  print(1)
else:
  print(s.count("R"))

### FIXED CODE ###

s = input()
if s == "RSR":
  print(1)
else:
  print(s.count("R"))
import numpy as np
n, k = map(int, input().split())
P = np.array(list(map(int, input().split())))
# P = list(map(int, input().split()))
P = (P + 1) * 0.5
maxv = 0
for i in range(n):
	maxv = max(maxv, sum(P[i:i+k]))
print(maxv)

### FIXED CODE ###

n, k = map(int, input().split())
P = list(map(int, input().split()))
maxv = tempsum = sum(P[:k])
for i in range(1, n-k+1):
	tempsum = tempsum - P[i-1] + P[i+k-1]
	maxv = max(maxv, tempsum)
print((maxv + k) * 0.5)
import sys
sys.setrecursionlimit(100000)

n, q = map(int, input().split())
dic = {}

for _ in range(n - 1):
    a, b = map(int, input().split())
    if not (a in dic):
        dic[a] = []
    dic[a].append(b)

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


def add_v(num, value):
    v_list[num - 1] = v_list[num - 1] + value
    if num in dic:
        for root in dic[num]:
            add_v(root, value)


for i in range(q):
    p, x = map(int, input().split())
    add_v(p, x)

print(*v_list)


### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)

n, q = map(int, input().split())
dic = {}

for _ in range(n - 1):
    a, b = map(int, input().split())
    if not (a in dic):
        dic[a] = []
    dic[a].append(b)

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

for _ in range(q):
    a, b = map(int, input().split())
    v_list[a-1] += b

key_list = list(dic.keys())
key_list.sort()

for a in key_list:
    for b in dic[a]:
        v_list[b-1] = v_list[a-1] + v_list[b-1]

print(*v_list)
H,W,A,B=map(int,input().split())

if W/A==H/B or W/A==0 or H/B==0:
    for h in range(H):
        S=[0]*W
        for i in range(A):
            S[W*h//H-i]=1
        print(S)
else:
    print(-1)



### FIXED CODE ###

# coding: utf-8
# Your code here!
H,W,A,B=map(int,input().split())

ans=[]
for b in range(B):
    ans.append(["1"]*A+["0"]*(W-A))
for b in range(H-B):
    ans.append(["0"]*A+["1"]*(W-A))

for item in ans:
    print("".join(item))
n = int(input())
print(round((n/3)**3,15)


### FIXED CODE ###

n = int(input())
print(round((n/3)**3,15))
n=int(input())
a=list(map(int,input().split()))
b=[]

for i in range(n):

    if n-i*2-1 > 0:
        b.append(a[n-i*2-1])
    else:
        k=abs(n-i*2)
        b.append(a[k])


print(*b)


### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
b=[]

if n%2==0:

    for i in range(n):

        if n-i*2-1 > 0:
            b.append(a[n-i*2-1])
        else:
            k=abs(n-i*2)
            b.append(a[k])

else:
    
    for i in range(n):

        if n-i*2-1 >= 0:
            b.append(a[n-i*2-1])
        else:
            k=abs(n-i*2-1)
            b.append(a[k-1])

print(*b)
A = int(input())
B = int(input())

print(6-a-b)



### FIXED CODE ###

a = int(input())
b = int(input())

print(6-a-b)
values = [int(input()) for i in range(int(input()))]
maxv = - 1000000
minv = values[0]

for value in enumerate(values):
    # maxv = max(maxv, value - minv)
    # minv = min(minv, value)
print(maxv)


### FIXED CODE ###

values = [int(input()) for _ in range(int(input()))]
maxv = values[1] - values[0]
minv = values[0]

for val in values[1:]:
    maxv = max(maxv, val - minv)
    minv = min(minv, val)         # 今までの最小値を保持(自分と自分を比較しない様に、最大値の評価後に計算)
print(maxv)
a = int(input())

print(int((a*(a**3-1)/(a-1))))

### FIXED CODE ###

a = int(input())

print(int(a+a**2+a**3))
import sys
a,b,c = map(lambda x: int(x), input().split())
k = int(input())

for _ in range(k):
    if b <= a:
        b = 2 * b
        continue
    if c <= b:
        c = 2 * c
        continue
    print('Yes')
    quit()
    
if (a < b) & (b < c):
    print('Yes')
    quit()
print('No')

### FIXED CODE ###

print(10 - int(input())//200)
n,m = map(int,input().split())
cor = set()
pens = {}
for i in range(m):
  p,s = input().split()
  if s=="AC":
    cor.add(p)
  else:
    if not p in cor:
      if p in pens:
        pens[p] += 1
      else:
        pens[p] = 1
pen = 0
for x in cor:
  if x in pens:  
    pen += pens(x)
print(str(len(cor))+" "+str(pen))

### FIXED CODE ###

n,m = map(int,input().split())
cor = set()
pens = {}
for i in range(m):
  p,s = input().split()
  if s=="AC":
    cor.add(p)
  else:
    if not p in cor:
      if p in pens:
        pens[p] += 1
      else:
        pens[p] = 1
pen = 0
for x in cor:
  if x in pens:  
    pen += pens[x]
print(str(len(cor))+" "+str(pen))
n = input()
x = list(map(int,input().split()))
count = 0
for i in range(1,n):
  if all(x[j]>x[i] for j in range(0,i-1)):
    count+=1
print(count)

### FIXED CODE ###

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

for i in range(1,n):
  if m >=x[i]:
    count+=1
    m = x[i]
  
print(count)
print('YES' if set(map(int, input().split())) == set(1, 9, 7, 4) else 'NO')


### FIXED CODE ###

print('YES' if set(list(map(int,
                            input().split()))) == set([1, 9, 7, 4]) else 'NO')
n=int(input())
if n==1:
  if int(input())==0:
    print(n)
  else:
    print(0)
  exit
a=list(map(int,input().split()))
m=10**9+7
x=[]
if n%2==1:
  x.append(0)
for i in range(n%2+1,n,2):
  x.append(i)
  x.append(i)
if sorted(a)==x:
  print((2**(n//2))%m)
else:
  print(0)

### FIXED CODE ###

n=int(input())
if n==1:
  if int(input())==0:
    print(n)
  else:
    print(0)
  exit()
a=list(map(int,input().split()))
m=10**9+7
x=[]
if n%2==1:
  x.append(0)
for i in range(n%2+1,n,2):
  x.append(i)
  x.append(i)
if sorted(a)==x:
  print((2**(n//2))%m)
else:
  print(0)
i = int(input())
for n in range(1, i):
	if (n ** .5).is_integer():
		num = n
print(num)

### FIXED CODE ###

import math
X = int(input())
n = (int(math.sqrt(X)))**2
for b in range(2, int(math.sqrt(X))+2):
    for p in range(1, 10):
        if (b**p > n) and (b**p <= X):
            n = b**p
print(n)
x, n = map(int, input().split())
if n == 0:
    print(x)
    exit()

p = np.array(list(map(int, input().split())))
for i in range(100):
    if not x-i in p:
        print(x-i)
        exit()
    elif not x+i in p:
        print(x+i)
        exit()

### FIXED CODE ###

import numpy as np

x, n = map(int, input().split())
if n == 0:
    print(x)
    exit()

p = np.array(list(map(int, input().split())))
for i in range(100):
    if not x-i in p:
        print(x-i)
        exit()
    elif not x+i in p:
        print(x+i)
        exit()
from heapq import heappush, heappop
from collections import deque
import itertools
from itertools import permutations
import sys
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall

import bisect
sys.setrecursionlimit(10**6)
def SI():
    return input().split()
def MI():
    return map(int,input().split())
def I():
    return int(input())
def LI():
    return [int(i) for i in input().split()]
YN=['Yes','No']
YNeos='YNeos'
GYN=['Yes','trumpet']
mo=10**9+7
imp='IMPOSSIBLE'

n,k=MI()
a=LI()
A=[0]
for i in a:
    A+=[A[-1]+i]
b=[]
for i in range(n+1):
    for j in range(i+1,n+1):
        b+=[A[j]-A[i]]
        
c=sorted(b)[-k:]
ans=0
i=0
i2=1
while i2<c[-1]*2:
    ans+=i2 if sum([j>>i&1 for j in c])==k else 0
    #print(i2,sum([j>>i&1 for j in c]))
    i2*=2
    i+=1
    
print(ans)


### FIXED CODE ###

from heapq import heappush, heappop
from collections import deque
import itertools
from itertools import permutations
import sys

import bisect
sys.setrecursionlimit(10**6)
def SI():
    return input().split()
def MI():
    return map(int,input().split())
def I():
    return int(input())
def LI():
    return [int(i) for i in input().split()]
YN=['Yes','No']
YNeos='YNeos'
GYN=['Yes','trumpet']
mo=10**9+7
imp='IMPOSSIBLE'

n,k=MI()
a=LI()
A=[0]
for i in a:
    A+=[A[-1]+i]
b=[]
for i in range(n+1):
    for j in range(i+1,n+1):
        b+=[A[j]-A[i]]
        
c=sorted(b)#[-k:]
ans=0
i=0
i2=2**40
while i2>0:
#    print(i2,sum([(j&(ans+i2))==(ans+i2) for j in c]))
    ans+=i2 if sum([(j&(ans+i2))==(ans+i2) for j in c])>=k else 0
    i2//=2
    i+=1
    
print(ans)#,A,c)
#print()
import heapq
def dijkstra_heap(s,g,edge):
    #始点sから各頂点への最短距離
    d = [10**20] * (n+2)
    used = [True] * (n+2) #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    sx,sy,sr=edge[s][0],edge[s][1],edge[s][2]
    for i in range(n+2):
        x,y,r=edge[i][0],edge[i][1],edge[i][2]
        dist=((x-sx)**2+(y-sy)**2)**(1/2)
        heapq.heappush(edgelist,int(max(dist-r-sr,0)*(10**9))*10000+i)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        dis=(minedge//(10**4))/10**9
        v = int(minedge-dis*10**13)
        if not used[v]:
            continue
        d[v] = dis
        used[v] = False
        bx,by,br=edge[v][0],edge[v][1],edge[v][2]
        for i in range(n+2):
            x,y,r=edge[i][0],edge[i][1],edge[i][2]
            dist=((x-bx)**2+(y-by)**2)**(1/2)
            if used[i]:
                heapq.heappush(edgelist,int((max(dist-r-br,0)+d[v])*(10**9))*10000+i)
        if not used[g]:
            break
    return d[g]

sx,sy,gx,gy = map(int,input().split()) #n:頂点数　w:辺の数
n=int(input())
edge=[[sx,sy,0],[gx,gy,0]]
for i in range(2,n+2):
    x,y,r=map(int,input().split())
    edge.append([x,y,r])
print(dijkstra_heap(0,1,edge))

### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline

    import heapq
    def dijkstra_heap(s,g,edge):
        #始点sから各頂点への最短距離
        d = [10**20] * (n+2)
        used = [True] * (n+2) #True:未確定
        d[s] = 0
        used[s] = False
        edgelist = []
        sx,sy,sr=edge[s][0],edge[s][1],edge[s][2]
        for i in range(n+2):
            x,y,r=edge[i][0],edge[i][1],edge[i][2]
            dist=((x-sx)**2+(y-sy)**2)**(1/2)
            heapq.heappush(edgelist,(max(dist-r-sr,0),i))
        while len(edgelist):
            minedge = heapq.heappop(edgelist)
            #まだ使われてない頂点の中から最小の距離のものを探す
            v = minedge[1]
            if not used[v]:
                continue
            d[v] = minedge[0]
            used[v] = False
            bx,by,br=edge[v][0],edge[v][1],edge[v][2]
            for i in range(n+2):
                x,y,r=edge[i][0],edge[i][1],edge[i][2]
                dist=((x-bx)**2+(y-by)**2)**(1/2)
                if used[i]:
                    heapq.heappush(edgelist,(max(dist-r-br,0)+d[v],i))
            if not used[g]:
                break
        return d[g]

    sx,sy,gx,gy = map(int,input().split()) #n:頂点数　w:辺の数
    n=int(input())
    edge=[(sx,sy,0),(gx,gy,0)]
    for i in range(2,n+2):
        x,y,r=map(int,input().split())
        edge.append((x,y,r))
    print(dijkstra_heap(0,1,edge))

if __name__ == '__main__':
    main()
# -*- coding: utf-8 -*-
# モジュールのインポート
import math
import numpy as np

# 標準入力の取得
A, B, N = list(map(int, input().split()))


def func(x: np.ndarray) -> np.ndarray:
    return np.floor(A*x/B) - A*np.floor(x/B)


# 求解処理
x = np.arange(min(N, B-1), N+1, B, dtype="float32")
x = func(x)

# 結果出力
print(int(np.max(x)))


### FIXED CODE ###

# -*- coding: utf-8 -*-
# モジュールのインポート
import math

# 標準入力の取得
A, B, N = list(map(int, input().split()))


def f(x: int) -> int:
    return math.floor(A*x/B) - A*math.floor(x/B)


# 求解処理
result = f(min(B-1, N))

# 結果出力
print(result)
from collections import deque
import sys
input=sys.stdin.readline
h,w=map(int,input().split())
d=deque()
b=[]
for i in range(h):
  s=input()
  for j in range(w):
    if s[j]=="#":d.append([i,j])
  b.append(list(s))
count=0
while len(d)!=0:
  for i in range(len(d)):
    x=d.popleft()
    if x[0]<h-1:
      if b[x[0]+1][x[1]]==".":b[x[0]+1][x[1]]=count;d.append([x[0]+1,x[1]])
    if 0<x[0]
      if b[x[0]-1][x[1]]==".":b[x[0]-1][x[1]]=count;d.append([x[0]-1,x[1]])
    if x[1]<w-1
      if b[x[0]][x[1]+1]==".":b[x[0]][x[1]+1]=count;d.append([x[0],x[1]+1])
    if 0<x[1]
      if b[x[0]][x[1]-1]==".":b[x[0]][x[1]-1]=count;d.append([x[0],x[1]-1])
  count+=1
print(count-1) 

### FIXED CODE ###

from collections import deque
import sys
input=sys.stdin.readline
h,w=map(int,input().split())
d=deque()
dc=0
b=[]
for i in range(h):
  t=[]
  s=input()
  for j in range(w):
    if s[j]=="#":d.append((i,j));dc+=1;t.append(1)
    else:t.append(0)
  b.append(t)
count=0
while dc!=0:
  ld=dc
  dc=0
  for i in range(ld):
    x=d.popleft()
    if x[0]<h-1:
      if b[x[0]+1][x[1]]==0:b[x[0]+1][x[1]]=1;d.append((x[0]+1,x[1]));dc+=1
    if 0<x[0]:
      if b[x[0]-1][x[1]]==0:b[x[0]-1][x[1]]=1;d.append((x[0]-1,x[1]));dc+=1
    if x[1]<w-1:
      if b[x[0]][x[1]+1]==0:b[x[0]][x[1]+1]=1;d.append((x[0],x[1]+1));dc+=1
    if 0<x[1]:
      if b[x[0]][x[1]-1]==0:b[x[0]][x[1]-1]=1;d.append((x[0],x[1]-1));dc+=1
  count+=1
print(count-1)
S= input()
m= int(S[5:7])
if S>4:
  print('TBD')
else:
  print('Heisei')

### FIXED CODE ###

S = input()
a = int(S[5:7])
if a >4:
    print("TBD")
else:
    print("Heisei")