Tracking Out-of-Stock Items in an Online Store

You are given an online store system that maintains a list of products, each identified by a unique SKU and an initial stock quantity. As purchase orders come in, the stock for each product is decreased accordingly. Your task is to determine which products go out-of-stock (i.e. their stock becomes zero or negative) for the first time, and list them in the order in which they run out of stock. If no product goes out of stock during the orders, output "No SKUs out of stock".

More formally, you are provided with:

• Two integers \(n\) and \(m\), representing the number of SKUs and the number of purchase orders respectively.
• \(n\) lines each containing a SKU identifier (a string) and its initial stock quantity (an integer).
• \(m\) lines each containing a SKU identifier and a purchase quantity.

For each order, if the SKU exists and its current stock is above zero, subtract the purchase quantity from the stock. If the stock becomes zero or less for the first time due to an order, record that SKU. Finally, output the recorded SKUs separated by a space. If none of the SKUs ever run out of stock, output "No SKUs out of stock".

inputFormat

The input is read from standard input (stdin) and is formatted as follows:

 n m
 sku1 initial_stock1
 sku2 initial_stock2
 ...
 skun initial_stockn
 sku_order1 order_quantity1
 sku_order2 order_quantity2
 ...
 sku_orderm order_quantitym

Here, the first line contains two integers \(n\) and \(m\). The next \(n\) lines each contain a SKU identifier and its corresponding initial stock. This is followed by \(m\) lines that represent the orders.

outputFormat

Output a single line to standard output (stdout) containing the SKU identifiers that go out of stock (in the order they first drop to zero or below), separated by a space. If no SKU goes out of stock, output "No SKUs out of stock".

2 3
sku1 10
sku2 10
sku1 3
sku2 5
sku1 3

No SKUs out of stock