E. Замын хажуугийн моднууд

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

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

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

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

Лисс хэрэм самарт дуртай. Лисс таныг хэсэг самрын мод тарихыг хүсжээ.

Зам дагуу мод тарих нийт $n$ байрлал байдаг (баруунаас зүүн уруу 1-ээс $n$ хүртэл дугаарлагдсан). Моднууд нь сар болгонд нэг метр ургадаг. Сар болгоны эхэнд та нэг асуултыг гүйцэтгэх юм. Асуулт нь дараах төрлүүдийн нэг нь байна:

  1. $p$ байрлалд $h$ өндөртэй мод тарина.
  2. Баруунаас эхлэн оршин байгаа $x$-дэх (тайрагдаагүй) модыг тайрна. Бид модыг тайрч унагаасны дараа уг мод байсан байрлал дээрх бүх боломжит зайг уг мод эзлэх юм. Иймд уг байрлал дээр ахин мод тарих боломжгүй болно.

Асуулт бүрийг гүйцэтгэсний дараа та хамгийн урт өсөж буй дэд дарааллын уртыг хэвлэх ёстой. Хэрэв тухайн олонлог доторх моднуудын өндрүүд нь баруунаасаа зүүн уруугаа эрс ихсэж байвал уг оршин буй моднуудын дэд олонлогийг өсөж буй дэд дараалал гэнэ. Жишээлбэл уг олонлогийн хамгийн баруун талын мод нь олонлог доторх хамгийн намхан мод байх юм. Уг өсөж буй дэд дарааллын урт гэдэг нь түүн дотор байх моднуудын тоог хэлнэ.

Лисс ижил өндөртэй моднуудад дургүй болохыг анхаарна уу. Иймд ямар ч үед яг ижил өндөртэй моднууд байхгүй байна.

Оролт

Эхний мөрөнд байрлалуудын тоо болон асуултуудын тоо болох 2 бүхэл тоо $n$ болон $m$ ($1  ≤ n ≤ 10^{5}; 1 ≤ m ≤ 2*10^{5}$) өгөгдөнө.

Дараагийн $m$ мөрөнд дараах хэлбэрүүдтэй асуултуудын мэдээлэл өгөгдөнө:

  • Хэрэв $i$-дахь асуулт нь 1-р төрлийн байвал $i$-дахь мөрөнд 3 бүхэл тоо 1, $p_{i}$, болон $h_{i}$ ($1 ≤ p_{i} ≤ n, 1 ≤ h_{i} ≤ 10$) өгөгдөх ба энд $p_{i}$ нь шинэ модны байрлал ба $h_{i}$ нь шинэ модны анхны өндөр байна.
  • Хэрэв $i$-дахь асуулт нь 2-р төрлийн байвал $i$-дахь мөрөнд 2 бүхэл тоо 2 болон $x_{i}$ ($1 ≤ x_{i} ≤ 10$) өгөгдөх ба энд $x_{i}$ нь бидний огтлохыг хүссэн модны дугаар байна.

Оролт нь зөв байна. Ө.х:

  • 1-р төрлийн асуултуудын хувьд , $p_{i}$-ууд нь хос хосоороо ялгаатай байна.
  • 2-р төрлийн асуултууд хувьд , $x_{i}$ нь одоогийн моднуудын тооноос бага эсвэл тэнцүү байна.
  • Ямар ч үед яг ижил өндөртэй 2 мод байхгүй байна.

Мөр болгонд бүхэл тоонууд нь зайгаар тусгаарлагдсан байна.

Гаралт

Асуулт бүрийн дараа хамгийн урт өсөж буй дэд дарааллын уртыг хэвлэх ба нийт $m$ ширхэг бүхэл тоо хэвлэнэ. Тоонуудыг цагаан зайгаар тусгаарласан байна.

Орчуулсан: Баатархүү

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

Оролт
4 6
1 1 1
1 4 4
1 3 4
2 2
1 2 8
2 3
Гаралт
1
2
3
2
2
2

Тэмдэглэл

Асуулт болгоны дараах гудамжнуудын байрлалыг та дараах хүүхэлдэйн киноноос харж болно:

Хэрэв таны browser animation png-г дэмжихгүй байвал http://212.193.37.254/codeforces/images/162/roadtree.gif эндээс gif хэлбэрээр харна уу.

Сэтгэгдлүүдийг ачааллаж байна...