Golden Week Contest 2015

A - 得点

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

Golden Week Contest 2015 へようこそ。

このコンテストの配点はいささか複雑そうです。なのでまず、このコンテストで取ることのできる点数を列挙してみましょう。

G 問題以外の問題では、0 点または満点のみを取ることができ、G 問題では、0 点または 58 点または満点のみを取ることができます。

問題を解いていき、それぞれの問題で得られた点数の合計がコンテストでの得点となります。

ちなみに、各問題の満点は、

25,39,51,76,163,111,136,128,133,138

となっており、G 問題の部分点は 58 点です。

入力

この問題には入力はありません。

出力

このコンテストで取ることのできる点数を小さい順に、1 行につき 1 つずつ出力せよ。出力の末尾にも改行を入れること。

例

例えば、もしも問題数が 3 問で配点が、

A 問題：100 点
B 問題：120 点
C 問題：90 点（部分点が 20 点）

だった場合は、

と出力すると正解となります。120 点は 2 通りの取り方ができますが、2 回出力してはいけません。

B - アリ巣

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

無限に広いグリッドのがあり、座標 (0,0) にアリがいる。各整数座標の位置には 0 または 1 の数が書けるようになっていて、最初は全ての座標に 0 が書かれている。最初アリは上の方向（Y 軸の正の方向）を向いていて、以下の行動を無限に繰り返す。

今いる座標に書かれている数が 0 なら 90 度右に向きを変え、1 なら 90 度左に向きを変える。
今いる座標に書かれている数を反転させる。すなわち、元の数が 0 なら 1 を書き、1 なら 0 を書く。
1 歩前進する。すなわち、
- アリが座標 (x,y) にいて上の方向を向いていた場合は、座標 (x,y+1) に移動する。
- アリが座標 (x,y) にいて右の方向を向いていた場合は、座標 (x+1,y) に移動する。
- アリが座標 (x,y) にいて下の方向を向いていた場合は、座標 (x,y-1) に移動する。
- アリが座標 (x,y) にいて左の方向を向いていた場合は、座標 (x-1,y) に移動する。

アリが N 歩目の前進をした直後に、アリがいる座標に書かれている数を答えよ。

入力

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

1 行目には、歩数を表す整数 N (1 ≦ N ≦ 10^{18}) が与えられる。

出力

アリが N 歩目の前進をした直後に、アリがいる座標に書かれている数を 1 行に出力せよ。出力の末尾に改行を入れること。

入力例1

出力例1

10 歩目までのグリッドの様子は以下のようになっている。ただし、a はアリの位置を表している。

入力例2

出力例2

入力例3

出力例3

入力例4

12345678987654321

出力例4

C - Snukeと対戦！

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

Cat Snukeは囲碁をたまに打つ。Snukeは碁石を使った以下のような新たなゲームを思いついた。

H 行 W 列のマス目を書く。
2 人で交互に マスの中 に碁石を 1 つずつ置いていく。碁石の色には黒と白の 2 種類があるが、このうちどちらの色の石を置いても良い。
すでに碁石が置かれているマスには碁石を置くことはできない。また、上下左右に直接隣り合うマスに、置こうとしている石と同じ色の石が 1 つでも 置かれている場合も置くことができない。
碁石を置くことができなくなったプレイヤーが負けとなり、もう一方のプレイヤーが勝ちとなる。

Snukeはあなたにこのゲームで対戦を挑んできた。あなたは先手と後手の好きな方を選ぶことができる。あなたの目的はこのゲームに勝つことである。

入出力

まず、マス目の行数と列数をあらわす 2 つの整数 H (1 ≦ H ≦ 18), W (1 ≦ W ≦ 18) が空白区切りで標準入力に与えられる。

H W

続いて、あなたのプログラムは先手と後手のどちらを選ぶかを出力する。先手の場合は First を、後手の場合は Second を出力すれば良い。末尾には改行を入れること。

先手か後手かを出力すると直ちにゲームが開始される。

先手を選んだ場合は、以下のような流れでゲームを進める。

