| Codeforces Round 259 (Div. 1) |
|---|
| Закончено |
Элементы гармонии — это шесть артефактов, обладающих сверхъестественной силой. Каждый из них является некоторым аспектом гармонии. Вполне вероятно, что элементы гармонии — это самые могущественные силы в Equestria. Каждый элемент гармонии представляет из себя полный граф с n вершинами, пронумерованными от 0 до n - 1, где n — степень двойки, равная 2m.
Энергия в элементах гармонии находится в постоянном движении. Согласно древней книге, энергия вершины u в момент времени i (ei[u]) равна:
Здесь b[] — это коэффициент трансформации, массив состоящий из m + 1 целых чисел. Функция f(u, v) обозначает количество единичных битов в битовом представлении числа (u xor v).
Вам задан коэффициент трансформации элемента гармонии, а также энергия каждой вершины в момент времени 0 (e0[i]). Помогите Twilight Sparkle посчитать энергию каждой вершины в момент t (et[i]). Так как числа могут получиться довольно большими, выведите их по модулю p.
В первой строке записаны три целых числа: m, t и p (1 ≤ m ≤ 20; 0 ≤ t ≤ 1018; 2 ≤ p ≤ 109). Следующая строка содержит n (n = 2m) целых чисел e0[i] (1 ≤ e0[i] ≤ 109; 0 ≤ i < n). В следующей строке записаны m + 1 целых чисел b[i] (0 ≤ b[i] ≤ 109; 0 ≤ i ≤ m).
Выведите n строк, в i-й строке выведите et[i] по модулю p.
2 2 10000
4 1 2 3
0 1 0
14
6
6
14
