J. Halzoom's Coffee Grid
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

After securing enough Moonlit Moss to keep their lantern flickering, Sam07a, Omar, and Abd-Elmohaymen ventured deeper into a particularly ancient and silent part of the Unknown — the Elderwood. The trees were impossibly tall, their bark etched with glowing glyphs that shifted when no one looked directly at them.

Their journey came to a halt at a moss-covered stone monolith. As they approached, the surface shimmered and revealed a magical window into another part of the forest — a humble cabin hidden among the trees. Inside lived a curious engineer named Halzoom, famed not only for his inventions but also for brewing the finest magical coffee in the Unknown.

In that cabin, Halzoom faced a peculiar problem. His comical cat, 3ntar, had recently fallen in love with a mysterious, graceful feline who roamed the Elderwood. 3ntar, now struck by divine inspiration, demanded a coffee that matched his "love mood" — a special number $$$k$$$.

To prepare this enchanting blend, Halzoom turned to his experimental grid of coffee beans. Each cell in the grid held a smell strength, and the aroma of the final cup must come from a rectangle (submatrix) of beans whose total smell equals exactly $$$k$$$.

The beautiful cat that 3ntar fell in her love.

His challenge? Find all rectangles (submatrices) in the grid where the sum of values is exactly $$$k$$$. For every value inside any of those rectangles, keep it. All other values must be changed to $$$0$$$.

Now, it's your task to help Halzoom, 3ntar, and the Elderwood explorers all at once — by solving this aromatic mystery.

Input

The first line contains integers $$$n$$$, $$$m$$$, $$$k$$$ $$$(1 \le n, m \le 100,\ 0 \le k \le 10^4)$$$ — the number of rows, columns, and the desired total smell value.

The next $$$n$$$ lines contain $$$m$$$ integers each — the smell values in the grid $$$(0 \le a_{ij} \le 100)$$$.

Output

Print the grid after finding all valid rectangles. Keep the values that are part of at least one rectangle with total sum $$$k$$$, and change all others to $$$0$$$.

Example
Input
5 5 5
1 1 1 1 5
1 7 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 5
Output
1 0 1 1 5 
1 0 1 1 0 
1 1 1 1 1 
1 1 1 1 1 
1 0 1 1 5
Note

In the first example:

The highlight on columns and rows, those submatrices will be printed with the same values.