Asteroid Mining

Shofa is working on her new spacefaring game, No Person’s Star. The star systems in the game are procedurally generated, and contain stars, planets and asteroids. The asteroids are only used to mine minerals, and consist of multiple mineral veins. Players can only mine one vein at a time, and they will always mine the vein with the most minerals first.

One of the clever things Shofa has done is to base asteroids on two previously generated asteroids. To generate a new asteroid $i$, she copies all mineral veins from asteroid $a_{i1}$ to the new asteroid, and scales them all up by multiplying with the factor $f_{i1}$. She then does it again with asteroid $a_{i2}$ and the factor $f_{i2}$.

For example, if asteroid $0$ contains the mineral veins $[3.0, 4.0, 5.0]$, and asteroid $1$ contains the mineral veins $[14.0, 56.0]$, then combining them with $f_{i1} = 1.1$ and $f_{i2} = 0.5$ will create a new asteroid with the mineral veins $[3.3, 4.4, 5.5, 7.0, 28.0]$.

This can be a bit iffy, because newer asteroids could grow their total mineral amount exponentially! However, she thinks this will not be a problem in practice if she generates them based on the current state of the parent asteroids: Hopefully people will stay at the same asteroid until it’s out of resources.

To test this hypothesis, she has gotten some prototype testers to play the game for her, and she is now parsing the logs. Could you help her double check the results for her?

Input

The first line contains three integers, $A$, $A_{init}$ and $E$: The total number of asteroids at the end, the number of initial asteroids, and the number of events in the event log.

Next follow $2 A_{init}$ lines describing the contents of the initial asteroids, two lines per asteroid:

  • The first line contains an integer $n_ i$, the number of mineral veins in this asteroid.

  • The second line contains $n_ i$ real numbers $m_{i,j}$, each describing the amount of minerals in a single vein.

Then follow $E$ lines, one per event, ordered by their event time:

  • mine $a_ i$ $g_ i$ – denoting a player mining the $g_ i$ most mineral-rich veins on asteroid $a_ i$

  • generate $a_{i1}$ $f_{i1}$ $a_{i2}$ $f_{i2}$ – denoting the creation of the next asteroid, generated as explained above

The first generate event creates the asteroid with index $A_{init}$, the second with index $A_{init}+1$ and so on.

Output

For each asteroid, print a line containing the total amount of minerals in the asteroid along with the total amount of minerals in the biggest mineral vein (or $0$ if there are no more veins left). The numbers must have an absolute or relative error of at most $10^{-6}$, and can be printed in scientific notation.

Limits

  • $0 < A \leq 350$

  • $0 < A_{init} \leq \min (10, A)$

  • $0 < E \leq 700$

  • $0 < n_ i \leq 1\, 000$ and $0.0 < m_{i,j} < 200.0$

  • Asteroids have been created before they are first mentioned in the event log

  • Asteroids will always contain less than $10^{222}$ minerals in total

  • For mine events: $0 < g_ i \leq size(a_ i)$ and $g_ i \leq 300$, where $size(a_ i)$ is the current number of mineral veins on asteroid $a_ i$

  • For generate events: $0.5 \leq f_{i1}, f_{i2} \leq 2.0$

  • Real numbers in the input will have at most $4$ digits after the decimal point

Sample Input 1 Sample Output 1
4 2 5
3
3.0 4.0 5.0
4
14.0 56.0 57.0 105.0
mine 1 2
generate 0 1.1 1 0.5
mine 1 1
generate 2 1.1 1 2.0
mine 3 2
12.0 5.0
14.0 14.0
48.2 28.0
22.22 7.7