Числа

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

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

Вхідні дані

Числа N, K, P, Q (0 ≤ N ≤ 10^7, 1 ≤ K ≤ 24, 1 ≤ P, Q ≤ 10^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. Але вони нулі.) Першою потрібно виводити відповідь для молодшого розряду.

Приклади