AT_arc047_d [ARC047D] ナナメクエリ

[problemUrl]: https://atcoder.jp/contests/arc047/tasks/arc047_d 縦に $ N $ 行、横に $ N $ 列の方眼紙があります。 この方眼紙上の最も左上のマスから下に $ X $ マス、右に $ Y $ マス進んだところにあるマスをマス $ (X,\ Y) $ と呼ぶことにします。 つまり、最も左上のマスはマス $ (0,\ 0) $ 、右下のマスはマス $ (N-1,\ N-1) $ になります。 初め、全てのマスには整数 $ 0 $ が書き込まれています。 この方眼紙に $ Q $ 回のクエリ操作を行うことを考えます。 クエリ操作は $ 3 $ 種類あり以下のとおりです。 - `1 A B C` : $ A\ ≦\ X+Y\ ≦\ B $ となる全てのマス $ (X,\ Y) $ にかかれている整数に $ C $ を加える。$ 0\ ≦\ A\ ≦\ B\ ≦\ 2N-2,\ -10^5\ ≦\ C\ ≦\ 10^5 $ を満たすことが保証される。 - `2 A B C` : $ A\ ≦\ X-Y\ ≦\ B $ となる全てのマス $ (X,\ Y) $ にかかれている整数に $ C $ を加える。$ 1-N\ ≦\ A\ ≦\ B\ ≦\ N-1,\ -10^5\ ≦\ C\ ≦\ 10^5 $ を満たすことが保証される。 - `3 A B C D` : $ A\ ≦\ X\ ≦\ B $ かつ $ C\ ≦\ Y\ ≦\ D $ となる全てのマス $ (X,Y) $ の中の最大値 $ M $ と、その範囲の中に $ M $ が書かれたマスがいくつあるか求める。$ 0\ ≦\ A\ ≦\ B\ ≦\ N-1,\ 0\ ≦\ C\ ≦\ D\ ≦\ N-1 $ を満たすことが保証される。 このようなクエリを順番に処理するプログラムを書いてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ Q $ $ Query_1 $ $ Query_2 $ : $ Query_Q $ - $ 1 $ 行目には方眼紙の大きさを表す整数 $ N(1\ ≦\ N\ ≦\ 5,000) $ とクエリの個数を表す整数 $ Q(1\ ≦\ Q\ ≦\ 5,000) $が空白区切りで与えられる。 - $ 2 $ 行目からの $ Q $ 行の内 $ i $ 行目には $ i $ 番目のクエリが与えられる。クエリの形式は問題文中で与えたとおりである。 - $ 3 $ 種類目のクエリは $ 1 $ 個以上与えられる。

出力の行数は $ 3 $ 種類目のクエリの個数と等しくなる。 $ i $ 行目には $ i $ 番目の $ 3 $ 種類目のクエリの答えを出力せよ。 範囲の中の最大値を $ M $、その個数を $ C $ とすると $ M,\ C $ をこの順で空白区切りで出力せよ。 出力の末尾に改行を入れること。

### 部分点 この問題には部分点が設定されている。 - $ 1\ ≦\ N\ ≦\ 50 $を満たすデータセットに正解した場合は $ 10 $ 点が与えられる。 - $ 1\ ≦\ N\ ≦\ 500 $を満たすデータセットに正解した場合はさらに $ 20 $ 点が与えられる。合計で$ 30 $点となる。 - $ 1\ ≦\ N\ ≦\ 5,000 $を満たすデータセットに正解した場合はさらに $ 70 $ 点が与えられる。合計で$ 100 $点となる。 ### Sample Explanation 1 $ 1 $ 番目のクエリを処理した後の方眼紙の様子は以下の様になります。 !\[\](https://arc047.contest.atcoder.jp/img/arc/047/fajeojasopef/D-1.png)$ 2 $ 番目のクエリの範囲は以下の様な範囲です。 !\[\](https://arc047.contest.atcoder.jp/img/arc/047/fajeojasopef/D-2.png)よって最大値は $ 2 $、 個数は $ 4 $ 個になります。 $ 3 $ 番目のクエリを処理した後の方眼紙の様子は以下の様になります。 !\[\](https://arc047.contest.atcoder.jp/img/arc/047/fajeojasopef/D-3.png)$ 4 $ 番目のクエリの範囲は以下の様な範囲です。 !\[\](https://arc047.contest.atcoder.jp/img/arc/047/fajeojasopef/D-4.png)よって最大値は $ 5 $、 個数は $ 7 $ 個になります。