B. Сонгон шалгаруулах сорил

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

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

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

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

Тун удахгүй Бэрландад сурагчдын Програмчлалын Багийн Олимпиад болох аж. Бэрландын $m$ ширхэг аймаг бүрээс хоёр гишүүнтэй нэг баг илгээхийг урьжээ. Багуудаа бүрдүүлэх сонгон шалгаруулах сорилд $n$ сурагч оролцсон ба $m$ муж тус бүрээс ядаж хоёр сурагч хамрагдсан байв. Оролцогчдын энэ сонгон шалгаруулах тэмцээний оноо $0$-ээс $800$ хүртэл тоогоор үнэлэгджээ.

Аймаг бүрийн бүр сонгон шалгаруулах тэмцээнээс хоёр хоёр шилдэг оролцогчоороо багаа бүрдүүлнэ. Хэрвээ шилдэг багаа хоёр янзаар бүрдүүлэх боломжтой байвал нэмэлт сорил зохион байгуулах шаардлагатай.

Сонгон шалгаруулах тэмцээнд аль аймаг ямар оролцогчид ямар оноо авсан үр дүн мэдэгдэж буй бол аймаг бүрийн хувьд тэднийг төлөөлөх хоёр оролцогчийг нь шалгаруул, эсвэл нэмэлт сорил шаардлагатай эсэхийг тогтооно уу.

Оролт

Эхний мөрөнд $n$ and $m$ ($2 \le n \le 100 000$, $1 \le m \le 10 000$, $n \ge 2m$) хоёр тоо өгөгдөнө, харгалзан нийт оролцогчдын тоо болон аймгуудын тоог илэрхийлнэ.

Дараагийн $n$ мөр оролцогчдын тодорхойлолтыг дараах байдлаар өгнө: Нэр (том жижиг Англи үсгээс бүрдэх 1-10 урттай стринг), аймгийн дугаар ($1$-ээс $m$-н хооронд бүхэл тоо), оролцогчийн оноо ($0$-ээс $800$ хооронд бүхэл тоо).

Оролцогчдын нэр бүгд ялгаатай ба $m$ мужаас тус бүр дор хаяж хоёр хоёр сурагч оролцсон.

Гаралт

Дараах байдлаар $m$ мөр хэвлэнэ: $i$ дэх мөрөнд $i$ дэх аймгийн хоёр оролцогчийн нэрийг дурын эрэмбээр гаргах ба хэрэв нэмэлт шалгаруулалт шаардлагатай бол "?" хэвлэнэ үү.

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

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

Оролт
5 2
Ivanov 1 763
Andreev 2 800
Petrov 1 595
Sidorov 1 790
Semenov 2 503
Гаралт
Sidorov Ivanov
Andreev Semenov
Оролт
5 2
Ivanov 1 800
Andreev 2 763
Petrov 1 800
Sidorov 1 800
Semenov 2 503
Гаралт
?
Andreev Semenov

Тэмдэглэл

Эхний жишээнд аймгуудыг төлөөлөх багууд цор ганц утгаар тодорхойлогдоно.

Хоёр дах жишээнд $2$ дах аймгийн баг ганц л байна. Харин $1$-р аймагт гурван боломжит сонголт бий: "Petrov"-"Sidorov", "Ivanov"-"Sidorov", "Ivanov" -"Petrov", иймд цор ганц аргаар тодорхойлох боломжгүй.

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