Mixing Spices to Match a Secret Ratio

Chef Serge, the renowned chef from Salt, Pepper & Garlic, is preparing for a secret inspection by a Michelin reviewer. The reviewer demands that the dish's spice mix has ingredients in the exact ratio \(A:B:C\) (salt, pepper, and garlic powder respectively). In the kitchen, Serge has several bottles of mixed spices. For each bottle, he knows the amounts (in kilograms) of salt, pepper, and garlic powder it contains. He can use any fraction of a bottle (from 0 up to the full bottle), and mix spices from one or more bottles to achieve the required ratio.

Formally, suppose a bottle \(i\) contains \(s_i, p_i, g_i\) for salt, pepper, and garlic powder respectively. By taking a fraction \(x_i\) (with \(0 < x_i \le 1\)) from some selected bottles, the overall mixture is given by:

[ \left(\sum_{i\in S} x_i s_i, ; \sum_{i\in S} x_i p_i, ; \sum_{i\in S} x_i g_i\right) = t,(A, B, C)\quad (t>0). ]

Your task is to determine, after every update to the set of bottles, the minimum number of bottles required to produce a mixture that exactly matches the ratio \(A:B:C\). If it is impossible with the available bottles, output \(-1\).

Note that initially there are some bottles on the shelf. Then the available bottles will change, as some bottles are added or removed. Bottles are identified by an integer id: the initial bottles are numbered from 1 to \(N\) and each new bottle gets a new id sequentially.

Example:

Bottle ID	Salt	Pepper	Garlic Powder
1	10	20	30
2	300	200	100
3	12	15	27

If the reviewer requires a \(1:1:1\) ratio, one valid solution is to use all of bottle 1 and take 60 kilograms from bottle 2 (which gives 30 kg salt, 20 kg pepper, and 10 kg garlic powder). Thus, the answer in that scenario is 2 bottles. Note that if bottle 2 is removed, it may become impossible.

inputFormat

The input is given as follows:

1. The first line contains three space-separated integers \(A, B, C\) representing the required ratio.
2. The second line contains an integer \(N\), the number of initially available bottles.
3. Each of the next \(N\) lines contains three integers \(s_i\), \(p_i\), and \(g_i\), the amounts of salt, pepper, and garlic powder in bottle \(i\) respectively.
4. The next line contains an integer \(Q\), the number of update events.
5. Each of the following \(Q\) lines starts with an integer op:
   • If op = 1, it is an addition event, followed by three integers \(s\), \(p\), and \(g\) (the amounts in the new bottle). The new bottle is assigned the next available id.
   • If op = 2, it is a removal event, followed by an integer id which is the id of the bottle to remove.

outputFormat

After each update event, output a single line containing the minimum number of bottles required to achieve a mixture that meets the reviewer's ratio requirement. If it is impossible, output \(-1\).

Mixing condition: There exist values \(x_i\) (with \(0 < x_i \le 1\)) for the selected bottles \(i\) such that:

[ \sum_{i\in S} x_i s_i = tA, \quad \sum_{i\in S} x_i p_i = tB, \quad \sum_{i\in S} x_i g_i = tC \quad (t > 0). ]

You can take fractions of a bottle; hence, if a bottle's composition is already exactly proportional to \((A,B,C)\), it can be used alone.

sample

1 1 1
3
10 20 30
300 200 100
12 15 27
3
2 2
1 20 20 20
2 1

-1
1
1

</p>