Description

School X is holding an in-school training camp before CSP.

There are $n$ OIers taking part in this training camp, and the coach has carefully prepared $m$ sets of mock contest problems for them.

However, each OIer has their own schedule. Coincidentally, in the next $k$ days, each of them happens to have exactly $m$ days free to do mock contests.

To make management easier, the coach requires that each person must complete the $m$ sets of mock contests in order.

For example, if Xiao X is free on days $2,3,5$ in the next days, then they must do the $1$st set on day $2$, the $2$nd set on day $3$, and the $3$rd set on day $5$.

The coach needs to prepare for every person’s every mock contest. To reduce workload, if multiple people do the same set of mock contest problems on the same day, then the coach only needs to prepare one mock contest using that set of problems on that day.

As a top student in the lab, the coach wants you to help compute how many mock contests they need to prepare each day.

Input Format

The first line contains three integers $n,m,k$.

In the next $n$ lines, each line contains $m$ integers. The integer $a_{i,j}$ in row $i$ and column $j$ indicates that for the $i$-th person, the $j$-th free day among the next $k$ days is day $a_{i,j}$.

Output Format

Output one line with $k$ integers. The $i$-th integer indicates the number of mock contests the coach needs to prepare on day $i$ among the next $k$ days.

1 3 5
2 3 5

0 1 1 0 1

6 3 7
2 3 4
2 5 7
3 5 7
1 3 5
5 6 7
1 2 3

1 2 3 1 3 1 1

10 10 20
2 3 4 8 9 11 12 16 17 18
2 3 6 10 12 13 14 15 19 20
1 3 7 10 11 13 14 15 17 19
1 2 4 6 7 9 15 17 19 20
2 3 5 6 9 11 14 16 19 20
1 2 3 8 9 10 11 12 15 19
1 4 6 7 9 12 13 17 18 19
1 7 8 9 10 11 13 15 18 20
1 5 6 7 8 9 13 16 18 19
4 5 7 10 11 13 14 17 18 20

1 2 2 3 2 2 4 3 3 3 3 4 2 1 3 1 2 2 2 1

Hint

This problem uses bundled tests.

• Subtask 1 (13 points): $n = m = k = 1$.
• Subtask 2 (24 points): $n = 1$.
• Subtask 3 (24 points): $m = 1$.
• Subtask 4 (39 points): no special constraints.

For $100\%$ of the testdata, $1 \le n,m,k \le 10^3$, $m \le k$, $1 \le a_{i,1} < a_{i,2} < \cdots < a_{i,m} \le k$.

Translated by ChatGPT 5