（★）まず、あなたは碁石を置く場所と置く碁石の色の情報を表す 3 つの整数 a (1 ≦ a ≦ H), b (1 ≦ b ≦ W), c (0 ≦ c ≦ 1) を空白区切りで出力する。これは、あなたが a 行目 b 列目に色 c の碁石を置くということを表すことになる。ただし、色 0 は黒、色 1 は白を表すものとする。末尾には改行を入れること。

a b c

このとき、ルールに違反するような置き方をしようとした場合には直ちに不正解となる。この場合のジャッジ結果は不定である（必ずしも WA になるとは限らない）。また、正しくないフォーマットで出力をした場合の結果も不定である。

（△）次に、Snukeが碁石を置く場所と置く碁石の色の情報を表す 3 つの整数 A (1 ≦ A ≦ H), B (1 ≦ B ≦ W), C (0 ≦ C ≦ 1) が空白区切りで与えられる。これは、Snukeが A 行目 B 列目に色 C の碁石を置くということを表す。ただし、A = B = C = -1 の場合はSnukeが碁石を置く場所がなくなりあなたがゲームに勝ったことを表す。この場合、 あなたのプログラムは直ちに終了しなければならない。 終了しなかった場合のジャッジ結果は不定である。

A B C

ゲームが終了するまで、（★）と（△）を交互に繰り返す。

あなたのプログラムがゲームに勝って終了した場合、正答とみなされる。

また、後手を選んだ場合は、（★）のステップを飛ばして（△）のステップから処理を行う。

出力した後に、出力をflushしなければならないことに注意せよ。flushしなかった場合、TLEとなることがある。

各言語での入出力の方法は過去の AtCoder で出題されている問題 (リンク: ABC 019 D: 高橋くんと木の直径) を参考にしてもよい。

入出力例

説明	プログラムの出力	プログラムへの入力
マス目の行数と列数が与えられている。		2 2
後手を選ぶということを答えている。	Second
Snukeが碁石を置く場所と、置く碁石の色の情報が与えられている。		1 2 0
あなたが碁石を置く場所と、置く碁石の色の情報を答えている。	2 2 1
Snukeが碁石を置く場所と、置く碁石の色の情報が与えられている。		1 1 1
あなたが碁石を置く場所と、置く碁石の色の情報を答えている。	2 1 0
Snukeが碁石を置くことができなくなったという情報が与えられている。		-1 -1 -1

D - 最短絡問題

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

H 行 W 列のマス目に区切られた部屋がある。i (1 ≦ i ≦ H) 行目 j (1 ≦ j ≦ W) 列目のマスをマス (i,j) と呼ぶことにする。マス目とマス目の間には扉があり、扉を開閉するときのコストが定まっている。扉を開閉するときのコストは全て 1 以上の整数である。全ての i (2 ≦ i ≦ H), j (2 ≦ j ≦ W) について、以下のことが成り立っている。

マス (i-1,j-1) とマス (i-1,j) の間の扉の開閉コストを A とする。
マス (i,j-1) とマス (i,j) の間の扉の開閉コストを B とする。
マス (i-1,j-1) とマス (i,j-1) の間の扉の開閉コストを C とする。
マス (i-1,j) とマス (i,j) の間の扉の開閉コストを D とする。
このとき、A+D = B+C かつ A+C ≦ B+D が成り立つ。

マス (si,sj) からマス (ti,tj) まで、上下左右に隣り合うマスに移動することを繰り返して行くときにかかる扉の開閉コストの和の最小値を dist(si,sj,ti,tj) と呼ぶことにする。ただし、隣り合うマスに移動するときにはそれらのマスの間にある扉の開閉コストがかかるものとする。また、任意の i,j に対して、dist(i,j,i,j) = 0 であるとして良い。

あなたは、H と W の値は知っているが、扉の開閉コストの情報は何も知らない。あなたは最初に、

dist(si,sj,ti,tj) の値はいくつですか？

という形式の質問をちょうど H \times W 回行う。そしてその後、同様の形式の Q 個の質問に答えなければならない。

