C. Левко ба дарааллыг сэргээх нь

хугацааны хязгаарлалт 1 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Левкод бүхэл тооноос тогтох $a_1, a_2, ... , a_n$ дараалал таалагддаг. Тиймдээ ч тэрээр дараалал дээр төрөл бүрлийн үйлдүүд гүйцэтгэж үздэг. Левко доорх 2 төрлийн үйлдлийн нэгийг нь гүйцэтгэдэг.

  1. $l_i$-ээс $r_i$ хүртэлх дугаартай элементүүдийг $d_i$-ээр ихэсгэх. Өөрөөр хэлбэл $l_i\le j\le ri$ байх $j$-үүдийн хувьд $a_j = a_j + d_i$ гүйцэтгэнэ.
  2. $l_i$-ээс $r_i$ хүртэлх дугаартай элементүүдийн хамгийн их утгыг нь олох. Өөрөөр хэлбэл $m=\max_{j=l_i}^{r_i} a_j$ утгыг олох.

Харамсалтай Левко энэ дарааллаа алдчихжээ. Азаар түүнд $a$ дараалал дээр ямар ямар үйлдлүүд ямар дарааллаар хийсэн нь мэдэгдэж байлаа. Левкод байгаа мэдээлэлтэй зохицох дараалал олж түүнд тусална уу. The results of all operations for the given array must coincide with the record results. Левко түүний дараалалд байсан тоонууд $10^9$-с хэтрэхгүй байсныг нь тод санаж байлаа, тэгээд тэр таниас тусламч хүсч байна.

Оролт

Эхний мөрөнд $n, m (1\le n,m\le 5000)$ тоонууд өгөгдөх ба эдгээр нь харгалзан дарааллын урт ба Левкогийн хийсэн үйлдлийн тоо юм.

Дараагийн $m$ мөрнүүд дараалалд хийгдсэн үйлдлүүдийг илтгэнэ: $i$ дэх мөр $i$-дэх үйлдлийг төлөөлнө.$i$-дэх мөрний эхний тоо $t_i (1\le t_i\le 2)$ тоо нь ямар үйлдэл хийснийг тодорхойлно.Хэрэв $t_i=1$ бол ардаас нь $l_i, r_i d_i (1\le l_i\le r_i\le  n, -10^4\le d_i\le 10^4)$ тоонууд өгөгдөх ба энэ нь эдгээрээр дээр заагдсан 1-р төрлийн үйдлийг хийснийг илтгэнэ. Хэрэв $t_i = 2, $ бол араас нь $l_i, r_i m_i (1 ≤l_i≤r_i≤n, -5·10^7≤m_i≤5·10^7)$ тоонууд өгөгдөх ба энэ нь дээр заагдсан 2-р төрлийн үйлдэл хийгдсэнийг илтгэнэ.

Үйлдлүүд Левкогийн хийсэн дарааллаар өгөгдсөн.

Гаралт

Хэрэв боломжит дараалал олдож байвал эхний мөрөнд "YES" гэж хэвлэ (хашилтгүйгээр), үгүй бол "NO" (хашилтгүйгээр) гэж хэвлэ.

Хэрвээ хариу олдож байвал 2 дахь мөрөнд анхны дарааллыг сэргээж хэвлэ $a_1,a_2, ... ,a_n (|a_i|\le 10^9)$.

Орчуулсан: Төрбат

Жишээ тэстүүд

Оролт
4 5
1 2 3 1
2 1 2 8
2 3 4 7
1 1 3 3
2 3 4 8
Гаралт
YES
4 7 4 7
Оролт
4 5
1 2 3 1
2 1 2 8
2 3 4 7
1 1 3 3
2 3 4 13
Гаралт
NO
Сэтгэгдлүүдийг ачааллаж байна...