eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Числа

Числа

Ліміт часу 3 секунди
Ліміт використання пам'яті 256 MiB

Задано N цілих невід'ємних чисел. Ми розглядаємо їх попарні суми (усі N^2 сум).

Для кожного дійкового розряду від 0 до K потрібно порахувати, скільки разів у цих сумах у ньому стояла одиниця.

Вхідні дані

Числа N, K, P, Q (0N10^7, 1K24, 1P, Q10^9+7, P та Q - прості). Послідовність чисел a_0, ...,a_{N-1} генерується так. a_0 = 1, a_{i+1} = (a_i·P+Q) mod 2^K.

Вихідні дані

У першому рядку виведіть K+1 ціле число - кількості одиничок у розрядах (Можно було б вивести інші кількості, не лише перші K+1. Але вони нулі.) Першою потрібно виводити відповідь для молодшого розряду.

Приклад

Вхідні дані #1
3 10 3 5
Вихідні дані #1
4 4 4 5 4 3 0 0 0 0 0
Автор Сергій Копеліович