C. Нууц баримт

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

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

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

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

Дэлхийн хамгийн том нууц баримт $n$ ширхэг үгнээс бүтдэг бөгөөд эдгээр үгнүүдийг $1$-ээс $n$ хүртэл тоогоор дугаарлажээ. Нууц баримт дахь үгнүүдийг $k$ ширхэг нууц хадгалагчид хуваан оноожээ. $i$ дэхь ($1$-ээс эхлэн дугаарлагдана) нууц хадгалагч нууц баримтын $U_{i} = (u_{i, 1}, u_{i, 2}, ..., u_{i, |U_{i}|})$ үгнүүдийн цуглуулгыг хадгалдаг. Нууц баримтын үгнүүд нь өсөх дарааллаар дугаарлагдсан.

Хэрвээ дараах нөхцөлийг хангаж байвал нууц баримтыг задраагүй бөгөөд бүрэн бүтэн хадгалагдаж байна гэж тооцно:

  • Аль ч $i, j$ ($1 ≤ i < j ≤ k$) хоёр нууц хадгалагчийн $U_{i}$, $U_{j}$ үгний цуглуулгын үгнүүд хоорондоо давхцахгүй байвал;
  • Нууц хадгалагчдын цуглуулгууд $U_{1}, U_{2}, ..., U_{k}$ нийлээд нууц $(1, 2, ..., n)$-ыг бүтээж чадаж байвал;
  • Аль ч $U_{i}$ цуглуулгын үгнүүдийн дугаарууд $u_{i, 1}, u_{i, 2}, ..., u_{i, |U_{i}|}$ нь хоорондоо арифметик прогресс үүсгэхгүй байвал нууц задраагүй байна гэж тооцно ($|U_{i}| ≥ 3$ нөхцөл хангагдах ёстой).

Хэрвээ бүх $i$ ($1 ≤ i < s$)-ын хувьд $u_{i} + d = u_{i + 1}$ тэгшитгэл биелэж байхаар $d$ тоо олдож байвал $(u_{1}, u_{2}, ..., u_{s})$ элемэнтүүд нь хоорондоо арифметик прогресс үүсгэж байна гэсэн үг. Жишээ нь: $(5)$, $(1, 10)$, $(1, 5, 9)$ эдгээр нь арифметик прогресс үүсгэж байгаа бол, харин $(1, 2, 4)$, $(3, 6, 8)$ нь үүсгэхгүй байна.

Таны даалгавар бол нууц баримт бүрэн хадгалагдаж байхаар нууц баримтын элемэнт болгоныг $U_{1}, U_{2}, ..., U_{k}$ нууц хадгалагчдад хуваах юм.

Оролт

Нууц баримтын нийт үгийн тоо болон нийт нууц хадгалагчидын тоо болох $2$ ширхэг бүхэл тоо $n$, $k$ ($2 ≤ k ≤ n ≤ 10^{6}$) өгөгдөнө. Тоонууд хоорондоо зайгаар тусгаарлагдана.

Гаралт

Хэрвээ нууцыг аюулгүй хадгалах боломжгүй бол "-1" гэж хэвлэнэ үү. Боломжтой бол нууц баримтын $i$ дэхь үгийг хэд дэхь нууц хадгалагч хадгалж байгааг илэрхийлж буй $n$ ширхэг бүхэл тоо хэвлэнэ үү.

Хэрэв нэгээс олон хариулт олдвол аль нэгийг хэвлэнэ үү.

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

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

Оролт
11 3
Гаралт
3 1 2 1 1 2 3 2 2 3 1
Оролт
5 2
Гаралт
-1
Сэтгэгдлүүдийг ачааллаж байна...