Optimal Factory Machine Configuration

A group of engineers is planning to build a new factory. In order for the factory to be reliable, they want to produce various items at a constant and reliable rate (units per second). Different machines can produce these items, and each machine has its own speed. Moreover, each material (or intermediate material) has a fixed production recipe and must be produced on a designated machine.

You are given the description of n materials. For each material, the input provides the production machine's speed and the recipe required to produce that material. The recipe consists of a list of ingredients (other materials) along with the amount needed per unit produced. In addition, you are given a list of final products along with the required production rate for each final product. Your task is to determine an optimal machine configuration.

A configuration is called optimal if and only if, after removing any one machine, there exists at least one material whose production rate falls below the required rate. Equivalently, if for every material i with required production rate R_i and production machine speed s_i, you use exactly

$\lceil \frac{R_i}{s_i} \rceil$

machines, then the configuration is optimal. Note that the required production rates for intermediate materials are determined by the recipes needed to produce the final products. In other words, if a material i appears as an ingredient in the recipe of another material j, then material i must be produced sufficiently fast to cover the demand from material j.

The dependency between materials forms a directed acyclic graph (DAG). You should process materials in an order such that if material i requires material j (i.e. there is an edge from i to j), then i is processed before j. Using this observation, you can compute the required production rate for each material as follows:

For each final product i, initialize
$req[i] = R_i$,
then for every recipe of a material i that requires an ingredient j in quantity q, update
$req[j] += req[i] \times q$.

Finally, for each material i, the number of machines required is given by:

$ans[i] = \lceil \frac{req[i]}{s_i} \rceil$

Output the machine counts for all materials (in order from 1 to n) in one line (space‐separated).

inputFormat

The input begins with an integer n (1 ≤ n ≤ 10⁵), representing the number of materials. The following n lines describe the recipe for each material i (1-indexed):

 speed[i] k  ing1 quantity1 ing2 quantity2 ... ingk quantityk

Here, speed[i] (a positive integer) is the production rate of the machine designated for material i, and k is the number of ingredients required. If k = 0, the material is a raw material and does not require any ingredients. Each ingredient is represented by its material index (ing) and the quantity required per unit production.

After these, an integer F is given, which denotes the number of final products. Each of the next F lines contains two integers:

 material_index required_rate

which means that material material_index must be produced at a rate of at least required_rate units per second.

outputFormat

Output one line containing n integers. The i-th integer represents the number of machines allocated to material i. The configuration must be optimal; that is, for each material, the number of machines is the minimum number required to meet the production rate given the machine speed, computed as

$\lceil \frac{req[i]}{speed[i]} \rceil$

where req[i] is the required production rate for material i (taking into account both final production and requirements from recipes).

sample

4
5 1 2 3
4 1 3 2
10 0
2 0
2
1 10
4 3

2 8 6 2