D. Максим ба өсч буй дэд дараалал

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

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

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

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

Максим өсч буй дараалалд их дуртай. Тэрээр өгөгдсөн $a$ дарааллын хамгийн урт дэд дарааллын урт хэд вэ? гэдгийг олохыг хүсч байлаа.

$a$ дарааллыг дараах байдлаар өгчээ:

  • Дарааллын урт нь $n × t$-тэй тэнцүү;
  • $a_i = b_{((i-1)\ mod\ n) + 1}$ $(1 ≤ i ≤ n \cdot t)$. Энд $(x\ mod\ y)$ үйлдэл нь $x$ тоог $y$ тоонд хуваагаад үлдэгдлийг нь авах юм.

Хэрвээ $a_{i_{j}}  =  s_{j}$ байх $i_{1}, i_{2}, ..., i_{r}(1  ≤  i_{1}  <  i_{2}  < ...   <  i_{r}  ≤  n)$ өсч буй индекстэй дараалал байх юм бол $r$ урттай $s_{1},  s_{2},  ...,  s_{r}$ дараалал нь $a_{1},  a_{2},  ...,  a_{n}$ дарааллын дэд дараалал болох юм. Өөрөөр хэлвэл дарааллаас элемэнтүүдийг хасах буюу арилган дэд жагсаалт үүсгэнэ.

Хэрвээ $s_{1},  s_{2},  ...,  s_{r}$ жагсаалт $s_{1} < s_{2} <  ... <  s_{r}$ нөхцөлийг хангаж байвал энэ жагсаалтыг өсч буй жагсаалт гэнэ.

Максимд нийт $k$ ширхэг $a$ жагсаалт байна. Жагсаалт болгонд хамгийн урт өсч буй жагсаалтын уртыг Максимд олж өгөөрэй.

Оролт

Эхний мөрөнд 4-н ширхэг бүхэл тоо $k$, $n$, $maxb$, $t$ $(1 ≤ k ≤ 10; 1 ≤ n, maxb ≤ 10^{5}; 1 ≤ t ≤ 10^{9}; n × maxb ≤ 2*10^{7})$ өгөгдөнө. Дараагийн $k$ ширхэг мөрөнд $n$ ширхэг бүхэл тоо $b_{1}, b_{2}, ..., b_{n}$ $(1 ≤ b_{i} ≤ maxb)$ өгөгдөнө.

$a$ жагсаалт болгонд $n$, $maxb$, $t$-ын утгууд адил. Зөвхөн $b$ нь хоорондоо ялгаатай.

Бүх нэг мөрөнд байгаа тоонууд хоорондоо зайгаар тусгаарлагдана.

Гаралт

$k$ ширхэг мөрөнд мөр болгонд нэг ширхэг $a$ жагсаалтын хамгийн урт өсч буй дарааллын уртыг хэвлэнэ үү. $a$ жагсаалтуудын оролтонд өгсөн дарааллаар хариуг гаралтанд хэвлэнэ үү.

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

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

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