괄호 문자열

(와 )로만 이루어진 문자열을 괄호 문자열이라고 한다. 괄호 문자열 가운데 올바른 괄호 문자열은 다음과 같이 정의한다.

1. 빈 문자열은 올바른 괄호 문자열이다.
2. 문자열 $S$가 올바른 괄호 문자열이면 $(S)$도 올바른 괄호 문자열이다.
3. 문자열 $S$와 $T$가 올바른 괄호 문자열이면 $ST$도 올바른 괄호 문자열이다.

올바른 괄호 문자열이 아닌 괄호 문자열은 올바르지 않은 괄호 문자열이라고 한다. (())(), ()()(), (()())는 올바른 괄호 문자열이고, ())((), (, (()()()는 올바르지 않은 괄호 문자열이다.

문자열 $S$의 접두사 가운데 비어 있지 않고 $S$ 자신도 아닌 것이 $S$의 접미사와 같으면, $S$를 주기성이 있는 문자열이라고 한다. 그런 접두사가 하나도 없는 문자열은 주기성이 없는 문자열이다. abcabcab, ()(, aaaaaa는 주기성이 있는 문자열이고, abcd, (())(), a는 주기성이 없는 문자열이다.

길이가 $L$인 괄호 문자열 가운데 주어진 조건을 만족하는 것이 몇 개인지 세는 프로그램을 작성하시오.

첫째 줄에 네 정수 $p$, $q$, $m$, $Q$가 공백을 사이에 두고 주어진다. ($0 \le p \le 1$, $0 \le q \le 1$, $1 \le m \le 10^6$, $1 \le Q \le 10^5$)

이어지는 $Q$개의 줄에 자연수 $L$이 한 줄에 하나씩 주어진다. ($1 \le L \le 10^6$)

길이가 $L$인 모든 괄호 문자열의 집합을 $A_L$, 길이가 $L$인 올바르지 않은 괄호 문자열의 집합을 $B_L$, 길이가 $L$인 주기성이 없는 괄호 문자열의 집합을 $C_L$이라고 하자. $p = 0$이면 $P = A_L$, $p = 1$이면 $P = B_L$이고, $q = 0$이면 $R = A_L$, $q = 1$이면 $R = C_L$이다.

정리하면 $p = 0$, $q = 0$일 때는 길이가 $L$인 괄호 문자열의 개수를, $p = 1$, $q = 0$일 때는 올바르지 않은 괄호 문자열의 개수를, $p = 0$, $q = 1$일 때는 주기성이 없는 괄호 문자열의 개수를, $p = 1$, $q = 1$일 때는 올바르지 않으면서 주기성도 없는 괄호 문자열의 개수를 세면 된다.

각 $L$마다 $|P \cap R|$을 $m$으로 나눈 나머지를 한 줄에 하나씩 출력한다. 입력에 주어진 순서대로 $Q$개의 줄을 출력한다.

길이가 4인 괄호 문자열 가운데 올바른 것은 ()()과 (()) 두 가지이므로, 올바르지 않은 것은 $16 - 2 = 14$개다. 길이가 4이면서 주기성이 없는 괄호 문자열은 (((), (()), ())), )(((, ))((, )))( 여섯 개이고 그중 올바른 것은 (()) 하나뿐이므로, 길이가 4이면서 올바르지 않고 주기성도 없는 괄호 문자열은 5개다.