АЛГОРИТМЫН ЦАГААН ТОЛГОЙ

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

N тулаанч байх бөгөөд тулаанч бүр өөрийн хүчтэй. N тулаанчид k багт хуваагдах бөгөөд 1 тулаанч 1 багт хамаарна. Тулаан бүрт Great Masters of Meereen 2 баг сонгож авна, сонгогдсон 2 баг х,у нь үхтлээ тулалдах ёстой. Багууд ээлжлэн бие бие рүүгээ довтолно, эхний довтолгоог үргэлж х баг хийнэ. Аль нэг багийн бүх тулаанч амь эрсдэхэд тулаан дуусна.

Багууд довтлохдоо хамгийн сайнаараа довтолно. Довтолгоо бүр дараахь байдлаар явагдана:

1. Довтлогч тал багаасаа S хүчтэй тулаанчийг сонгоно.

2. Сонгогдсон тулаанч эсрэг багаасаа хамгийн ихдээ S  тулаанч сонгож бүгдийг нь хорооно.

Great Masters өөрсдийн хайртай дайчдаа тулаанд амь эрсдээсэй гэж хүсэхгүй байгаа тул дайчдыг 2 багт хуваахдаа, боломжит хуваалт бүрт аль тал нь ялахыг мэдэхийг хүсэж байгаа. Үүний тулд чамайг 2 төрлийн хүсэлт гүйцэтгэхийг хүсэлт байгаа:

1. 1 p x гэвэл p хүчтэй тулаанчийг x багт нэмнэ. Нэмэгдэж байгаа тулаанчийн хүч нь тухайн багт байгаа аль ч тулаанчаас багагүй байна гэдэгт баталгаа өгч байгаа. 

2. 2 х у гэвэл х, у 2 багийн хоорондын тулаанд одоогийн байдлаар аль баг нь ялахыг хэвлэнэ. (x баг үргэлж эхэлж довтолно гэдгийг санаарай.) x у 2 тэнцүү биш гэдэгт баталгаа өгч байгаа.

Багуудын анхны хуваалт болон хүсэлтүүд өгөгдсөн бол хүсэлт бүрийг боловсруулна уу. Ингэснээр Greate Masters дараагийн тэмцээнийг төлөвлөх боломжтой болно.

Анхаар: Чи 2 баг тулалдсан тохиолдолд аль нь ялахыг тодорхойлж байгаа. Ө.х тухайн тэмцээнд аль ч тулаанч жинхнээсээ амь эрсдэхгүй тул багт хувааарлагдсаныхаа дараа тулаанч ирээдүйн бүх боломжит тэмцэээнд оролцох боломтой.

Оролтын формат

Эхний мөрөнд зайгаар тусгаарлагдсан 3 тоо байна. n - нийт тулаанчдын тоо, k - багуудын тоо, q – хүсэлтүүдийн тоо.

Дараагийн n мөрөнд зайгаар тусгаарлагдсан 2 бүхэл тоо байх бөгөөд энэ нь  i дугаар тулаанчийн хүч s_i болон багийн дугаар t_i

Дараагийн q мөрөнд зайгаар тусгаарлагдсан хүсэлт байна. Эдгээр хүсэлт нь бодлогонд тодорхойлоглдсон 2 хэлбэрт байна  (ө.х 1 p x эсвэл 2 x y).

Хязгаарлалтууд

1 <= n, q <= 2 * 10^5

2 <= k <= 2 * 10^5

1 <= x, y, t_i <= k

1 <= s_i, p <= 2 * 10^5

 Оноолт таарсан 2 баг тус бүр үргэлж хамгийн багадаа 1 тулаанчтай байна.

Оноо

Энэ даалгавар 2-тын оноотой. Энэ нь хэрвээ бодолт чинь бүх тестүүдийг давбал бүтэн оноо авна үгүй бол 0 оноо авна.

Гаралт

2 дугаар төрлийн хүсэлт бүрийн дараа ялагч багийн дугаарыг хэвлэнэ. Жишээ нь хэрвээ х=1, у=2 багуудын хооронд тулаан болоод  x ялах бол 1 гэж хэвлэнэ.

Жишээ Оролт

7 2 6

1 1

2 1

1 1

1 2

1 2

1 2

2 2

2 1 2

2 2 1

1 2 1

1 2 1

2 1 2

2 2 1

Жишээ гаралт

 1

2

1

1

Тайлбар

1-р баг дараахь хүчтэй 3 тулаанчтай: S₁ = {1, 1, 2}

2-р баг дараахи хүчтэй 4 тулаанчтай: S₂ ={1, 1, 1, 2}

Эхний хүсэлт x = 1, y = 2 багуудын хооронд оноолт тааруулсан.

Энэ үед дараахь байдлаар тоглолт явагдана:

1. x = 1 баг довтолно. 2 хүчтэй тулаанч 1 хүчтэй 1 тулаанч, 2 хүчтэй 1 тулаанчийг хөнөөж болно.

Ингэснээр S₁=  {1, 1, 2},  S₂={1, 1} болно.

2. x = 2 баг довтолно. 1 хүчтэй тулаанч 2 хүчтэй тулаанчийг хөнөөж болно.

Ингэснээр S₁= {1, 1},  S₂={1, 1} болно.

3. x = 1 баг довтолно. 1 хүчтэй тулаанч 1 хүчтэй 1 тулаанчийг хөнөөж болно.

Ингэснээр S₁= {1, 1},  S₂={1} болно.

4. x = 2 баг довтолно. 1 хүчтэй тулаанч 1 хүчтэй 1 тулаанчийг хөнөөж болно.

Ингэснээр S₁ = {1},  S₂ ={1} болно.

5. x = 1 баг довтолно. 1 хүчтэй тулаанч 1 хүчтэй 1 тулаанчийг хөнөөж болно.

Ингэснээр S₁ =  {1},  S₂ = {} болно.

Сүүлийн довтолгооны дараа 2-р багт тулаанч үлдэхгүй.

Иймээс 1-р баг тулаанд ялах тул гаралтанд эхний 2 1 2 хүсэлтийн хариу нь 1 гэж хэвлэсэн байна.

Орчуулсан : Б.Даваабаяр АНУ