Problem Description
A bunch of N cats have taken over a H by W units wide space. They have divided it into blocks of 1 by 1 unit and each block is 'owned' by 1 cat. However, a cat can own more than one block and the blocks a cat owned need not be adjacent.
Cats hate socialising with their neighbours but are still curious about how many neighbours they have.
If two cats own blocks which share an edge (not corner), they are known to be neighbours with each other. In other words, if two blocks are adjacent in 4-directional movement, the owners of these two blocks will be neighbours with each other.
Cats are labelled from 0 to N-1 and you will be provided with a H by W map denoting which cat owns which block.
For each cat, output the number of neighbours it has! It is possible that a cat happen to not own any blocks. In that case, it will have 0 neighbours.
Limits
Subtask 1 (23%): 1 ≤ H, W ≤ 10, 1 ≤ N ≤ 100.
Subtask 2 (28%): 1 ≤ H, W ≤ 100, 1 ≤ N ≤ 1000
Subtask 3 (49%): 1 ≤ H, W ≤ 1000, 1 ≤ N ≤ 1000000
Subtask 4 (0%): Sample Testcases.
Input
The first line of input will contain three integers, H, W followed by N.
There will be H lines containing W integers each. Each integer will be between 0 and N-1 and they represent who is the owner of that block.
Output
The output should contain N integers, the ith integer should be the number of neighbours a cat has.
Sample Testcase 1
Input
3 3 5
1 3 4
2 0 1
3 1 2
Output
3
4
3
4
2
Explanation
Cat 0 has 3 neighbours: 1, 2 and 3.
Cat 1 has 4 neighbours: 0, 2, 3 and 4. They are adjacent to either one of the 3 Cat 1's blocks.
Cat 2 has 3 neighbours: 0, 1 and 3.
Cat 3 has 4 neighbours: 0, 1, 2 and 4.
Cat 4 only has 2 neighbours: 1 and 3.
Sample Testcase 2
Input
4 4 3
0 0 0 0
1 1 1 1
0 0 0 0
1 1 1 1
Output
1
1
0
Explanation
Cat 0 and Cat 1 are neighbours.
Cat 2 does not have any block and thus have 0 neighbours.
Sample Testcase 3
Input
1 5 5
0 1 2 3 4
Output
1
2
2
2
1