C. Тэсрэх бөмбөг

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

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

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

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

Танд хавтгай дээрх тэсрэх бөмбөгүүдийг устгадаг робот байдаг. Тэгш хавтгай дээр $n$ ширхэг тэмрэх бөмбөг байдаг ба $i$ дэх тэсрэх бөмбөг $(x_i,y_i) $ координаттай. Тэсрэх бөмбөгүүдийн координатууд ялгаатай ба аль ч тэсрэх бөмбөгийн координат нь $(0,0)$ биш. Анхлан робот нь $(0,0) $ цэг дээр байх ба дараах гурван төрлийн үйлдлүүдээр тэсрэх бөмбөгүүдээ устгана: (роботын тухайн үеийн байрлалыг $(x,y)$ гэе.)

  1. "1 k dir" төрлийн үйлдэл. Энэ нь робот dir чиглэлд $k(k \ge 1)$ удаа шилжилт хийхийг илтгэнэ. Робот нь "R", "L", "U", "D" гэсэн 4 чиглэлд шилжилт хийж чадах ба эдгээр нь харгалзан $(x+1,y), (x-1,y),(x,y+1),(x,y-1)$ координаттай байрлал руу шилжих шилжилт юм. Хэрэв явах замд(мөн эцсийн зогсох цэг дээр нь) нь тэсрэх бөмбөг байвал энэ үйлдлийг хийх хориотой.
  2. "2" төрлийн үйлдлээр $(x,y)$ цэг дээрх тэсрэх бөмбөгийг робот аваад тусгай саванд хийнэ. Тэгээд робот энэ тэсрэх бөмбөгийг аль ч цэгээс аль ч цэг рүү хүргэж болно. Саванд нэгээс олон тэсрэх бөмбөг нэгэн зэрэг байж болохгүй ба $(x,y)$ координаттай цэг дээр тэсрэх бөмбөг байхгүй бол энэ үйлдлийг гүйцэтгэх боломжгүй.
  3. "3" төрлийн үйлдлээр тэсрэх бөмбөгөө тусгай савнаасаа гаргаад устгадаг. Энэ үйлдлийг робот $(0,0)$ координаттай цэг дээр байхад л гүйцэтгэх ба тусгай сав нь хоосон бол энэ үйлдэл гүйцэтгэгдэх боломжгүй. Роботод бүх тэсрэх бөмбөгийг устгах үйлдлүүдийн хамгийн цөөн дарааллыг олоход нь тусална уу.

Оролт

Эхний мөрөнд координатын хавтгай дээрх тэсрэх бөмбөгийн тоо $n (1\le n\le 10^5)$ өгөгдөнө. Дараагийн $n$ мөр бүрт тус бүрд нь 2 ширхэг бүхэл тоо өгөгдөнө. $i$ дэх мөр нь $i$ дэх тэсрэг бөмбөгний байрлал $(x_i, y_i) (-10^9\le x_i,y_i\le 10^9)$ бүхэл тоон хосыг агуулна. Нэг цэг дээр хоёр тэсрэх бөмбөг байрлахгүй ба аль ч тэсрэх бөмбөг $(0,0)$ цэг дээр байрлахгүй.

Гаралт

Бүх тэсрэх бөмбөгийг устгахын тулд хамгийн багадаа хэдэн үйлдэл хийхийг илтгэх $k$тоог хэвлэнэ үү. Дараагийн мөрүүдэд $k$ үйлдлүүдээ тодорхойлж хэвлэнэ үү. Олон шийд байвал аль дуртайгаа хэвлэхэд хангалттай. $k\le 10^6$ байх оролт өгөгдөнө.

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

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

Оролт
2
1 1
-1 -1
Гаралт
12
1 1 R
1 1 U
2
1 1 L
1 1 D
3
1 1 L
1 1 D
2
1 1 R
1 1 U
3
Оролт
3
5 0
0 5
1 0
Гаралт
12
1 1 R
2
1 1 L
3
1 5 R
2
1 5 L
3
1 5 U
2
1 5 D
3
Сэтгэгдлүүдийг ачааллаж байна...