Wood Plank Orders

You are given one or more datasets. Each dataset consists of an inventory of wood planks and a set of orders. The inventory is given as a list of wood types along with the length available per plank. Each order specifies a number of pieces needed from a specific wood type, along with the required length per piece.

Your task is to compute, for each wood type in the inventory, the minimum number of planks required to satisfy the orders. The number of planks needed for a specific wood type is calculated using the formula \[ planks = \left\lceil \frac{\text{total required length}}{\text{plank length}} \right\rceil \] where \(\lceil x \rceil\) denotes the ceiling of \(x\). If there is no order for a given wood type, then 0 planks are required.

The input terminates with a line containing "0 0" which should not be processed.

inputFormat

The input consists of one or more datasets. Each dataset begins with a line containing two integers I and J, where I is the number of inventory items and J is the number of orders.

This is followed by I lines, each containing two integers: the wood_type and the available plank_length for that type.

Then follow J lines, each containing three integers: the number of pieces required, the wood_type for the order, and the required_length for each piece.

The last dataset is followed by a line containing "0 0" which signals the end of input.

outputFormat

For each dataset, output a single line containing space-separated integers. Each integer represents the minimum number of planks required for the corresponding inventory item (in the same order they were listed in the input).

3 2
1 500
2 1000
3 300
5 1 100
3 2 250
0 0

1 1 0