入出力

まず、マス目の行数・列数と質問の個数を表す 3 つの整数 H (1 ≦ H ≦ 20), W (1 ≦ W ≦ 20), Q (1 ≦ Q ≦ 100) が空白区切りで標準入力に与えられる。

H W Q

続いて、あなたのプログラムはちょうど H \times W 回の質問を行わなければならない。

各質問ではまず、4 つの整数 si (1 ≦ si ≦ H), sj (1 ≦ sj ≦ W), ti (1 ≦ ti ≦ H), tj (1 ≦ tj ≦ W) を空白区切りで出力する。これは、「dist(si,sj,ti,tj) の値はいくつですか？」という質問を表す。

si sj ti tj

すると、あなたのプログラムには dist(si,sj,ti,tj) の値が与えられる。 いかなる場合も dist(si,sj,ti,tj) が 10^9 を超えることはないことが保証される。

H \times W 回の質問が終わると、あなたのプログラムは Q 個の質問に答えなければならない。

各質問ではまず、4 つの整数 Si (1 ≦ Si ≦ H), Sj (1 ≦ Sj ≦ W), Ti (1 ≦ Ti ≦ H), Tj (1 ≦ Tj ≦ W) が空白区切りで与えられる。これは、「dist(Si,Sj,Ti,Tj) の値はいくつですか？」という質問を表す。

Si Sj Ti Tj

続いて、あなたのプログラムは dist(Si,Sj,Ti,Tj) の値を出力しなければならない。

Q 個の質問に答え終われば、 あなたのプログラムは直ちに終了しなければならない。 終了しなかった場合のジャッジ結果は不定である。

また、正しくない出力をした場合の結果も不定である（必ずしも WA になるとは限らない）。

あなたのプログラムが Q 個の質問全てに正しく答えて終了した場合、正答とみなされる。

出力した後に、出力をflushしなければならないことに注意せよ。flushしなかった場合、TLEとなることがある。

各言語での入出力の方法は過去の AtCoder で出題されている問題 (リンク: ABC 019 D: 高橋くんと木の直径) を参考にしてもよい。

入出力例

説明	プログラムの出力	プログラムへの入力
マス目の行数・列数と質問の個数が与えられている。		2 2 2
dist(1,1,2,2) の値を質問している。	1 1 2 2
質問の答えが与えられている。		6
dist(1,1,2,2) の値を再び質問している。	1 1 2 2
質問の答えが与えられている。		6
dist(2,1,2,1) の値を質問している。	2 1 2 1
質問の答えが与えられている。		0
dist(2,2,1,1) の値を質問している。	2 2 1 1
質問の答えが与えられている。		6
dist(1,1,2,2) の値を質問されている。		1 1 2 2
質問の答えを出力している。	6
dist(1,2,1,2) の値を質問されている。		1 2 1 2
質問の答えを出力している。	0

E - シフト塗り分け

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

N 個のボールが 1 列に並んでいる。K 種類の色でボールを塗り分ける（K^N 通りの塗り方がある）。連続するちょうど L 個のボールを shift させることを何回か繰り返して色の並びを同じにできるような 2 つの塗り方を同じ塗り方だとみなすとき、何種類の異なる塗り方が存在するだろうか。ただし、ボール i, ボール i+1, ... ボール i+L-1 を shift させるとは、これらのボールをボール i+L-1, ボール i, ボール i+1, ... ボール i+L-2 というように並び替える操作のことであるものとする。

入力

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

N K L

1 行目には、3 つの整数 N (2 ≦ N ≦ 10^6), K (1 ≦ K ≦ 10^6), L (2 ≦ L ≦ N) が空白区切りで与えられる。

出力

異なる塗り方の種類数を 10^9+7 で割った余りを 1 行に出力せよ。出力の末尾に改行を入れること。

入力例1

3 3 3

出力例1

この例では、以下のような 11 通りの異なる塗り方がある。

1,1,1
1,1,2
1,1,3
1,2,2
1,2,3
1,3,2
1,3,3
2,2,2
2,2,3
2,3,3
3,3,3

