Bracket Strings

A string made only of ( and ) is a bracket string. Among bracket strings, a correct bracket string is defined as follows.

1. The empty string is a correct bracket string.
2. If a string $S$ is a correct bracket string, then $(S)$ is also a correct bracket string.
3. If strings $S$ and $T$ are correct bracket strings, then $ST$ is also a correct bracket string.

A bracket string that is not correct is called an incorrect bracket string. (())(), ()()(), (()()) are correct bracket strings, and ())((), (, (()()() are incorrect bracket strings.

A string $S$ is periodic if some prefix of $S$ that is neither empty nor $S$ itself is also a suffix of $S$. A string with no such prefix is aperiodic. abcabcab, ()(, aaaaaa are periodic, and abcd, (())(), a are aperiodic.

Write a program that counts the bracket strings of length $L$ satisfying the given conditions.

The first line contains four integers $p$, $q$, $m$, $Q$ separated by spaces. ($0 \le p \le 1$, $0 \le q \le 1$, $1 \le m \le 10^6$, $1 \le Q \le 10^5$)

Each of the next $Q$ lines contains one natural number $L$. ($1 \le L \le 10^6$)

Let $A_L$ be the set of all bracket strings of length $L$, let $B_L$ be the set of incorrect bracket strings of length $L$, and let $C_L$ be the set of aperiodic bracket strings of length $L$. If $p = 0$ then $P = A_L$, and if $p = 1$ then $P = B_L$. If $q = 0$ then $R = A_L$, and if $q = 1$ then $R = C_L$.

In other words, for $p = 0$, $q = 0$ count the bracket strings of length $L$; for $p = 1$, $q = 0$ count the incorrect ones; for $p = 0$, $q = 1$ count the aperiodic ones; for $p = 1$, $q = 1$ count the ones that are incorrect and also aperiodic.

For each $L$, print $|P \cap R|$ modulo $m$ on its own line. Print $Q$ lines in the order the lengths are given.

Among the bracket strings of length 4, exactly two are correct, ()() and (()), so $16 - 2 = 14$ of them are incorrect. The aperiodic bracket strings of length 4 are (((), (()), ())), )(((, ))((, )))(, six in total, and only (()) among them is correct. So 5 bracket strings of length 4 are incorrect and aperiodic at the same time.