Little C очень любит число «3». Он любит все, что с ним связано.
В данный момент его заинтересовала следующая задача:
Даны два массива из \(2^n\) целых чисел: \(a_0,a_1,...,a_{2^n-1}\) и \(b_0,b_1,...,b_{2^n-1}\).
Задача состоит в том, чтобы для каждого \(i (0 \leq i \leq 2^n-1)\), вычислить \(c_i=\sum a_j \cdot b_k\) (\(j|k=i\) и \(j\&k=0\), где "\(|\)" обозначает побитовую операцию ИЛИ и "\(\&\)" обозначает побитовую операцию И).
Это замечательно, что можно доказать, что существует ровно \(3^n\) троек \((i,j,k)\), для которых \(j|k=i\), \(j\&k=0\) и \(0 \leq i,j,k \leq 2^n-1\). Поэтому Little C хочет решить эту отличную задачу (потому что она тесно связана с числом \(3\)) .
Помогите ему вычислить все \(c_i\). Little C очень любит число \(3\), поэтому он лишь хочет знать все \(c_i \& 3\).
Выходные данные
Выведите одну строку, которая содержит \(2^n\) целых чисел, принадлежащих \([0,3]\) без пробелов — \(i\)-е из них должно обозначать \(c_{i-1}\&3\). (Очевидно, что \(c_{i}\&3\) принадлежит \([0,3]\)).