Ecosystem

Time limit1sMemory limit128 MB

Summary

Given populations and per-member diets for species ordered by food chain position, simulate feeding in increasing species order and report survivors.

Level: Medium4 of 10
Topics: Simulation, Implementation, Array, Greedy
Solved: No attempts yet

Problem

When you read about environmental disasters such as a large oil spill, you frequently see mention of the damage done to the ecosystem of the affected region. One dimension of an ecosystem is that many different animals and plants depend on one another for survival (or for population control), so introducing a pollutant into the food chain can have all kinds of side effects. Even if the pollutant does not affect a particular animal directly, it might wipe out the zooplankton, leaving the herring with nothing to eat, and in turn leaving too little food for the seals that eat the herring.

We model the ecosystem as follows. There are $n$ species, numbered $1$ through $n$ . A species only ever eats species that are lower on the food chain, that is, species with smaller numbers. For each species you are given its current population (the number of members left after the disaster) and its diet: how many members of each lower-numbered species one member must eat in order to survive. The diet is balanced and cannot be substituted: if one seal must eat exactly one herring and one squid, then two herrings and half a squid (or ten squids) will not do.

When a species feeds, if one or more of its required food sources has already been depleted, then the members that cannot complete their diet starve and die (their other prey is left untouched). To keep the model well-defined, species feed in increasing order of their number. Because a lower-numbered predator feeds before a higher-numbered one, it gets first access to any prey they share: for example, if both seals (say species $5$ ) and dolphins (say species $12$ ) need herring, and the seals have already eaten every remaining herring, then all the dolphins die.

Compute how many members of each species survive.

Input

The first line contains the number of data sets $K$ . Each of the $K$ data sets has the following form.

The first line contains an integer $n$ ( $1 \le n \le 100$ ), the number of species.

Then follow $n$ lines. Line $i$ describes species $i$ and contains $i$ integers. The first integer is the current population of species $i$ . The remaining $i-1$ integers give, for each species $1, 2, \ldots, i-1$ in order, how many of its members one member of species $i$ must eat to survive.

Output

For each data set, first print a line Data Set x:, where $x$ is the number of the data set (starting from $1$ ). Then print $n$ lines: the number of members of species $1, 2, \ldots, n$ that survive one unit of time, one count per line, in order. Separate consecutive data sets with a blank line.

Examples4

Example 1

Input

1
6
200
30 2
1000 0 5
300 1 0 1
20 2 0 0 0
10 1 0 0 0 1

Expected output

Data Set 1:
84
0
0
6
10
10

Example 2
Input
```
1
1
42
```
Expected output
```
Data Set 1:
42
```
Example 3
Input
```
1
2
5
10 1
```
Expected output
```
Data Set 1:
0
5
```

Example 4

Input

Expected output

Data Set 1:
7

Data Set 2:
0
5