Бір отбасыда туған күндерді тортпен және \(0\)-ден \(9\)-ға дейінгі цифр түріндегі шамдармен атап өтеді. Шамдар жағылмайды — олар тек жасты көрсету үшін тортқа қойылады. Осыған байланысты шамдарды әртүрлі жылдарда және әртүрлі адамдар үшін бірнеше рет қолдануға болады.

Әрбір күнде тек бір адамның туған күні болады деп есептеледі.

Отбасы алдағы \(k\) жылда барлық туған күндерді атап өту үшін жеткілікті ең аз шам санын алдын ала сатып алғысы келеді.

Әрбір \(n\) отбасы мүшесінің қазіргі жасы белгілі. Әр жыл сайын әр адам туған күнін атап өтеді, және әр тортқа оның жасы шам-цифрлар арқылы қойылады.

Шамдарды қайта пайдалануға болады, бірақ бір тортта әр цифр жеке шаммен көрсетілуі тиіс. Мысалы, \(22\) жасын көрсету үшін \(2\) цифры бар екі шам қажет.

«Алдағы \(k\) жыл» дегенде әр адам үшін жас шамалары \(a_i, a_i+1, \ldots, a_i+k-1\) болып есептеледі, яғни ағымдағы жастан бастап.

Барлық отбасы мүшелерінің туған күндерін алдағы \(k\) жылда атап өту үшін әр цифрдан (\(0\)-ден \(9\)-ға дейін) қанша шам сатып алу керектігін анықтаңыз.

Енгізу

Бірінші жолда екі бүтін сан \(n\), \(k\) (\(1 \le n \le 10^5\), \(1 \le k \le 10^6\)) беріледі — отбасы мүшелерінің саны және қанша жыл алға есептелетіні. Екінші жолда \(n\) бүтін сан \(a_1, a_2, \ldots, a_n\) (\(0 \le a_i \le 10^6\)) — отбасы мүшелерінің қазіргі жастары беріледі.

Шығару

\(0\)-ден \(9\)-ға дейінгі цифрларға арналған шамдардың ең аз санын көрсететін \(10\) бүтін санын шығарыңыз. Сандар бос орын арқылы бөлініп, \(0\)-ден \(9\) ретімен шығарылуы тиіс.

Мысалдар

Енгізу 1

3 3
12 12 15

Жауап 1

0 1 1 1 1 1 1 1 0 0

Енгізу 2

7 4
78 74 49 44 20 15 9

Жауап 2

1 2 2 1 2 1 1 2 1 1

Енгізу 3

2 1
90 5

Жауап 3

1 0 0 0 0 1 0 0 0 1

Енгізу 4

7 1
10 5 1 6 2 0 3

Жауап 4

1 1 1 1 0 1 1 0 0 0

Ескертпелер

Екінші мысалды қарастырайық. Барлығы \(n=7\) адам, алдағы \(k=4\) жыл.

Қазіргі жастары: \(78, 74, 49, 44, 20, 15, 9\). Әр жыл сайын жас \(1\)-ге артады.

Бірінші отбасы мүшесі: \(78 \to 78, 79, 80, 81\)

Қажетті шамдар: 0,1,7,8,9

Сатып алу керек шам нөмірлері: 0,1,7,8,9

Екінші отбасы мүшесі: \(74 \to 74, 75, 76, 77\)

Қажетті шамдар: 4,5,6,7,7

Сатып алу керек шам нөмірлері: 4,5,6,7

Қалған шамдар сатып алынған.

Үшінші отбасы мүшесі: \(49 \to 49, 50, 51, 52\)

Қажетті шамдар: 0,1,2,4,5,9

Сатып алу керек шам нөмірі: 2

Қалған шамдар сатып алынған.

Төртінші отбасы мүшесі: \(44 \to 44, 45, 46, 47\)

Қажетті шамдар: 4,4,5,6,7

Сатып алу керек шам нөмірі: 4

Қалған шамдар сатып алынған.

Бесінші отбасы мүшесі: \(20 \to 20, 21, 22, 23\)

Қажетті шамдар: 0,1,2,2,3

Сатып алу керек шам нөмірі: 2

Қалған шамдар сатып алынған.

Алтыншы отбасы мүшесі: \(15 \to 15, 16, 17, 18\)

Қажетті шамдар: 1,5,6,7,8

Жетпейтін шамдар жоқ.

Жетінші отбасы мүшесі: \(9 \to 9, 10, 11, 12\)

Қажетті шамдар: 0,1,1,2,9

Сатып алу керек шам нөмірі: 1

Қалған шамдар сатып алынған.

Қорытынды:

«0» — \(1\)

«1» — \(2\)

«2» — \(2\)

«3» — \(1\)

«4» — \(2\)

«5» — \(1\)

«6» — \(1\)

«7» — \(2\)

«8» — \(1\)

«9» — \(1\)

Бұл мысалдағы жауаппен сәйкес келеді.