入力例2

3 3 2

出力例2

この例では、以下のような 10 通りの異なる塗り方がある。

1,1,1
1,1,2
1,1,3
1,2,2
1,2,3
1,3,3
2,2,2
2,2,3
2,3,3
3,3,3

F - ピラミッド - 誕生日編

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

伊織ちゃんのマイブームはピラミッドである。

伊織ちゃんは誕生日プレゼントにピラミッドの模型をもらった。伊織ちゃんは仲の良い友人であるやよいちゃんとピラミッドの模型を使った以下のようなゲームをしている。

N 個のピラミッドを 1 列に並べる。このとき、i (1 ≦ i ≦ N) 番目のピラミッドには A_i 個の石が積まれている。
2 人で交互に以下のどちらかの操作を行う。先手は伊織ちゃんであり、後手はやよいちゃんである。
- いずれか 1 つのピラミッドから、石を 1 つ取り除く。
- N 個全てのピラミッドから、石を 1 つ取り除く。ただしこの操作は行うためには、全てのピラミッドに少なくとも 1 つの石が残っている必要がある。
操作ができなくなった方のプレイヤーが負けとなり、もう一方のプレイヤーが勝ちとなる。

2 人が勝ちを目指して最適な行動を取ったとき、どちらが勝つだろうか？

入力

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

N
A_1 A_2 ... A_N

1 行目には、ピラミッドの個数を表す整数 N (1 ≦ N ≦ 50) が与えられる。
2 行目には、各ピラミッドに積まれた石の個数を表す N 個の整数 A_i (1 ≦ A_i ≦ 50) が空白区切りで与えられる。

出力

先手が勝つ場合は Iori を、後手が勝つ場合は Yayoi を 1 行に出力せよ。出力の末尾に改行を入れること。

入力例1

2
1 1

出力例1

Iori

伊織ちゃんが石を 2 つとも取ると、やよいちゃんは石を取ることができなくなるため、伊織ちゃんの勝ちとなる。

ちなみに、Iori という文字列は「伊織」をローマ字に直したものであり、「I または i」という意味ではない。

入力例2

1
50

出力例2

Yayoi

G - ピラミッド - 球編

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

伊織ちゃんのマイブームはピラミッドである。

伊織ちゃんは半径が 1 である球状の石 L \times (L+1) \times (L+2) / 6 個を 1 辺が L 個となる正四面体状に並べて、ピラミッドのようなものを作ろうとしている。安定して机に置くことができるように、L \times (L+1) / 2 個の円状の穴があいた木の板の上に並べようとしている。しかし、穴をあけるときに失敗をしてしまい、いくつかの穴には石を置けなくなってしまった。正四面体状に並べるときと同じように石を並べていくと、伊織ちゃんはいくつの石を置くことができるだろうか。ただし「正四面体状に並べるときと同じように石を並べていく」とは、以下のような並べ方のことである。

正四面体状に石を並べるときに、下から i (1 ≦ i ≦ L) 段目、奥から j (1 ≦ j ≦ L-i+1) 列目、左から k (1 ≦ k ≦ j) 個目の石を置くはずだった位置を位置 (i,j,k) と呼ぶことにする。ただし、下から 1 段目の奥から x (1 ≦ x ≦ L) 列目に x 個の石が並ぶような向きで置くことを考えているものとする。
まず、下から 1 段目の位置のうち、穴をあけるのに成功していて石を置けるような場所に全て石を置く。
下から 2 段目から L 段目の位置 (i,j,k) のうち、位置 (i-1,j,k) にも位置 (i-1,j+1,k) にも位置 (i-1,j+1,k+1) にも石があるような位置に石を置く、という操作を石を置ける位置がなくなるまで繰り返す。

入力

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

L N
A_1 B_1
A_2 B_2
:
A_N B_N

