Convolution

Consider all subsets of the set $U = \{0, 1, 2, \dots, n-1\}$. Each subset $A = \{a_1, a_2, \dots, a_k\}$ corresponds to a unique integer $p(A) = \sum_{i=1}^k 2^{a_i}$. A function $F$ on an $n$-element set is given by an integer array $f$ of length $2^n$, and $F(A) = f[p(A)]$.

You are given two functions $F$ and $G$. Find the function $H$ such that

$H(A) = \sum_{B \cup C = A} F(B)G(C).$

The first line contains two integers $n$ and $t$ ($1 \le n \le 16$, $1 \le t \le 100$). Here $n$ is the size of $U$, and $t$ is the number of test cases.

The second line contains two integers $a$ and $b$, each from $1$ to $10^9$. They are used in the following pseudo-random generator:

1. unsigned int cur = 0; // unsigned 32-bit integer
2. unsigned int nextRand16() {
3.   cur = cur * a + b; // calculated modulo 2^32
4.   return cur / 2^16; // integer from 0 to 2^16-1
5. }

The test cases are generated in order. In each one, first generate the elements of $f$ in increasing index order, then the elements of $g$ in the same order. Each element is produced by calling nextRand16().

For each test case, print one integer on its own line: $\left(\sum_A H(A) \cdot (p(A)+1)\right) \bmod 2^{32}$.

The arrays for the first example are:

• $f_1$: 3, 113, 3395, 36331, 41370, 61471, 9130, 11774
• $g_1$: 25547, 45526, 55066, 13590, 14501, 41817, 9356, 18543
• $h_1$: 76641, 8167827, 273846333, 5284992017, 1656829263, 11450721456, 3699971823, 14260048942
• $f_2$: 32024, 43238, 51978, 52034, 53714, 38578, 43250, 52338
• $g_2$: 62834, 50034, 59250, 8050, 44914, 36722, 53106, 20338
• $h_2$: 2012196016, 6482475400, 8243104152, 15561662464, 7225902008, 16869349792, 22350138288, 44342816072