Description

陶陶最近迷上了滑雪，这天他来到了滑雪场。滑雪场可以看做N*M 的方格区域，每个格子有一个高度，陶陶可以选择任意一个格子作为起点，然后每次可以滑到相邻的某个格子，但要满足经过格子的高度严格递减，同时陶陶可以随时停下来，途中滑的次数就为这条滑雪路径的长度，例如经过了3个格子，路径长度为就为2。有一点需要注意，陶陶不能够停在原地，也就是说路径的长度一定是正整数。

这样的话，陶陶就有很多很多种路径选择，但能发现不可能有无限种路径供陶陶选择，然后陶陶就想知道所有可能路径长度的0至K次方之和为多少。由于答案可能会很大，你只需要输出每个答案Mod 12345后的值。

Format

Input

共N+1行。

第一行包含三个正整数N,M,K。

接下来有N行，每行包含M个不超过10^9的正整数，依次表示每个格子的高度。

Output

共K+1行，每行包含一个非负整数，第i行的整数表示所有可能路径长度的i-1 次方之和Mod 12345后的值。

Samples

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

38
66
136
318

Limitation

N，M<=300,K<=200