1 行目には、2 つの整数 L (2 ≦ L ≦ 10^5), N (0 ≦ N ≦ Min(10^5, L \times (L+1) / 2)) が空白区切りで与えられる。これは、1 辺が L 個となる正四面体状に石を並べる予定であったことと、穴をあけるのに失敗した位置が N 個あるということを表す。
2 行目からの N 行には、穴をあけるのに失敗した位置の情報が与えられる。このうち i (1 ≦ i ≦ N) 行目には、2 つの整数 A_i (1 ≦ A_i ≦ L), B_i (1 ≦ B_i ≦ A_i) が与えられる。これは、奥から A_i 列目、左から B_i 個目の穴をあけるのに失敗したということを表す。ただし、同じ位置の情報が 2 回以上与えられないことが保証される。

部分点

この問題には部分点が設定されている。

N ≦ 20 を満たすデータセット 1 に正解した場合は、58 点が与えられる。
全てのテストケースに正解した場合は、満点が与えられる。

出力

伊織ちゃんが置く石の個数を 1 行に出力せよ。出力の末尾に改行を入れること。

入力例1

3 1
2 1

出力例1

位置 (1,1,1)、位置 (1,2,2)、位置 (1,3,1)、位置 (1,3,2)、位置 (1,3,3)、位置 (2,2,2) の 6 箇所に石を置くことができる。

入力例2

100000 0

出力例2

166671666700000

このように、穴をあけるのに実は失敗していなかったということもありうるので注意すること。

入力例3

出力例3

H - ピラミッド - デコ編

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

伊織ちゃんのマイブームはピラミッドである。

伊織ちゃんは半径が 1 である球状の石を大量に持っている。デコレーションが好きな伊織ちゃんは石の色が気に入らなかったので、全ての石を黒か白のどちらかの色で塗ってしまった。

伊織ちゃんは L \times (L+1) \times (L+2) / 6 個を 1 辺が L 個となる正四面体状に並べて、ピラミッドのようなものを作ろうとしている。安定して机に置くことができるように、L \times (L+1) / 2 個の円状の穴があいた木の板の上に並べようとしている。しかし、ただ並べるだけではつまらないので、仲の良い友人であるやよいちゃんと以下のようなゲームをしながら並べていくことにした。

正四面体状に石を並べるときに、下から i (1 ≦ i ≦ L) 段目、奥から j (1 ≦ j ≦ L-i+1) 列目、左から k (1 ≦ k ≦ j) 個目の石を置く位置を位置 (i,j,k) と呼ぶことにする。ただし、下から 1 段目の奥から x (1 ≦ x ≦ L) 列目に x 個の石が並ぶような向きで置くことを考えているものとする。
2 人で交互に、下から 1 段目の位置に石を 1 つずつ置いていく。このとき、置く石の色に制限はない。先手は伊織ちゃんで、後手はやよいちゃんである。
下から 1 段目の L \times (L+1) / 2 個の位置全てに石を置かれたら、ゲームは終了となり、結果を以下のような手順で判定する。
- 下から 2 段目から L 段目の位置 (i,j,k) のうち、位置 (i-1,j,k) にも位置 (i-1,j+1,k) にも位置 (i-1,j+1,k+1) にも石があるような位置に石を置く、という操作を石を置ける位置がなくなるまで繰り返す。このとき、位置 (i,j,k) に置く石の色は以下のような規則で決める。
  - 位置 (i-1,j,k) と位置 (i-1,j+1,k) と位置 (i-1,j+1,k+1) にある石のうち、黒い石の個数が 2 個または 0 個なら黒
  - そうでないなら白
- 一番上に置かれた石が黒なら伊織ちゃんの勝ちで、白ならやよいちゃんの勝ちとなる。

今ゲームが終了し、これからゲームの結果を判定しようとしている。どちらが勝っているだろうか？

入力

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

L N
A_1 B_1
A_2 B_2
:
A_N B_N

