Задача D. Числа ≡

Условие

Даны N целых неотрицательных чисел. Мы рассматриваем их попарные суммы (все N² сумм). Для каждого двоичного разряда от 0 до K нужно посчитать, сколько раз в этих суммах в нем стояла единица.

Решение, работающее для K ≤ 20 и N ≤ 10⁶, будет набирать не менее 70 баллов.

Формат входного файла

Числа N, K, P, Q. Последовательность чисел a₀, ... , a_N − 1 генерируется так. a₀ = 1, a_i + 1 = (a_i ⋅ P + Q) mod 2^K

Формат выходного файла

В первой строке выведите K + 1 целое число — количества единичек в разрядах (Можно было бы вывести остальные количества, не только первые K + 1. Но они нули.) Первым выводить нужно ответ для младшего разряда.

Ограничения

0 ≤ N ≤ 10⁷;

1 ≤ K ≤ 24;

1 ≤ P, Q ≤ 10⁹ + 7;

P и Q — простые;

Примеры тестов

3 10 3 5

4 4 4 5 4 3 0 0 0 0 0

10 3 3 5

50 25 48 16

100 10 17 239

5000 5000 5002 5002 4998 5014 4989 5029 4985 5015 4188