24145번 - 折り紙 (Origami) 다국어

あなたは JOI 高校の文化祭の展示のため，貼り絵を作ることになった．

貼り絵は，台紙にいくつかの折り紙を貼り付け作るのだが，折り紙を重ねて貼ると厚みが出 てはがれやすくなる．そこで折り紙が最も多く重なっている部分が何枚重ねであるのかと，そ の部分の合計の面積を知りたい．

まず貼り絵を作るための台紙として，横 a cm，縦 b cm の長方形の紙を使うことにした．こ の台紙には 1 cm おきに辺に平行になるように縦横に直線が引かれ，全体でa×b 個の一辺 1 cm の正方形の格子ができるように区切られている．これより，左から x 列目，下から y 行目の格 子を (x, y) と表す．

図 1: 横 8 cm，縦 6 cm の長方形の台紙 (a = 8, b = 6 の場合)

次に，台紙の上に n 枚の長方形の折り紙を順番に貼っていく．折り紙の貼り方 (折り紙を貼る 位置) は，4 つの整数の組 (p, q, r, s) で指定される．p, q, r, s は

1 ≤ p ≤ r ≤ a, 1 ≤ q ≤ s ≤ b

をみたす整数である．これは横 (r − p + 1) cm × 縦 (s − q + 1) cm の長方形の折り紙を，4 つ の格子 (p, q), (p, s), (r, q), (r, s) が折り紙の角になるように，台紙の上に貼ることを意味する．

下の図は，横 8 cm，縦 6 cm の長方形の台紙に，4枚の折り紙を(2, 4, 3, 6), (5, 1, 6, 6), (2, 5, 8, 5), (1, 2, 5, 3) の順番に貼った様子を図示したものである．このとき最も多く折り紙を重ねている部 分は 2 枚重ねであり，その部分の合計の面積は 6cm² である．

図 2: 貼付け方の例

入力として台紙の大きさと，台紙に貼る折り紙の貼り方が与えられたとき，最も多く折り紙 が重なっている部分は何重であるかと，その部分の面積を求めるプログラムを書け．ただし，入 力では，必ず 2 枚以上の紙が重なっている格子が存在する．

入力の 1 行目には台紙に貼る折り紙の枚数を表す整数 n (1 ≤ n ≤ 5, 000) が書かれている．

2 行目には台紙の大きさを表す整数 a, b (1 ≤ a, b ≤ 1, 000, 000) が横，縦の順に書かれている．

i + 2 行目 (1 ≤ i ≤ n) には，i 枚目の折り紙の貼り方を表す 4 つの整数 p_i, q_i, r_i, s_i が書かれ ている．p_i, q_i, r_i, s_i は

1 ≤ p_i ≤ r_i ≤ a, 1 ≤ q_i ≤ s_i ≤ b, r_i − p_i < 20, s_i − q_i < 20

を満たす．すなわち，貼り絵に用いる折り紙の辺の長さは 20 cm 以下である．

出力は標準出力に 2 行で出力する．

1 行目には最も多く折り紙が重なっている部分は何重に貼られているかを表す整数を，2 行目 には最も沢山の折り紙が重なっている部分の面積を表す正の整数 (単位は cm²) を出力せよ．