AT_agc017_e [AGC017E] Jigsaw

Description

[problemUrl]: https://atcoder.jp/contests/agc017/tasks/agc017_e $ N $ 個の特殊なジグソーピースがあります.それぞれのピースは,幅が $ 1 $ で高さが $ 1 $ 以上の長方形のパーツを $ 3 $ つつなげた形をしています. $ i $ 番目のピースは,次のような形をしています: - 高さ $ H $ のパーツの左側に高さ $ A_i $ のパーツを,右側に高さ $ B_i $ のパーツをくっつけた形.ただし,左側のパーツの一番下の辺,右側のパーツの一番下の辺は,それぞれ中央のパーツの一番下の辺から $ C_i,\ D_i $ だけ上にある. ![](https://cdn.luogu.com.cn/upload/vjudge_pic/AT_agc017_e/085913e2ea706e9f5a234d65bf3ad02f7f07f135.png) すぬけ君は,これらのピースを,一辺が $ 10^{100} $ の正方形の形をしたテーブルの上に置こうとしています.この時,次の条件を満たさなければなりません: - すべてのピースをテーブルの上に置く. - すべてのピースの中央のパーツの一番下の辺全体は,テーブルの手前の辺に接している. - 左右のパーツの一番下の辺全体は,テーブルの手前の辺に接しているか,他のピースを構成するあるパーツの上の辺と接している. - ピースを回転させたり,反転させたりして用いてはならない. このような並べ方ができるかどうかを判定してください.

Input Format

N/A

Output Format

N/A

Explanation/Hint

### 制約 - $ 1\ \leq\ N\ \leq\ 100000 $ - $ 1\ \leq\ H\ \leq\ 200 $ - $ 1\ \leq\ A_i\ \leq\ H $ - $ 1\ \leq\ B_i\ \leq\ H $ - $ 0\ \leq\ C_i\ \leq\ H\ -\ A_i $ - $ 0\ \leq\ D_i\ \leq\ H\ -\ B_i $ - 入力はすべて整数 ### Sample Explanation 1 例えば,下図のように並べればよいです. !\[\](https://atcoder.jp/img/agc017/27db184b6924d4cec5077a54b505706a.png)