E. Машины зогсоол

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

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

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

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

Хотод $n$ машины багтааж бүхий, нэг эгнээнд байрлах машины зогсоолын талбай бий. Зогсоолуудыг зүүнээс баруун тийш $1-n$ тоогоор дугаарласан.

Машин зогсоолд ирэхэд оператор уг машин зогсож болох сул зогсоолыг зааж өгнө. Болгоомжлох үүднээс операторын заах зогсоол нь машинтай зогсоолоос аль болох хол байх хэрэгтэй. Хэрвээ тийм газар олон байвал оператор бага дугаартайг нь сонгоно. Бүх зогсоол сул байвал машиныг $1$ дугаартай зогсоолд байрлуулна.

$i$-р болон $j$-р зогсоолуудын хоорондох зайг $4 \cdot |i-j|$ метр байна гэж үзнэ.

Танд одоог хүртэл машины зогсоолын талбайд ирсэн болон явсан машинуудыг хугацаагаар нь дараалуулан бүртгэсэн тэмдэглэл өгөгдсөн бол машин бүрд оператороос ямар дугаар зааж өгснийг олно уу.

Оролт

Эхний мөр нь зогсоолын тоо болон тэмдэглэлийн бичлэгийн тоог харуулах зайгаар тусгаарлагдсан $n$ ба $m$ $(1≤n, m≤2 \cdot 10^{5})$ хоёр бүхэл тоог агуулна.

Дараагийн $m$ тооны мөр нь тэмдэглэлийн тайлбарыг агуулна. $i$-р мөр нь $t_{i}$, $id_{i}$ $(1≤t_{i}≤2; 1≤id_{i}≤10^{6})$ тоонуудыг агуулна. $t_{i}=1$ бол харгалзах тэмдэглэл нь $id_{i}$ дугаартай машин зогсоолд ирсэн гэдгийг харуулна. Харин $t_{i}=2$ бол харгалзах тэмдэглэл нь $id_{i}$ дугаартай машин зогсоолоос явсан гэдгийг харуулна.

Зогсоолд ирсэн болон зогсоолоос явсан тухай тэмдэглэлүүд нь цаг хугацааны дарааллаар өгөгдөнө. Бүх үйл явдал дараалан авагдах бөгөөд ямар ч 2 үйл явдал зэрэг явагдахгүй.

Оролтод өгөгдөх тэмдэглэлд дараах нөхцлүүдийг үргэлж биелэхийг анхаарна уу.

  • машин бүр хамгийн ихдээ $1$ удаа зогсоолд ирнэ, зогсоолоос явна,
  • машин зогсоолд өмнө нь ирээгүй бол машины явсан тэмдэглэл байхгүй,
  • ямар ч үед зогсоолд $n$-ээс олон тооны машин зогсохгүй.

Та машиныг ялгаатай $1-10^{6}$ хүртэл тоогоор дурын байдлаар дугаарлаж болно. Эхэндээ бүх зогсоолууд хоосон байна гэж үзнэ.

Гаралт

Ирсэн машин бүрийн хувьд зогссон зогсоолын дугаарыг нь ирсэн дарааллаар нь хэвлээрэй.

Орчуулсан: Солонго

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

Оролт
7 11
1 15
1 123123
1 3
1 5
2 123123
2 15
1 21
2 3
1 6
1 7
1 8
Гаралт
1
7
4
2
7
4
1
3
Сэтгэгдлүүдийг ачааллаж байна...