Convolution

Consider all subsets of set $U = \\{0, 1, 2, \dots, n-1\\}$. Every subset $A = \\{a\_1, a\_2, \dots, a\_k\\}$ corresponds to a unique integer $p(A) = \sum\limits\_{i=1}^k 2^{a\_i}$. Let function $F$ of an $n$-element set be defined by an array of integers $f$ of length $2^n$: the value $F(A)$ is equal to $f\[p(A)]$.

You are given two functions $F$ and $G$. Your task is to find such function $H$ that $H(A) = \sum\limits\_{B \cup C = A}F(B)G(C)\text{.}$

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 the set $U$, and $t$ is number of test cases. The second line contains two integers $a$ and $b$, each from $1$ to $10^9$. These numbers 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 232
4.   return cur / 216; // integer from 0 to 216-1
5. }

The test cases are generated successively. In each of them, first, you must generate the elements of array $f$ (values of $F$) in the order of increasing array index, and after that, you must generate the elements of $g$ (values of $G$) in the same order. Each element is generated by calling the function nextRand16().

For each test case, print one integer on a separate line: $\left(\sum\limits\_A H(A) \cdot (p(A)+1)\right) \bmod 2^{32}\text{.}$

The arrays in the first example are the following:

• $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$