A. Тхор

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

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

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

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

Тхор Дэлхийд дасаж эхэлж байна. Локи түүнд бэлэг болгон ухаалаг утас өгжээ. Энэ утсанд $n$ ширхэг аппликейшн байна. Тхорын сонирхлыг энэ утас ихэд татаж байгаа бөгөөд тэрэнд нэг жижигхэн асуудал байгаа: Зарим аппликейшнээс үүссэн уншаагүй (буюу онгойлгож үзээгүй) мэдэгдлүүдийг тоолж чадахгүй байгаа (магадгүй Локи үүнд хараал хийсэн болохоор үүнийг тоолж чадахгүй байгаа байх).

$q$ ширхэг үйл явдал болох гэж байгаа (цаг хугацааны дараалалтайгаар). Эдгээр нь 3-н төрөл:

  1. Аппликейшн $x$ нэг мэдэгдэл үүсгэх (энэ шинэ мэдэгдэл нь уншаагүй байна).
  2. Тхор аппликейшн $x$-ын үүсгэсэн бүх мэдэгдлийг унших (заримыг нь дахин уншиж болно).
  3. Тхор утасны аппликейшнээс үүссэн эхний $t$ мэдэгдлийг уншина (эхний $t$ үйл явдлын мэдэгдлүүд). Энэ үйл явдлаас өмнө дор хаяж $t$ ширхэг үйл явдал болсон гэдэг нь баталгаатай. Энд тэрээр эхний уншаагүй $t$ мэдэгдлийг унших биш, харин яг хамгийн эхний $t$ мэдэгдлийг уншиж байгаа гэдгийг анхаарна уу. Үүнээс гадна тэрээр энэ үйл явдалд зарим мэдэгдлийг дахин уншиж болно.

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

Оролт

Эхний мөрөнд аппликейшны тоо болон үйл явдлын тоо болох 2 бүхэл тоо $n$, $q$ ($1 ≤ n, q ≤ 300 000$) өгөгдөнө.

Дараагийн $q$ ширхэг мөрөнд үйл явдлууд өгөгдөнө. $i$ дэхь мөр бүхэл тоо $type_{i}$-ээр эхлэнэ. Энэ нь $i$ дэхь үйл явдлын төрөл. Хэрвээ мөр $type_{i} = 1$ эсвэл $type_{i} = 2$-ээр эхэлж байвал энэ мөрөнд дараагийн тоо $x_{i}$ өгөгдөнө. Харин $type_{i} = 3$-аар эхэлвэл дараагийн тоо $t_{i}$ ($1 ≤ type_{i} ≤ 3, 1 ≤ x_{i} ≤ n, 1 ≤ t_{i} ≤ q$) өгөгдөнө.

Гаралт

Бүх үйл явдлын дараа уншаагүй үлдсэн мэдэгдлийн тоог хэвлэнэ үү.

Орчуулсан: Энхлут

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

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

Тэмдэглэл

Эхний жишээнд:

  1. Аппликейшн $3$ нэг мэдэгдэл үүсгэнэ (Нийт $1$ уншаагүй мэдэгдэлтэй болно).
  2. Аппликейшн $1$ нэг мэдэгдэл үүсгэнэ (Нийт $2$ уншаагүй мэдэгдэлтэй болно).
  3. Аппликейшн $2$ нэг мэдэгдэл үүсгэнэ (Нийт $3$ уншаагүй мэдэгдэлтэй болно).
  4. Тхор аппликейшн $3$-ын үүсгэсэн мэдэгдлийг уншина. Тиймээс уншаагүй $2$ мэдэгдэл үлдэнэ.

2 дахь жишээнд:

  1. Аппликейшн $2$ нэг мэдэгдэл үүсгэнэ (Нийт $1$ уншаагүй мэдэгдэлтэй болно).
  2. Аппликейшн $4$ нэг мэдэгдэл үүсгэнэ (Нийт $2$ уншаагүй мэдэгдэлтэй болно).
  3. Аппликейшн $2$ нэг мэдэгдэл үүсгэнэ (Нийт $3$ уншаагүй мэдэгдэлтэй болно).
  4. Тхор эхний 3-н мэдэгдлийг уншина. Нийт 3-н мэдэгдэл байсан учир нэг ч уншаагүй мэдэгдэл үлдэхгүй.
  5. Аппликейшн $3$ нэг мэдэгдэл үүсгэнэ (Нийт $1$ уншаагүй мэдэгдэлтэй болно).
  6. Аппликейшн $3$ нэг мэдэгдэл үүсгэнэ (Нийт $2$ уншаагүй мэдэгдэлтэй болно).
Сэтгэгдлүүдийг ачааллаж байна...