Rəqəmlər

Verilmiş N qeyri-mənfi tam ədədlərdən ibarət bir sıra var. Biz bu ədədlərin cüt-cüt cəmlərini nəzərdən keçiririk (ümumilikdə N^2 cəm).

Məqsədimiz hər bir rəqəm dərəcəsi üçün 0-dan K-ya qədər bu cəmlərdə həmin dərəcədə birlərin neçə dəfə olduğunu saymaqdır.

Giriş verilənləri

Ədədlər N, K, P, Q verilmişdir (0 ≤ N ≤ 10^7, 1 ≤ K ≤ 24, 1 ≤ P, Q ≤ 10^9+7, P və Q sadə ədədlərdir). Ədədlər ardıcıllığı a_0, ...,a_{N-1} aşağıdakı qayda ilə yaradılır: a_0 = 1, a_{i+1} = (a_i·P+Q) mod 2^K.

Çıxış verilənləri

Birinci sətirdə K+1 tam ədəd çıxarın - hər bir dərəcədəki birlərin sayını. Əvvəlcə ən kiçik dərəcə üçün cavabı çıxarın. (Başqa dərəcələr üçün də cavablar çıxarmaq olardı, lakin onlar sıfırdır.)

Nümunələr