011 - 決まりを守る漁師

時間制限 1 秒 / メモリ制限 256 MB / 得点 12 / x 0 /


TLE
1sec
MLE
256MB
得点
12

問題

ケンジロウ君は湖で魚を採る漁師です。湖の全体は長方形の形をしています。湖には正方形の形に区切られた管理区画が格子状に並んでいます。地図上では湖の左上の管理区画の座標を(1,1)とし、上からi番目、左からj番目の管理区画の座標を(i,j)としています。これまでの経験で、すべての管理区画に1匹ずつ魚がいることと、それぞれの魚の価格がわかっています。

漁は長方形の網を設置して管理区画のいくつかを網で囲うことで行います。網で囲われた管理区画の中にいる魚はすべて手に入れることができます。しかし、魚の育成を保護するためのルール導入が決まり、漁師はこのルールを守って漁を行うことになりました。ルールの詳細はまだわかりませんが、ルールの基準になるのは一度の網の設置で手に入れた魚を価格の順に並べたときに、安い方から
$K$ 番目に位置する魚の価格であることがわかっています。

ケンジロウ君は、網が設置できるすべての場所について、安い方から $K$ 番目に位置する魚の価格を調べておくことで、少しでも早くルールに対応して漁を始められるようにしようと考えました。

湖のそれぞれの区画にいる魚の価格、管理区画を囲う網の大きさ、魚の価格を調べる位置 $K$ が与えられたときに、網が設置できるすべての場所について安い方から $K$ 番目に位置する魚の価格を表示するプログラムを作成せよ。ただし、網は回転や変形をしない。

入力

入力は以下の形式で標準入力から与えられる。

$H$ $W$ $R$ $C$
$K$
$a$1,1 $a$1,2 ... $a$1,$W$
$a$2,1 $a$2,2 ... $a$2,$W$
:
$a$$H$,1 $a$$H$,2 ... $a$$H$,$W$

1行目に、湖の縦の区画の数 $H$ ( 1 ≤ $H$ ≤ 400 )と横の区画の数 $W$ ( 1 ≤ $W$ ≤ 400 )、管理区画を囲う網の縦の区画の数 $R$ ( 1 ≤ $R$ ≤ $H$ )、横の区画の数 $C$ ( 1 ≤ $C$ ≤ $W$ )が与えられる。続く1行に価格を調べる位置 $K$ ( 1 ≤ $K$ ≤ $R$ × $C$ )が与えられる。続く $H$ 行に、座標($i$,$j$)の区画にいる魚の価格 $a$i,j ( 0 ≤ $a$$i$,$j$ ≤ 1 , 000 , 000 , 000 )が与えられる。

出力

出力は ( $H$ − $R$ + 1 ) × ( $W$ − $C$ + 1 ) 行である。網が設置できるそれぞれの場所について求めた魚の価格を、1行にひとつずつ昇順で出力する。

入出力例

入力例

3 3 2 2
3
5 7 9
8 9 2
3 2 1

出力例

2
8
8
9