問題

背景

うさぎ王国と友好関係を築いたうなぎ王国は，今度は宇宙に進出することにした．目標はうなぎ宇宙ステーションの建設である．しかしながら，無数の小惑星に邪魔をされ，広大な空間を占有することができない．そこで王様はレーザー砲を使い，邪魔な小惑星を破壊し尽くすことにした．

課題

$N \times N$ の二次元格子上に $M$ 個の小惑星がある．縦方向($x$軸に垂直)もしくは横方向($y$軸に垂直)にレーザーを打つことで全ての小惑星を破壊したい．発射されたレーザーは一直線に進み，途中の小惑星を全て貫通してダメージを与える．全てのレーザーは同時に発射され，その出力には，$x$軸に垂直に直線$(x=i)$に沿って最大で $p_{i}$，$y$軸に垂直に直線$(y=j)$に沿って最大で $q_{j}$ の非負整数値を設定することが出来る．小惑星 $k$ は，位置 $(x_{k},y_{k})$ にあり，合計出力が $a_{k}$ 以上あれば破壊されるが，合計出力が $b_{k}$ より大きくなると爆発して非常に危険である．どの小惑星も爆発させることなく，全ての小惑星を破壊できるか判定せよ．

配点

$200$

入力

入力は以下の形式で与えられる．

$N$ $M$
$p_{1}$ ... $p_{N}$
$q_{1}$ ... $q_{N}$
$x_{1}$ $y_{1}$ $a_{1}$ $b_{1}$
...
$x_{M}$ $y_{M}$ $a_{M}$ $b_{M}$

制約

入力中の各変数は以下の制約を満たす．

• \(1 \leq N \leq 1000 (=10³)\)
• \(1 \leq M \leq 100000 (=10⁵)\)
• \(1 \leq p_{i}, q_{i} \leq 1000000 (=10⁶)\)
• $1 \leq x_{i}, y_{i} \leq N$
• $(x_{i}, y_{i}) \neq (x_{j}, y_{j}) (i \neq j)$
• \(1 \leq a_{k} \leq b_{k} \leq 2000000 (=2 \times 10⁶)\)

出力

どの小惑星も爆発させることなく，全ての小惑星を破壊することが可能ならば "yes" ，不可能ならば "no" を一行に出力せよ．

入力例1Copy

2 3
1 2
3 4
2 1 3 5
1 2 3 4
2 2 6 6

入力例1に対する出力例 Copy

yes

下図のようにレーザーの出力を設定すれば，全ての小惑星を安全に破壊できる．

図 $1$

入力例2Copy

2 3
1 2
3 4
2 1 1 1
1 2 2 3
2 2 5 7

入力例2に対する出力例 Copy

no