AT_code_festival_morning_hard_c 宝探し 2

[problemUrl]: https://atcoder.jp/contests/code-festival-2014-morning-hard/tasks/code_festival_morning_hard_c 太郎君は、ある広場にお宝を探しにやってきました。 この広場には、水平な方向に $ n $ 本、垂直な方向に $ m $ 本の線が等間隔に引かれています。隣接する線同士の距離は $ 1 $ です。上から $ i $ 番目の水平な線と左から $ j $ 番目の垂直な線が交わる点の位置は ($ i,\ j $) で表され、そこには $ k $ 種類のうちの $ 1 $ つのお宝が $ 1 $ つだけ埋められています。 太郎君は最新の機械を持っているので、どこにどのようなお宝が埋まっているかをすべて知っています。そこで、太郎君はこの広場の中のさまざまな長方形の領域に対して、その中にどのようなお宝が多く埋まっているかを調べようとしています。 しかし、次郎君がときどきいたずらをして、隣接しているお宝の位置を入れ替えてしまいます。ここでお宝が隣接しているとは、それぞれのお宝が埋まっている点同士の距離がちょうど $ 1 $ であることを言います。 次郎君のいたずらに困ってしまった太郎君に代わって、与えられた各領域に対して、その時に領域の中にある最も数の多いお宝を求めてください。

入力は以下の形式で与えられる。 > $ n $ $ m $ $ k $ $ a_{1,1} $ $ a_{1,2} $ $ ... $ $ a_{1,m} $ $ ... $ $ a_{n,1} $ $ a_{n,2} $ $ ... $ $ a_{n,m} $ $ q $ $ t_1 $ $ x_{11} $ $ y_{11} $ $ x_{21} $ $ y_{21} $ $ ... $ $ t_q $ $ x_{1q} $ $ y_{1q} $ $ x_{2q} $ $ y_{2q} $ - $ 1 $ 行目には、広場に引かれた水平な線の本数を表す整数 $ n $ ($ 1\ \leq\ n\ \leq\ 500 $)、垂直な線の本数を表す整数 $ m $ ($ 1\ \leq\ m\ \leq\ 500 $) と、広場に埋められているお宝の種類数を表す整数 $ k $ ($ 1\ \leq\ k\ \leq\ 100 $) が与えられる。 - 続く $ n $ 行には、広場の各位置に埋められているお宝の種類が与えられる。 - $ a_{i,j} $ ($ 1\ \leq\ a_{i,j}\ \leq\ k $) は、広場の ($ i,\ j $) の位置に埋められているお宝の種類を表す。 - $ n\ +\ 2 $ 行目には、クエリの数を表す整数 $ q $ ($ 1\ \leq\ q\ \leq\ 100{,}000 $) が与えられる。 - 続く $ q $ 行には、それぞれのクエリの情報が与えられる。 - $ t_i $ ($ 1\ \leq\ t_i\ \leq\ 2 $) は、$ i $ 番目のクエリの種類を表す。 - $ t_i\ =\ 1 $ のとき、$ i $ 番目のクエリが次郎君によってお宝が交換されるクエリであることを表し、($ x_{1i},\ y_{1i} $) の位置にあるお宝と ($ x_{2i},\ y_{2i} $) の位置にあるお宝が交換されることを意味する。 - $ t_i\ =\ 1 $ のとき、($ x_{1i},\ y_{1i} $) と ($ x_{2i},\ y_{2i} $) は隣接していることが保証される。 - $ t_i\ =\ 2 $ のとき、$ i $ 番目のクエリが現在のお宝の状況を調べるクエリであることを表し、($ x_{1i},\ y_{1i} $) と ($ x_{2i},\ y_{2i} $) を対角線上の頂点とする広場に引かれた線に平行な長方形の中にあるお宝の状況を調べることを意味する。 - $ t_i\ =\ 2 $ のとき、$ x_{1i}\ \leq\ x_{2i} $ かつ $ y_{1i}\ \leq\ y_{2i} $ であることが保証される。 - 各クエリにおいて、$ 1\ \leq\ x_{1i},\ x_{2i}\ \leq\ n $ かつ $ 1\ \leq\ y_{1i},\ y_{2i}\ \leq\ m $ であることが保証される。

それぞれの $ t_i\ =\ 2 $ のクエリに対して、各クエリが表す長方形内に含まれる最も数の多いお宝の種類とその数を $ 1 $ 行で出力せよ。 最も数の多いお宝の種類が複数ある場合は、その中で最もお宝の種類を表す数が大きいものを答えよ。 最後は改行し、余計な文字、空行を含まないこと。