D. Нийтийн сүлжээ

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

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

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

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

Поликарпус нэгэн алдартай нийтийн сүлжээнд дадлага хийхээр болжээ. Түүний даалгавар нь тухайн өдөр нийтийн сүлжээнд хандсан онцгой хэрэглэгчдийн тоог тоолох. Поликарпус өдрийн цагаар хандсан бүх үйлчлүүлэгчдийн мэдээллээр хангагдсан. Хандалт болгоны хандсан цагийг бид мэднэ... өөр юу ч мэдэхгүй, учир нь Поликарпус хэрэглэгчдийн ID-уудыг санаандгүй устгачихжээ. Тиймээс одоо аль ч 2 хандалтыг нэг хүн хийсэн үү эсвэл ялгаатай хүн хийсэн үү гэдгийг мэдэх боломжгүй болсон.

Гэхдээ бас нэгэн зүйл мэдэгдэж байгаа, учир нь тэр өдрийн бүртгэл тэмдэглэгдсэн байсан -- хамгийн ихдээ $M$ ширхэг ялгаатай хэрэглэгчид зэрэг холбогдсон. Үүнээс гадна, хэрвээ хэрэглэгч $s$ секундэнд хандсан бол тэрээр үүний дараа $T$ секундын турш холбогдсон байсан. Өөрөөр хэлбэр тухайн хэрэглэгч $s$, $s + 1$, $s + 2$, ..., $s + T - 1$ секундуудэд холбогдсон байсан гэсэн үг. Тиймээс хэрэглэгчийн холбогдсон байсан хугацааг $[s, s + T - 1]$ интервалаар илэрхийлж болно.

Дараах нэмэлт мэдээллүүдийг ашиглан Поликарпус хандалт болгоны хэрэглэгчийн ID-г олохыг хүсч байгаа:

  • холбогдсон ялгаатай хэрэглэгчдийн тоо аль ч үед $M$-ийг хэтрэхгүй,
  • аль нэг мөчид холбогдсон ялгаатай хэрэглэгчдийн тоо $M$-д хүрсэн,
  • нийт ялгаатай хэрэглэгчдийн тоо байж болох хамгийн их байна.

Поликарпусд даалгавраа давахад тусална уу.

Оролт

Эхний мөрөнд 3-н бүхэл тоонууд $n$, $M$, $T$ ($1 ≤ n, M ≤ 20 000$, $1 ≤ T ≤ 86400$) өгөгдөнө. Эдгээр нь нийт хандсан тоо, холбогдсон хэрэглэгчдийн хамгийн их тоо, хандалт эхэлснээс хойш хэр удаан хэрэглэгч холбогдсон байх хугацаа. Дараагийн $n$ ширхэг мөрөнд хандалтын эхлэх хугацаанууд "hh:mm:ss" байдлаар өгөгдөнө. Энд hh нь цаг, mm нь минут, ss нь секунд болно. Хандалтууд өгсөх дарааллаар өгөгдөнө. Энд зарим нь давхцаж болно. Энд бүх хандалтын эхлэх болон дуусах хугацаа 24-н цаг дотор байна (00:00:00-ээс 23:59:59-ны хооронд).

Гаралт

Эхний мөрөнд байж болох хамгийн их ялгаатай хэрэглэгчдийн тоо болох $R$ тоог хэвлэнэ үү. Дараагийн $n$ ширхэг мөрөнд оролтонд өгөгдсөн дарааллаар хэрэглэгчдийн ID-уудыг хэвлэнэ үү. Хэрэглэгчийн ID нь $1$-ээс $R$-ийн хооронд бүхэл тоо байна. Адилхан хэрэглэгч хандсан хандалт бол энэ 2 хандалтын ID нь адилхан байна. Ялгаатай хэрэглэгчдийн хандсан хандалт бол энэ 2 хандалтын ID нь ялгаатай байна. Хэрвээ олон хариулт олдвол аль нэгийг нь хэвлэнэ үү. Хэрвээ хариулт олдохгүй бол "No solution" гэж хэвлэнэ үү.

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

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

Оролт
4 2 10
17:05:53
17:05:58
17:06:01
22:39:47
Гаралт
3
1
2
2
3
Оролт
1 2 86400
00:00:00
Гаралт
No solution

Тэмдэглэл

Эхний жишээ: эхний хандалтыг хийсэн хэрэглэгч 17:05:53-ээс 17:06:02-ны хооронд холбогдсон, 2 дахь хандалтыг хийсэн хэрэглэгч 17:05:58-ээс 17:06:07-ны хооронд холбогдсон, 3 дахь хандалтыг хийсэн хэрэглэгч 17:06:01-ээс 17:06:10-ны хооронд холбогдсон. Тиймээс эдгээр ID-нууд нь 3-н ялгаатай хэрэглэгч байх боломжгүй учир нь жишээ нь эдгээр хэрэглэгчид нь 17:06:01 мөчид зэрэг холбогдсон байсан. Энэ нь боломжгүй учир нь $M = 2$. Эндээс эдгээр хандалтуудын 2-ыг нь нэг хэрэглэгч хандсан байна. Боломжит хариултуудын нэгийг жишээнд харуулсан байна. Үүний тулд хэрэглэгч $1$ 17:05:53-ээс 17:06:02-ны хооронд холбогдсон, хэрэглэгч $2$ 17:05:58 to 17:06:10 хооронд холбогдсон (энд тэрээр 2 дахь болон 3 дахь хандалтыг хийсэн), хэрэглэгч $3$ 22:39:47 to 22:39:56-ны хооронд холбогдсон.

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

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