[ARC165D] Substring Comparison

给定正整数 $n,m$ 和 $m$ 个形如 $(A_{i},B_{i},C_{i},D_{i})$ 的限制条件。 判断是否存在一个长度为 $n$ 的序列 $P$ 满足 $\forall i \in [1,m]$，$P_{A_{i} \dots B_{i}}$ 字典序小于 $P_{C_{i} \dots D_{i}}$。 $1 \leq n,m \leq 2 \times 10^{3}$。

[problemUrl]: https://atcoder.jp/contests/arc165/tasks/arc165_d 整数列 $ X=(X_1,X_2,\dots,X_n) $ に対し $ X[L,R] $ で整数列 $ (X_L,X_{L+1},\dots,X_{R}) $ を表します。 整数 $ N,M $ と $ M $ 個の整数の組 $ (A_i,B_i,C_i,D_i) $ が与えられます。 長さ $ N $ の整数列 $ X $ であって、すべての $ i=1,2,\dots,M $ に対して以下の条件を満たすものが存在するか判定してください。 - $ X[A_i,B_i] $ は $ X[C_i,D_i] $ より辞書式順序で小さい。 数列の辞書順とは？数列 $ S\ =\ (S_1,S_2,\ldots,S_{|S|}) $ が数列 $ T\ =\ (T_1,T_2,\ldots,T_{|T|}) $ より**辞書順で小さい**とは、下記の 1. と 2. のどちらかが成り立つことを言います。 ここで、$ |S|,\ |T| $ はそれぞれ $ S,\ T $ の長さを表します。 1. $ |S|\ \lt\ |T| $ かつ $ (S_1,S_2,\ldots,S_{|S|})\ =\ (T_1,T_2,\ldots,T_{|S|}) $。 2. ある整数 $ 1\ \leq\ i\ \leq\ \min\lbrace\ |S|,\ |T|\ \rbrace $ が存在して、下記の $ 2 $ つがともに成り立つ。 - $ (S_1,S_2,\ldots,S_{i-1})\ =\ (T_1,T_2,\ldots,T_{i-1}) $ - $ S_i $ が $ T_i $ より（数として）小さい。

入力は以下の形式で標準入力から与えられます。 > $ N $ $ M $ $ A_1 $ $ B_1 $ $ C_1 $ $ D_1 $ $ A_2 $ $ B_2 $ $ C_2 $ $ D_2 $ $ \vdots $ $ A_M $ $ B_M $ $ C_M $ $ D_M $

条件を満たす整数列が存在する場合は `Yes` を、存在しない場合は `No` を出力してください。

4 2
1 3 3 4
4 4 1 2

Yes

3 2
1 2 2 3
2 2 1 1

No

15 20
2 5 6 14
11 14 10 10
13 15 6 10
8 10 3 8
7 8 1 9
2 8 14 15
14 14 5 12
6 10 9 9
1 4 10 14
5 14 6 7
8 10 5 8
8 10 11 15
4 8 4 11
7 9 1 4
8 10 3 3
11 13 8 14
6 13 4 15
4 7 6 11
2 5 1 2
8 14 6 8

No

### 制約 - $ 2\ \leq\ N\ \leq\ 2000 $ - $ 1\ \leq\ M\ \leq\ 2000 $ - $ 1\ \leq\ A_i\ \leq\ B_i\ \leq\ N $ - $ 1\ \leq\ C_i\ \leq\ D_i\ \leq\ N $ - 入力される値はすべて整数 ### Sample Explanation 1 例えば $ X=(1,1,2,1) $ とすると条件を満たします。 ### Sample Explanation 2 条件を満たす整数列 $ X $ は存在しません。