C. Валера ба хоолой

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

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

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

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

Валерад $n$ мөртэй, $m$ баганатай тэгш өнцөгт хүснэгт байгаа. Валера хүснэгтийн мөрүүдийг нэгээс эхлүүлэн дээрээс доош дугаарласан, харин багануудыг нэгээс эхлүүлэн зүүнээс баруун тийш дугаарласан. Хүснэгтийн нүдийг $x$ мөр ба $y$ баганы огтлолцол дээрх хос бүхэл $(x, y)$ тоонуудаар илэрхийлж чадна.

Валера тэгш өнцөгт хүснэгтэндээ яг $k$ хоолой байрлуулахыг хүссэн. Хоолой нь хүснэгтийн мөрүүдийн дараалал $(x_{1}, y_{1})$, $(x_{2}, y_{2})$, $...$, $(x_{r}, y_{r})$ байна. Энэ нь:

  • $r ≥ 2$;
  • Ямар нэгэн бүхэл тоо $i$ $(1 ≤ i ≤ r - 1)$-ийн хувьд дараах тэгшитгэлийг хангана. $|x_{i} - x_{i + 1}| + |y_{i} - y_{i + 1}| = 1$;
  • Хүснэгтийн нүд бүр нь хоолойд хамаарагдаж яг нэг удаа дараалал үүсгэх ёстой.

Валера дараах нөхцлийг хангасан сонирхолтой хэлбэрээр зохион байгуулагдсан хоолой бодож байгаа:

  • Ижил нүднүүдтэй хос хоолой байж болохгүй;
  • Хоолой нь хүснэгтийн нүд бүрийг агуулна.

Валерад тэгш өнцөгт хүснэгтэнд $k$ хоолойг сонирхолтой хэлбэрээр зохион байгуулахад туслана уу.

Оролт

Эхний мөрөнд зайгаар тусгаарлагдсан гурван бүхэл $n, m, k$ ($2 ≤ n, m ≤ 300$; $2 ≤ 2k ≤ n*m$) тоонууд агуулагдана. Эдгээр нь харгалзан мөрийн тоо, баганын тоо, хоолойны тоо юм.

Гаралт

$k$ мөр хэвлэнэ. $i$-р мөрөнд $i$-р хоолойг илэрхийлэх: эхлээд бүхэл $r_{i}$ (хоолойн нүднүүдийн тоо) тоо, дараа нь $2r_{i}$ ширхэг бүхэл $x_{i1}, y_{i1}, x_{i2}, y_{i2}, ..., x_{ir_{i}}, y_{ir_{i}}$ (хүснэгтийн нүднүүдийн дараалал) тоонуудыг хэвлэнэ.

Хэрвээ олон хариулт байвал тэдгээрийн аль нэгийг нь хэвлэнэ. Оролтын өгөгдлөөс хамгийн багадаа нэг шийдэл олдох нь баталгаатай.

Орчуулсан: Даариймаа

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

Оролт
3 3 3
Гаралт
3 1 1 1 2 1 3
3 2 1 2 2 2 3
3 3 1 3 2 3 3
Оролт
2 3 1
Гаралт
6 1 1 1 2 1 3 2 3 2 2 2 1

Тэмдэглэл

Эхний жишээний зураг:

Хоёр дахь жишээний зураг:

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