Harryxun/stf_run huggingface dataset:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf,comb
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

h, w, k = MAP()
s = []
p = []
q = []
for i in range(h):
    s.append(input())
    if s[i].count('#') > 0:
        p.append(i)
    else:
        q.append(i)

a = [[0]*w for i in range(h)]
num = 0
if p:
    for i in p:
        num += 1
        k = 0
        while s[i][k] == '.':
            a[i][k] = num
            k += 1
        a[i][k] = num
        k += 1
        if k < w:
            for j in range(k, w):
                if s[i][j] == '#':
                    num += 1
                a[i][j] = num

if q:
    for i in q:
        k = i
        while k < h and a[k][j] == 0:
            k += 1
        if k >= h:
            k = i
            while k < h and a[k][j] == 0:
                k -= 1
        for j in range(w):
            a[i][j] = a[k][j]
for i in range(h):
    print(*a[i][:])

### FIXED CODE ###

from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf,comb
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

h, w, k = MAP()
s = []
p = []
q = []
for i in range(h):
    s.append(input())
    if s[i].count('#') > 0:
        p.append(i)
    else:
        q.append(i)

a = [[0]*w for i in range(h)]
num = 0
if p:
    for i in p:
        num += 1
        m = 0
        while s[i][m] == '.':
            a[i][m] = num
            m += 1
        if m < w:
            if s[i][m] == '#':
                a[i][m] = num
                m += 1
            if m < w:
                for j in range(m, w):
                    if s[i][j] == '#':
                        num += 1
                    a[i][j] = num

if q:
    for i in q:
        m = i
        while m < h and a[m][0] == 0:
            m += 1
        if m >= h:
            m = i
            while m > 0 and a[m][0] == 0:
                m -= 1
        a[i][:] = a[m][:]
for i in range(h):
    print(*a[i][:])
def add(pc, p, G, tmp):
    for i in range(len(pc)-1, -1, -1):
        for k in range(pc[i][0]):
            p += (i+1) * 100
            tmp += 1
            if p >= G:
                return tmp


D, G = map(int,input().split())
pc = [list(map(int,input().split())) for i in range(D)]
cnt = 10 ** 9
tmp = 0

for i in range(D):
    p = (i+1) * 100 * pc[i][0]
    p += pc[i][1]
    tmp = pc[i][0]
    if p < G:
        tmp += add(pc, p, G, tmp)
    cnt = min(cnt, tmp)
print(cnt)


### FIXED CODE ###

D, G = map(int, input().split())
pc = [list(map(int, input().split())) for _ in range(D)]

