생태계

대규모 기름 유출과 같은 환경 재해를 다룰 때 흔히 해당 지역 생태계가 입은 피해가 언급된다. 생태계의 한 가지 측면은 수많은 동식물이 생존(또는 개체 수 조절)을 위해 서로에게 의존한다는 점이다. 따라서 먹이 사슬에 오염 물질이 유입되면 온갖 부작용이 생길 수 있다. 어떤 동물이 오염 물질의 직접적인 영향을 받지 않더라도, 동물성 플랑크톤이 몰살당하면 청어가 먹을 것이 없어지고, 결국 청어를 먹는 물개도 먹이가 부족해진다.

생태계를 다음과 같이 모형화한다. $1$번부터 $n$번까지 번호가 붙은 $n$개의 종이 있다. 각 종은 먹이 사슬에서 자기보다 아래에 있는 종, 즉 번호가 더 작은 종만 잡아먹는다. 각 종에 대해 재해 이후 남은 현재 개체 수와 식단이 주어진다. 식단이란 한 개체가 살아남기 위해 번호가 더 작은 각 종의 개체를 몇 마리 먹어야 하는지를 뜻한다. 식단은 균형 잡힌 것이어서 대체할 수 없다. 예를 들어 물개 한 마리가 반드시 청어 한 마리와 오징어 한 마리를 먹어야 한다면, 청어 두 마리와 오징어 반 마리(또는 오징어 열 마리)로는 대신할 수 없다.

어떤 종이 먹이를 먹으려 할 때 필요한 먹이원 중 하나라도 이미 바닥났다면, 식단을 채우지 못한 개체들은 굶어 죽는다(이때 그 개체들이 먹으려던 다른 먹이는 잡아먹히지 않고 남는다). 모형을 명확히 하기 위해 종은 번호가 작은 순서대로 먹이를 먹는다. 번호가 작은 포식자가 큰 포식자보다 먼저 먹으므로 서로 공유하는 먹이에 먼저 접근할 수 있다. 예컨대 물개(가령 $5$번)와 돌고래(가령 $12$번)가 모두 청어를 필요로 하는데 물개가 남은 청어를 모두 먹어 치웠다면, 돌고래는 모두 죽는다.

각 종에서 몇 마리가 살아남는지를 구하라.

첫 번째 줄에 데이터 집합의 개수 $K$가 주어진다. 이어서 $K$개의 데이터 집합이 다음 형식으로 주어진다.

각 데이터 집합의 첫 번째 줄에는 종의 개수를 나타내는 정수 $n$ ($1 \le n \le 100$)이 주어진다.

그다음 $n$개의 줄이 이어진다. $i$번째 줄은 $i$번 종을 설명하며 $i$개의 정수를 담는다. 첫 번째 정수는 $i$번 종의 현재 개체 수이다. 나머지 $i-1$개의 정수는 $1, 2, \ldots, i-1$번 종 각각에 대해, $i$번 종의 한 개체가 살아남기 위해 그 종의 개체를 몇 마리 먹어야 하는지를 순서대로 나타낸다.

각 데이터 집합마다 먼저 Data Set x: 한 줄을 출력한다. 여기서 $x$는 데이터 집합의 번호이며 $1$부터 시작한다. 그다음 $1, 2, \ldots, n$번 종이 한 단위 시간 뒤에 살아남은 개체 수를 순서대로 한 줄에 하나씩 총 $n$개의 줄로 출력한다. 서로 다른 데이터 집합 사이에는 빈 줄을 하나 넣는다.