Bản đồ thế giới là một hình chữ nhật kích thước ~n \times m~, mỗi ô thuộc về một trong ~k~ quốc gia. Các ô của mỗi quốc gia luôn liên thông kề cạnh (từ một ô của quốc gia đó có thể đi lên/xuống/trái/phải để tới mọi ô khác của cùng quốc gia mà không sang quốc gia khác).

Trong thời kỳ bất ổn, quốc gia ~i~ coi toàn bộ các ô nằm trong hình chữ nhật nhỏ nhất (các cạnh song song với cạnh bản đồ) bao phủ tất cả ô của quốc gia ~i~ là "lãnh thổ lịch sử" của mình. Khi đó, quốc gia ~i~ sẽ có yêu sách lãnh thổ đối với mọi quốc gia ~j \ne i~ nếu trong hình chữ nhật đó có xuất hiện ít nhất một ô thuộc quốc gia ~j~.

Hãy xác định với mỗi quốc gia ~i~, có bao nhiêu quốc gia mà ~i~ có yêu sách lãnh thổ.

Input

• Dòng ~1~: ba số nguyên ~n, m, k~ - chiều cao bản đồ, chiều rộng bản đồ, số quốc gia ~(1 \le n, m \le 2 \cdot 10^5; 1 \le k \le nm \le 2 \cdot 10^6)~.

• ~n~ dòng tiếp theo: mỗi dòng gồm ~m~ số nguyên, số ở cột ~j~ của dòng ~i~ là ~a_{i,j}~ ~(1 \le a_{i,j} \le k)~ - mã quốc gia của ô ~(i,j)~.

• Bảo đảm: mỗi trong ~k~ quốc gia xuất hiện ít nhất một ô, và tập ô của mỗi quốc gia liên thông kề cạnh.

Output

In ra ~k~ số nguyên, trong đó số thứ ~i~ là lượng quốc gia mà quốc gia ~i~ có yêu sách lãnh thổ.

Sample Input 1

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

Sample Output 1

2 1 0 0