#2827. 滑雪

滑雪

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