% Автор: Сергей Копелиович
% Источник: чемпионат СПБГУ, осень 2014

%\gdef\thisproblemauthor{Сергей Копелиович}
%\gdef\thisproblemdeveloper{Сергей Копелиович}
\begin{problem}{Свёртка}
{convolution.in}{convolution.out}
{2 секунда}{256 мебибайт}{}

%\divspecific{%
\gdef\LIMIT{16}
%}{%
%\gdef\LIMIT{10}
%}%

Рассмотрим все подмножества множества $U = \{0, 1, 2, \dots, n-1\}$.
Каждому подмножеству $A = \{a_1, a_2, \dots, a_k\}$ соответствует
уникальное целое число, равное $p(A) = \sum\limits_{i=1}^k 2^{a_i}$.
Функцию $F$ от $n$-элементного множества будем задавать массивом целых чисел
$f$ длины $2^n$ так, что значение функции $F(A)$ равно $f[p(A)]$.

Вам даны две функции $F$ и $G$, нужно найти функцию $H$ такую, что
$$H(A) = \sum\limits_{B \cup C = A}F(B)G(C)\text{.}$$

\InputFile

В первой строке заданы два целых числа $n$ и $t$
($1 \le n \le \LIMIT$, $1 \le t \le 100$).
Здесь $n$ "--- размер множества $U$, а $t$ "--- количество тестовых случаев.
Во второй строке заданы целые числа $a$ и $b$, каждое от $1$ до $10^9$.
Эти числа используются в следующем генераторе псевдослучайных чисел: \\
\texttt{
~ \\
1.\hspace{0em} unsigned int cur = 0; // беззнаковое 32-битное число \\
2.\hspace{0em} unsigned int nextRand16() \{ \\
3.\hspace{2em}   cur = cur * a + b; // вычисляется по модулю $2^{32}$ \\
4.\hspace{2em}   return cur / $2^{16}$; // целое число от $0$ до $2^{16}-1$ \\
5.\hspace{0em} \} \\
}

Тестовые случаи генерируются последовательно.
В каждом из них
сперва генерируются по порядку элементы массива $f$ (значения функции $F$),
а затем генерируются по порядку элементы массива $g$ (значения функции $G$).
Каждое следующее целое число генерируется вызовом функции
\texttt{nextRand16()}.

\OutputFile

В ответ на каждый тестовый случай выведите в отдельной строке
одно целое число:

$\left(\sum\limits_A H(A) \cdot (p(A)+1)\right) \bmod 2^{32}\text{.}$

\Examples

\begin{example}
\exmp{
3 2
30 239017
}{
2723387430
3167905008
}%
\exmp{
16 2
239 17
}{
551267264
1632349120
}%
\end{example}

\Explanations

Массивы в первом тесте из примера:

{\footnotesize{
$f_1 \colon 3,113,3395,36331,41370,61471,9130,11774$

$g_1 \colon 25547,45526,55066,13590,14501,41817,9356,18543$

$h_1 \colon 76641,8167827,273846333,5284992017,1656829263,11450721456,3699971823,14260048942$

$f_2 \colon 32024,43238,51978,52034,53714,38578,43250,52338$

$g_2 \colon 62834,50034,59250,8050,44914,36722,53106,20338$

$h_2 \colon 2012196016,6482475400,8243104152,15561662464,7225902008,16869349792,22350138288,44342816072$

}}
\end{problem}