1 行目には、2 つの整数 L (2 ≦ L ≦ 10^9), N (0 ≦ N ≦ Min(1000, L \times (L+1) / 2)) が空白区切りで与えられる。これは、1 辺が L 個となる正四面体状に石を並べる予定であり、下から 1 段目に黒い石が N 個あるということを表す。
2 行目からの N 行には、黒い石の置かれた位置の情報が与えられる。このうち i (1 ≦ i ≦ N) 行目には、2 つの整数 A_i (1 ≦ A_i ≦ L), B_i (1 ≦ B_i ≦ A_i) が与えられる。これは、位置 (1,A_i,B_i) に黒い石が置かれているということを表す。ただし、同じ位置の情報が 2 回以上与えられないことが保証される。

出力

伊織ちゃんが勝ちなら Ioriを、やよいちゃんが勝ちなら Yayoi を 1 行に出力せよ。出力の末尾に改行を入れること。

入力例1

2 2
2 1
1 1

出力例1

Iori

入力例2

3 0

出力例2

Yayoi

I - ピラミッド - 立方体編

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

伊織ちゃんのマイブームはピラミッドである。

伊織ちゃんは球状の石を使ったピラミッドに飽きてしまったため、今度は 1 辺の長さが 1 である立方体状の石を使ってピラミッドを作ることにした。伊織ちゃんは以下のような手順でピラミッドを作ることにした。

N \times N のマス目を紙に書く。各マスの 1 辺の長さは 1 である。i (1 ≦ i ≦ N) 行目 j (1 ≦ j ≦ N) 列目のマスをマス (i,j) と呼ぶことにする。
各マスに石を 1 個以上縦に積んで置く。マス (i,j) には H_{i,j} 個の石を積み上げる。
マスを 1 つ選ぶ。このマスをマス P と呼ぶことにする。
いくつかの石（0 個でもよい）を取り除く。このとき、残った石が マス P を中心としたピラミッド を構成していなければならない。

ただし、石がマス P を中心としたピラミッドを構成している状態とは以下のような状態である。

マス P をマス (Pi,Pj)、マス (i,j) に積まれている石の個数を S_{i,j}、S_{Pi,Pj} を T と呼ぶことにすると、全ての i (1 ≦ i ≦ N), j (1 ≦ j ≦ N) に対して、以下の式が成り立っている。ただし、Abs(x) は x の絶対値を表すものとする。
- S_{i,j} = Max(0, T - Max(Abs(Pi - i), Abs(Pj - j)))
- S_{i,j} ≦ Min(Pi, Pj, N - Pi + 1, N - Pj + 1)

このとき、マス P に積まれている石の個数を ピラミッドの高さ と呼ぶことにする。

全ての i (1 ≦ i ≦ N), j (1 ≦ j ≦ N) に対して、マス (i,j) を中心としたピラミッドを作るときにできるピラミッドの高さの最大値を求め、それらの和を答えよ。

入力

入力は複数のテストケースからなる。

（ テストケースの生成方法が少し特殊ですが、これは入力ファイルのサイズを削減するための措置であり、他に特に深い意味はありません。 ）

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

N Q
X A B C
H_{1,1} H_{1,2} ... H_{1,N}
H_{2,1} H_{2,2} ... H_{2,N}
:
H_{N,1} H_{N,2} ... H_{N,N}

1 行目には、マス目の 1 辺の個数を表す整数 N (1 ≦ N ≦ 500) と、テストケース数を表す整数 Q (1 ≦ Q ≦ 10) が空白区切りで与えられる。
2 行目には、4 つの整数 X (0 ≦ X < C), A (0 ≦ A < C), B (0 ≦ B < C), C (N ≦ C ≦ 30,000) が空白区切りで与えられる。これらは、テストケースを生成する際の乱数を生成するために使われる整数である。
3 行目からの N 行には、最初に各マスに積む石の個数の情報が与えられる。このうち i (1 ≦ i ≦ N) 行目には、N 個の整数が空白区切りで与えられる。このうち j (1 ≦ j ≦ N) 個目の整数 H_{i,j} (1 ≦ H_{i,j} ≦ N) はマス (i,j) に積む石の個数を表す。

出力

出力は Q 行からなる。このうち i 行目には、i 個目のテストケースに対する答えを出力せよ。出力の末尾にも改行を入れること。

