İnci və çevirici

Perllər — insanların günahı üzündən demək olar ki, məhv olmuş və qalan nümayəndələri kosmosda sürüklənən sülhsevər və ilkin bir irqdir. Alfa'ya gəldikdən sonra perllər Valerian və Lorelin ilə tanış oldular və nəhayət, perl konverterinə sahib oldular.

Konverter — $k$ fərqli rəngdə perl istehsal edən şirin bir heyvandır. Kosmik gəminin mühərrikini işə salmaq üçün perllərə $k$ fərqli rəngdə perl dəsti lazımdır. Konverter hər saniyədə bir perl istehsal edir. Mühərrikin səmərəli işləməsi üçün hər dəstdə hər hansı iki perl arasında yaranma vaxtı fərqi $m$ saniyədən çox olmamalıdır. Hər perl yalnız bir dəstəyə aid ola bilər.

Konverter $n$ perl istehsal etdi və yoruldu. Perllərə mövcud perl ilə toplaya biləcəkləri maksimum dəst sayını öyrənməyə kömək edin.

Giriş verilənləri

Birinci sətirdə üç tam ədəd $n$, $m$, $k$ yazılmışdır — konverter tərəfindən istehsal olunan perl sayı, bir dəstdə hər hansı iki perl arasında yaranma vaxtı maksimum fərqi və fərqli rəngdə perl sayı ($1\le m\le n\le 10^5$, $1\le k\le 10^5$).

Növbəti sətirdə $n$ tam ədəd $a_i$ var — yaranan $i$-ci perlin rəngi ($1\le a_i\le k$).

Çıxış verilənləri

Birinci sətirdə bir tam ədəd $x$ yazın — mövcud perl ilə toplaya biləcəkləri maksimum dəst sayısı.

Növbəti $x$ sətirdə hər biri $k$ tam ədəd $d_{ij}$ yazın — $i$-ci dəstəyə daxil olan perl nömrələri ($1\le d_{ij}\le n$).

Əgər bir neçə düzgün cavab varsa, onlardan birini verin.

Nümunələr

Qiymətləndirmə

Bu məsələ beş alt məsələdən ibarətdir. Alt məsələlər üçün aşağıda göstərilən əlavə məhdudiyyətlər yerinə yetirilir. Alt məsələdən xal qazanmaq üçün həmin alt məsələnin bütün testlərini və həmçinin bütün zəruri alt məsələlərin testlərini keçmək lazımdır. Zəruri alt məsələlərin nömrələri də cədvəldə göstərilmişdir.

1. ($15$ xal): $n=m$, $n\le 1000$;

2. ($10$ xal): $k=2$, $n\le 1000$;

3. ($15$ xal): $k\le 10$, $n\le 1000$;

4. ($30$ xal): $n\le 1000$;

5. ($30$ xal): tam məhdudiyyətlər.