def dfs(question_num, rquired_point):
    if question_num < 0:
        return 10 ** 9

    point = (question_num+1) * 100
    ans_num = min(rquired_point // point, pc[question_num][0])
    score = ans_num * point

    if ans_num == pc[question_num][0]:
        score += pc[question_num][1]

    if rquired_point > score:
        ans_num += dfs(question_num-1, rquired_point-score)
    
    return min(ans_num, dfs(question_num-1, rquired_point))

print(dfs(D-1, G))
import bisect
n = int(input())
a = sorted(list(map(int, input().split())))
l, r = 0, 0
l = max(a)
a.remove(l)
j = bisect.bisect_left(a, l/2)
if abs((l/2) - a[j]) > abs((l/2) - a[j+1]):
    j += 1
print(l, a[min(j, len(a)-1)])

### FIXED CODE ###

import bisect
n = int(input())
a = sorted(list(map(int, input().split())))
l, r = 0, 0
l = max(a)
a.remove(l)
j = bisect.bisect_left(a, l/2)
try:
    if abs((l/2) - a[j-1]) < abs((l/2) - a[j]):
        j -= 1
except:
    pass
print(l, a[min(j, len(a)-1)])
import math

n, m = map(int, input().split())
color = [-1]*n
edge = [list() for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)

flag = True


def dfs(i, pre, c):
    if color[i] == c:
        return
    elif color[i] == 1-c:
        global flag
        flag = False
        return
    color[i] = c
    for v in edge[i]:
        dfs(v, i, 1-c)


dfs(0, -1, 0)
# print(color)
# print(flag)

if flag:
    print(color.count(1)*color.count(0)-m)
else:
    print(math.floor(n*(n-1)/2-m))


### FIXED CODE ###

import math
import sys
sys.setrecursionlimit(10**6)

n, m = map(int, input().split())
color = [-1]*n
edge = [list() for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)

flag = True


def dfs(i, pre, c):
    if color[i] == c:
        return
    elif color[i] == 1-c:
        global flag
        flag = False
        return
    color[i] = c
    for v in edge[i]:
        dfs(v, i, 1-c)


dfs(0, -1, 0)
# print(color)
# print(flag)

if flag:
    print(color.count(1)*color.count(0)-m)
else:
    print(math.floor(n*(n-1)/2-m))
n,m = map(int,input().split())
ans = 0
tmp = int(m/n)
for i in range(1,int(np.sqrt(m))):
    if m%i == 0:
        if (ans < i) and(i <= tmp):
            ans = i
print(ans)

### FIXED CODE ###

import numpy as np

n,m = map(int,input().split())
ans = 0
tmp = int(m/n)
for i in range(1,int(np.sqrt(m)+1)):
    if m%i == 0:
        if (ans < i) and(i <= tmp):
            ans = i
        tmp2 = m//i
        if (ans < tmp2) and(tmp2 <= tmp):
            ans = tmp2
print(ans)
import collections
da = list(map(int,input().split()))
a[] = []
b[] = []
for i in range(da[1]):
  k[i] = list(map(int,input().split()))
  
for i in range(da[1]):
  if k[i][0] == 1 or k[i][1] == 1:
    a.append(k[i])

for i in range(da[1]):
  if k[i][0] == da[0]or k[i][1] == da[0]:
    b.append(k[i])
    
a = list(set(a))
b = list(set(b))

k = a+b
c = collections.Counter(k)

for i in range(len(c)):
  if c[i][1] >1:
    print("POSSIBLE")
    break
  else
    print("IMPOSSIBLE")
  

### FIXED CODE ###

import sys
n,m = map(int,input().split())

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

a.sort()

k = [0 for i in range(n)]

for i in range(m):
    if a[i][0] != 1:
        break
    else:
        k[a[i][1]-1] = 1

for i in range(m):
    if k[a[i][0]-1] == 1:
        if a[i][1] == n:
            print("POSSIBLE")
            sys.exit()
print("IMPOSSIBLE")
n,m=map(int,input().split())
d={}
for i in range(n):
  a,b=map(int,input().split())
  d[b]=a
D=sorted(d.items())
val=0
cnt=0
j=0
while cnt<=m:
  cnt+=int(D[j][0])
  val+=int(D[j][1])
  j+=1
val-=int(D[j][1])*(cnt-m)
print(val)


### FIXED CODE ###

n,m=map(int,input().split())
a=[]
for i in range(n):
  a.append(list(map(int,input().split())))
a.sort()
totl=0
x=0
for j,k in a:
  if x+k<m:
    totl+=j*k
    x+=k
  else:
    totl+=j*(m-x)
    break
print(totl)
calc_lsit = list(map(int,input().split()))
k = int(input())

calc_list = sorted(calc_list)
Answer = calc_list[0] + calc_list[1] + calc_list[2]**k
print(Answer)

### FIXED CODE ###

calc_list = list(map(int,input().split()))
k = int(input())
 
calc_list = sorted(calc_list)
Answer = calc_list[0] + calc_list[1] + calc_list[2]*(2**k)
print(Answer)
n = [input()]
if n.count(7) == 0:
    print("No)
else:
    print("Yes")

### FIXED CODE ###

n = input()
if n.count("7") == 0:
    print("No")
else:
    print("Yes")
n=input()
s=list(input())
x=0
l=[]
for i in s:
    if i=="I":
        x+=1
    elif i=="D":
        x-=1
    l.append(x)
print(max(l))


### FIXED CODE ###

A,B,C,D=map(int,input().split())
sone=A*B
stwo=C*D
if sone>stwo:
    print(sone)
elif sone<stwo:
    print(stwo)
elif sone==stwo:
    print(sone)
a, p = (int(i) for i in input().split())
print(a*3 // p)

### FIXED CODE ###

a, p = (int(i) for i in input().split())  
print((a*3+p) // 2)
print("YES" if input() in 753 else "NO")

### FIXED CODE ###

print("YES" if input() in "753" else "NO")
n, m, k = map(int, input().split())
MOD = 998244353

ans = 0
for i in range(k + 1):
    ans += (ans + m * pow(m - 1, m - i - 1, MOD)) % MOD
    c = (c * (n - 1 - i) * pow(i + 1, MOD - 2, MOD)) % MOD

print(ans)


### FIXED CODE ###

n, m, k = map(int, input().split())
MOD = 998244353

ans = 0
c = 1
for i in range(k + 1):
    ans = (ans + m * pow(m - 1, n - i - 1, MOD) * c) % MOD
    c = (c * (n - 1 - i) * pow(i + 1, MOD - 2, MOD)) % MOD
    # print(f"{ans = }, {c = }")

print(ans)
n = int(input())
squares = list(map(int, input().split(" ")))

odd = 0
for i in range(n, 2):
  if squares[i] % 2 == 1:
    odd += 1
print(odd)

### FIXED CODE ###

n = int(input())
squares = list(map(int, input().split(" ")))

odd = 0
for i in range(0, n, 2):
  if squares[i] % 2:
    odd += 1
print(odd)
def __init__(self):
        pass
    
    def A(self):
        S=input()
        if "BA" in S or "AB" in S:print("Yes")
        else:print("No")
    
    def B(self):
        NAB=list(map(int,input().split()))
        
        if NAB[0]<=NAB[1]:ans=NAB[0]
        elif NAB[0]<=NAB[1]+NAB[2]:ans=NAB[1]
        else:
            tail = NAB[0]%(NAB[1]+NAB[2]) if NAB[0]%(NAB[1]+NAB[2])<NAB[1] else NAB[1]
            ans=(int(NAB[0]/(NAB[1]+NAB[2]))*NAB[1])+tail
            
        print(int(ans))
            
    def C(self):
        AB=list(map(int,input().split()))
        ans=-1
        
        #A<B<100
        for i in range(1,1001):
            if AB[0]==int(i*0.08) and AB[1]==int(i*0.1):
                ans=i
                break
            else:continue
        print(ans)
            
    def D(self):
        pass
        
    def E(self):
        pass
    
    def F(self):
        pass
    
    
if __name__=='__main__':
    obj=abc_158()
    obj.B()

### FIXED CODE ###


class abc_158:
    
    def __init__(self):
        pass
    
    def A(self):
        S=input()
        if "BA" in S or "AB" in S:print("Yes")
        else:print("No")
    
    def B(self):
        NAB=list(map(int,input().split()))
        
        if NAB[0]<=NAB[1]:ans=NAB[0]
        elif NAB[0]<=NAB[1]+NAB[2]:ans=NAB[1]
        else:
            tail = NAB[0]%(NAB[1]+NAB[2]) if NAB[0]%(NAB[1]+NAB[2])<NAB[1] else NAB[1]
            ans=(int(NAB[0]/(NAB[1]+NAB[2]))*NAB[1])+tail
            
        print(int(ans))
            
    def C(self):
        AB=list(map(int,input().split()))
        ans=-1
        
        #A<B<100
        for i in range(1,1001):
            if AB[0]==int(i*0.08) and AB[1]==int(i*0.1):
                ans=i
                break
            else:continue
        print(ans)
            
    def D(self):
        pass
        
    def E(self):
        pass
    
    def F(self):
        pass
    
    
if __name__=='__main__':
    obj=abc_158()
    obj.B()
a,b=map(int, input().split())
if d=='H':
  if a=='H':
    print('H')
  else:
    print('D')
else:
  if a=='H':
    print('D')
  else:
    print('H')

### FIXED CODE ###

a,b=map(str, input().split())

if b=='H':
  if a=='H':
    print('H')
  else:
    print('D')
else:
  if a=='H':
    print('D')
  else:
    print('H')
ls = list(map(int, input().split()))
ls.sort()
if ls[0]==ls[1]==ls[2]==ls[3] and ls[4==ls[5]==ls[6]==ls[7] and ls[8]==ls[9]==ls[10]==ls[11]:
    print('yes')
else:
    print('no')

### FIXED CODE ###

ls = list(map(int, input().split()))
ls.sort()
if ls[0]==ls[1]==ls[2]==ls[3] and ls[4]==ls[5]==ls[6]==ls[7] and ls[8]==ls[9]==ls[10]==ls[11]:
    print('yes')
else:
    print('no')
import sys

N = int(input())
H = input().split()
S = 0
M = H.index(max(H))
for i in range(M):
  if int(H[i]) - int(H[i + 1]) > 0:
    if int(H[i]) - int(H[i + 1]) > 1:
      print('No')
      exit()
    S.append(i)
for j in range(M, N - 1):
  if int(H[M]) - int(H[j]) > 1:
    print('No')
print('Yes')

### FIXED CODE ###

import sys
N = int(input())
H = input().split()
S = 0
for i in range(N):
  if int(H[i]) > S:
    S = int(H[i])
  elif S - int(H[i]) >= 2:
    print('No')
    exit()
print('Yes')
n = int(input())
action = []
for i in range(n):
    action.append(list(map(int,input().split())))

memo = []
for i in range(n):
    memo.append([-1]*3)
def dp(i, a):
    if i == 0:
        return action[0][a]
    elif memo[i][a] != -1:
        return memo[i][a]
    else:
        return memo[i][a] = max(dp(i-1, (a+1)%3), dp(i-1, (a+2)%3)) + action[i][a]

print(max([dp(n-1,a) for a in range(3)]))


### FIXED CODE ###

n = int(input())
action = []
for i in range(n):
    action.append(list(map(int,input().split())))

memo = []
for i in range(n):
    memo.append([-1]*3)

def dp(i, a):
    if i == 0:
        return action[0][a]
    elif memo[i][a] != -1:
        return memo[i][a]
    else:
        memo[i][a] = max(dp(i-1, (a+1)%3), dp(i-1, (a+2)%3)) + action[i][a]
        return memo[i][a]

import sys
sys.setrecursionlimit(1000000)
print(max([dp(n-1,a) for a in range(3)]))
import math
 
N, M = map(int, input().split())

ans1 = 0
if N > 1:
  ans1 = math.factorial(N)/math.factorial(N-2)/2
ans2 = 0
if N > 1:
  ans2 = math.factorial(M)/math.factorial(M-2)/2
print(int(ans1 + ans2))

### FIXED CODE ###

N, M = map(int, input().split())
 
print(N*(N-1)//2+M*(M-1)//2)
from collections import Counter
from collections import deque
from functools import reduce
from pprint import pprint
import bisect
import copy
import fractions
import itertools
import math
import queue
import random
import sys
import time
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def MI(): return map(int, sys.stdin.readline().split())
def II(): return int(sys.stdin.readline())
def IS(): return input()
def C(x): return Counter(x)
def GCD_LIST(numbers): return reduce(fractions.gcd, numbers)
def LCM_LIST(numbers): return reduce(LCM, numbers)
def LCM(m, n): return (m * n // fractions.gcd(m, n))


n, k = MI()
if ((n - 1) * (n - 2)) // 2 < k:
    print(-1)
else:
    graph = []
    for i in range(1, n + 1):
        for j in range(i, n + 1):
            if i != j:
                graph.append([i, j])
    for i in range(n - 1):
        print(*graph[i])
    for k in range((((n - 1) * (n - 2)) // 2) - k):
        print(*graph[n + k])


### FIXED CODE ###

from collections import Counter
from collections import deque
from functools import reduce
from pprint import pprint
import bisect
import copy
import fractions
import itertools
import math
import queue
import random
import sys
import time
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def MI(): return map(int, sys.stdin.readline().split())
def II(): return int(sys.stdin.readline())
def IS(): return input()
def C(x): return Counter(x)
def GCD_LIST(numbers): return reduce(fractions.gcd, numbers)
def LCM_LIST(numbers): return reduce(LCM, numbers)
def LCM(m, n): return (m * n // fractions.gcd(m, n))


n, k = MI()
if ((n - 1) * (n - 2)) // 2 < k:
    print(-1)
else:
    m = (n * (n - 1)) // 2 - k
    print(m)
    graph = []
    for i in range(1, n + 1):
        for j in range(i, n + 1):
            if i != j:
                graph.append([i, j])
    for i in range(m):
        print(*graph[i])
import numpy as np
n, q = map(int, input().split())

e = np.eye(n+1)
for i in range(n-1):
    a, b = map(int, input().split())
    e[a][b] = 1

for i in reversed(range(1, n+1)):
    if e[i-1][i] == 1:
        e[i-1][i+1:] += e[i][i+1:]
    else:
        continue


point = np.zeros(n)
for i in range(q):
    p, x = map(int, input().split())
    point[p-1] += x

ans = np.dot(point, e[1:, 1:])
print(*ans)

### FIXED CODE ###

from collections import deque
n, q = map(int, input().split())
tree = [[] for _ in range(n+1)]
cnt = [0] * (n+1)

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

for _ in range(q):
    p, x = map(int, input().split())
    cnt[p] += x

queue = deque([1])
visited = {1}
while queue:
    now = queue.popleft()
    visited.add(now)
    for t in tree[now]:
        if t in visited:
            pass
        else:
            queue.append(t)
            cnt[t] += cnt[now]

print(*cnt[1:])
H, W = map(int, input().split())
S = [input() for _ in range(H)]
M = {(0, 0): 1}


def dfs(x, y, c):
    cc = float('inf')
    for xx, yy in [(x + 1, y), (x, y + 1), (x - 1, y), (x, y - 1)]:
        if (H, W) == (yy + 1, xx + 1):
            return c + 1
        if 0 <= yy < H and 0 <= xx < W and S[yy][xx] == '.' and \
                ((xx, yy) not in M or M[(xx, yy)] > c + 1):
            M[(xx, yy)] = c + 1
            cc = min(cc, dfs(xx, yy, c + 1))
    return cc


def main():
    ans = 0
    for i in range(H):
        ans += S[i].count('.')
    c = dfs(0, 0, 1)
    if c == float('inf'):
        print(-1)
    else:
        print(ans - c)


main()


### FIXED CODE ###

H, W = map(int, input().split())
S = [input() for _ in range(H)]


def bfs():
    q = [(0, 0)]
    nq = []
    m = []
    c = 1
    while len(q) > 0:
        while len(q) > 0:
            x, y = q.pop(0)
            for xx, yy in [(x + 1, y), (x, y + 1), (x - 1, y), (x, y - 1)]:
                if (H, W) == (yy + 1, xx + 1):
                    return c + 1
                if 0 <= yy < H and 0 <= xx < W and S[yy][xx] == '.' and \
                        (xx, yy) not in m:
                    m.append((xx, yy))
                    nq.append((xx, yy))
        q = nq
        nq = []
        c += 1
    return -1


def main():
    ans = 0
    for i in range(H):
        ans += S[i].count('.')
    c = bfs()
    if c == -1:
        print(-1)
    else:
        print(ans - c)


main()
import numpy as np
N = int(input())
a = np.zeros(N)
for i in range(N):
    a[i+1] = int(input())
i = 1
n = 0
for j in range(N):
    n = n+1
    i = a[i]
    if i == 2:
        print(n)
        break
if i!=2:
    print(-1)

### FIXED CODE ###

import numpy as np
N = int(input())
a = np.zeros(N+1)
for i in range(N):
    a[i+1] = int(input())
i = 1
n = 0
for j in range(N):
    n = n+1
    i = a[i]
    if i == 2:
        print(n)
        break
if i!=2:
    print(-1)
if a*b==0 :
  print("even")
elese:print("odd")

### FIXED CODE ###

a,b=map(int,input().split())
if (a*b)%2 :
    print("Odd")
else:
    print("Even")
N, K = [int(i) for i in input().split()]
ds = [int(i) for i in input().split()]

#N, K = (99999, 1)
#ds = [0]

def run_code(N, K, ds):

    dislike_digits_set = set(i for i in ds)
    avail_digits = [i for i in range(10) if i not in dislike_digits_set]
    avail_min = avail_digits[0]

    def get_next_digit(d):
        last = [10]
        for ad in (avail_digits + last):
            if ad >= d:
                if ad == last:
                    return (1, avail_min)
                else:
                    return (0, ad)

    def to_num(n_digits):
        num = 0
        n = len(n_digits)
        for i in range(n):
            num += n_digits[i] * 10**(n-i-1)
        return num

    def to_digits(num):
        return [int(i) for i in str(num)]

    def search_nearest_larger(num):
        n_digits = to_digits(num)
        n = len(n_digits)

        for i in range(n):
            d_in = n_digits[i]
            inc, d_out = get_next_digit(d_in)
            if inc == 0 and d_in == d_out:
                continue

            if inc > 0:


### FIXED CODE ###

def run_code(N, K, ds):

    dislike_digits_set = set(i for i in ds)
    avail_digits = [i for i in range(10) if i not in dislike_digits_set]
    avail_min = avail_digits[0]

    def get_next_digit(d):
        last = 10
        for ad in (avail_digits + [last]):
            if ad >= d:
                if ad == last:
                    return (1, avail_min)
                else:
                    return (0, ad)

    def fill_last_kth_digits(n_digits, d, k):
        n = len(n_digits)
        for i in range(k):
            n_digits[n - i - 1] = d
        return n_digits

    def to_num(n_digits):
        num = 0
        n = len(n_digits)
        for i in range(n):
            num += n_digits[i] * 10**(n-i-1)
        return num

    def to_digits(num):
        return [int(i) for i in str(num)]

    def search_nearest_larger(num):
        n_digits = to_digits(num)
        n = len(n_digits)

        for i in range(n):
            d_in = n_digits[i]
            inc, d_out = get_next_digit(d_in)
            if inc == 0 and d_in == d_out:
                continue
            if inc > 0:
                num += 10**(n-i)
                n_digits = fill_last_kth_digits(to_digits(num), avail_min, n-i)
                return search_nearest_larger(to_num(n_digits))
            else:
                n_digits[i] = d_out
                return to_num(fill_last_kth_digits(n_digits, avail_min, n-i-1))

        return to_num(n_digits)

    return search_nearest_larger(N)


N, K = [int(i) for i in input().split()]
ds = [int(i) for i in input().split()]
res = run_code(N, K, ds)
print(res)
if s[2]==s[3] and s[4]==s[5]:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

s = input()
if s[2] == s[3] and s[4] == s[5]:
	print('Yes')
else:
	print('No')
s_n = [0, 0, 0]
s_l = [10000, 5000, 1000]
error = '-1 -1 -1'

for i, s in enumerate(s_l):
    if n > -1:
        s_n[i] = int(y/s)
        n = n - s_n[i]
        y = y - s * s_n[i]
    else:
        ans = error
 
if n > -1:
    if y == 0:
        ans = ' '.join(map(str, s_n))
    elif list(set(s_n)) == [0]:
        ans = error
    else:
        ans = error
else:
    ans = error

print(ans)

### FIXED CODE ###

N, Y = map(int, input().split(' '))
res10000 = -1
res5000 = -1
res1000 = -1

for a in range(N+1):
    for b in range(N-a+1):
        c = N - a - b
        total = 10000*a + 5000*b + 1000*c
        if total == Y:
            res10000 = a
            res5000 = b
            res1000 = c

print(str(' '.join(map(str, [res10000, res5000, res1000]))))
n =  int(input())
a = int(input())
b = int(input())

if n * a < b:
  print(n * a)
else:
  print(b)

### FIXED CODE ###

str = input().split()
n = int(str[0])
a = int(str[1])
b = int(str[2])

if n * a < b:
  print(n * a)
else :
  print(b)
N = int(input().strip())
A = list(map(int, input().strip().split(' ')))
if N % 2 == 1:
  checklist = {0: 1}
  for i in range((N-2)//2):
    checklist[(i+1)*2] = 2
else:
  checklist = {(i*2+1):2 in i in range(N//2)}
  
for a in A:
  if a in checklist and checklist[a] in {1,2}:
    checklist[a] -= 1
  else:
    print(0)
    exit()
print(int(2**(N//2)))

### FIXED CODE ###

N = int(input().strip())
A = list(map(int, input().strip().split(' ')))
if N % 2 == 1:
  checklist = {0:1}
  for i in range((N-1)//2):
    checklist[(i+1)*2] = 2
else:
  checklist = {(i*2+1):2 for i in range(N//2)}

for a in A:
  if a in checklist and checklist[a] in {1,2}:
    checklist[a] -= 1
  else:
    print(0)
    exit()
print(int(2**(N//2))%1000000007)