ソースコードは以下のようなC言語風の疑似コードに沿って書けばよい。

int N, Q, X, A, B, C;
int H[500][500];
int Rand() {
  return X = (A * X + B) % C;
}
void Shuffle() {
  for (int i = 0; i < N*N; ++i) {
    int ai = Rand() % N;
    int aj = Rand() % N;
    int bi = Rand() % N;
    int bj = Rand() % N;
    if (ai == bi && aj == bj) continue;
    swap(H[ai][aj], H[bi][bj]);
  }
}
void main() {
  入力を読み込む
  for (int i = 0; i < Q; i++) {
    この時点でのN,Hに対する答えを計算し、出力
    if (i != Q-1) Shuffle();
  }
  return 0;
}

入力例1

出力例1

35
27
30

1 つ目のテストケースは以下のようになる。

このとき、各マスを中心としたピラミッドの高さの最大値は以下のようになる。

これらの和は 35 であるため、出力の 1 行目には 35 と出力する。

2 つ目のテストケースは以下のようになる。

このとき、各マスを中心としたピラミッドの高さの最大値は以下のようになる。

これらの和は 27 であるため、出力の 2 行目には 27 と出力する。

3 つ目のテストケースは以下のようになる。

このとき、各マスを中心としたピラミッドの高さの最大値は以下のようになる。

これらの和は 30 であるため、出力の 3 行目には 30 と出力する。

J - ピラミッド - 2D編

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

伊織ちゃんのマイブームはピラミッドである。

伊織ちゃんはピラミッドを題材にした問題を思いついた。しかし、その問題は既出の問題だということが発覚し、伊織ちゃんは拗ねてしまった。そして、伊織ちゃんは別の問題を考えることにした。

段数が無限である 2 次元のピラミッドを考える。上から i (1 ≦ i) 段目の左から j (1 ≦ j ≦ i) 個目の石を石 (i,j) と呼ぶことにする。石 (A,B) と石 (C,D) を取ることを考える。石 (i,j) を取るためには、石 (i-1,j-1) と石 (i-1,j) を先に取らなければならない（i-1 < 1 または j-1 < 1 または j > i となる場合は石が最初から存在しないため取る必要はない）。石 (A,B) と石 (C,D) を取る方法であって、取る石の個数が最小となるような取り方は何通りあるだろうか？ただし、取り方は石を取る順番によって区別され、石を取る順番が異なる時 2 つの取り方は違う取り方であるということにする。また、同じタイミングで 2 つ以上の石を取ることはできない。

入力

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

T
A_1 B_1 C_1 D_1
A_2 B_2 C_2 D_2
:
A_T B_T C_T D_T

1 行目には、テストケースの個数を表す整数 T (1 ≦ T ≦ 300,000) が与えられる。
2 行目からの T 行には、各テストケースの情報が与えられる。このうち i (1 ≦ i ≦ T) 行目には、4 つの整数 A_i (1 ≦ A_i ≦ 10^6), B_i (1 ≦ B_i ≦ A_i), C_i (1 ≦ C_i ≦ 10^6), D_i (1 ≦ D_i ≦ C_i) が与えられる。これは、i 番目テストケースにおける A,B,C,D の値を表す。ただし、A_i ≠ C_i または B_i ≠ D_i が成り立つことが保証されている。また、取る必要のある石の個数が 10^6 個を超えないことも保証されている。

出力

出力は T 行からなる。このうち i (1 ≦ i ≦ T) 行目には、i 番目のテストケースの答えを 10^9+7 で割った余りを出力せよ。出力の末尾にも改行を入れること。

入力例1

6
2 1 2 2
1 1 1000000 1000000
3 2 5 3
5 2 4 3
2015 55 1700 1300
100 50 1000 500

出力例1

1 個目のテストケースでは以下の 2 通りの取り方がある。

石 (1,1)、石 (2,2)、石 (2,1) の順に取る。
石 (1,1)、石 (2,1)、石 (2,2) の順に取る。