"""
This program will verify a solution to Bytelandian Exchange 3. To use:
python byteland-3-check.py < solution.txt
If the program executes with no assertion errors, your solution is correct.
The first line of the file is two integers N and p, with N = the number of the coin you start
with and p = the smallest coin that Machine #1 will output. (For the basic challenge, p = 1,
and for the Bonus, p = 2.)
Each line after the first is a single number that represents an exchange:
-N means to put a coin with a value of N into Machine #1.
This will add three coins valued N/2, N/3, and N/4 to your collection.
N means to put a coin with a value of N into Machine #2, along with your smallest-valued coin
with a value of at least p. This will add a coin with a value of N+1 to your collection.
For example, the input might start like this:
897 1
-897
-224
-56
-14
-3
299
300
This represents 5 uses of Machine #1 followed by 2 uses of Machine #2. At this point, the coins
you have will be: 448 301 112 74 28 18 7 4
At the end you must have at least 2 coins worth >= p, one of which is worth >= N.
"""
import sys, collections
lines = list(sys.stdin)
N, p = map(int,lines[0].split())
coins = collections.Counter()
coins[N] = 1
for line in lines[1:]:
n = int(line)
assert abs(n)
if n < 0:
# Use Machine 1
n = -n
assert coins[n]
coins[n] -= 1
coins[n//2] += 1
coins[n//3] += 1
coins[n//4] += 1
else:
# Use Machine 2
m = min(coin for coin in coins if coins[coin])
assert coins[n]
assert coins[m]
coins[n] -= 1
coins[m] -= 1
if n == m:
assert coins[n] >= 0
coins[n+1] += 1
# Throw out useless coins
for n in coins:
if n < p:
coins[n] = 0
print("%s | %s" %
(line.strip(),
" ".join(map(str, sorted(list(coins.elements()), reverse=True))))
)
largest = max(coin for coin in coins if coins[coin])
ncoins = sum(coins.values())
assert largest >= N and ncoins > 1