부분 수열 해시

길이가 $N$인 정수 배열이 주어진다. 이 배열의 비어 있지 않은 부분 수열을 모두 사전순으로 정렬한 결과를 $s_1, s_2, \dots, s_q$라고 하자. 부분 수열은 원래 배열에서 원소를 0개 이상 지워서 만드는 배열이다. 값이 서로 같은 부분 수열이 여러 개 나올 수 있고, $q = 2^N - 1$이다.

배열 $A$가 배열 $B$보다 사전순으로 앞선다는 것은, 두 배열이 처음으로 달라지는 위치 $i$에서 $A_i < B_i$이거나 $A$가 $B$의 진 접두사인 경우를 뜻한다.

값이 $v_1, v_2, \dots, v_p$인 배열의 해시는 다음과 같이 정의한다.

$h(s) = (v_1 B^{p-1} + v_2 B^{p-2} + \dots + v_{p-1} B + v_p) \bmod M$

$B$와 $M$은 입력으로 주어지는 정수다. $K$가 주어질 때 $h(s_1), h(s_2), \dots, h(s_K)$를 구한다.

첫째 줄에 정수 $N$, $K$, $B$, $M$이 주어진다. ($1 \le N \le 100\,000$, $1 \le K \le 100\,000$, $1 \le B, M \le 1\,000\,000$)

둘째 줄에 정수 $a_1, a_2, \dots, a_N$이 주어진다. ($1 \le a_i \le 100\,000$)

모든 입력에서 $K \le 2^N - 1$이 성립한다.

$K$개의 줄을 출력한다. $j$번째 줄에는 $h(s_j)$를 출력한다.

첫 번째 예제에서 정렬된 부분 수열은 $s_1 = [1]$, $s_2 = [1, 2]$, $s_3 = [2]$이다. 따라서 $h(s_1) = 1 \bmod 5 = 1$, $h(s_2) = (1 + 2) \bmod 5 = 3$, $h(s_3) = 2 \bmod 5 = 2$이다.

두 번째 예제에서 정렬된 부분 수열은 $s_1 = [1]$, $s_2 = [1]$, $s_3 = [1, 1]$, $s_4 = [1, 3]$이다. 값이 1인 원소가 두 개이므로 $[1]$이 두 번 나온다. 따라서 $h(s_1) = 1 \bmod 3 = 1$, $h(s_2) = 1 \bmod 3 = 1$, $h(s_3) = (1 \times 2 + 1) \bmod 3 = 0$, $h(s_4) = (1 \times 2 + 3) \bmod 3 = 2$이다.