얼의 초고효율 암호화

얼은 동영상 파일의 크기를 줄이는 초고효율 암호화 알고리즘을 방금 완성했다. 동영상은 이미지를 순서대로 늘어놓은 것으로 볼 수 있다.

가장 단순한 방법은 이미지를 하나씩 전부 저장하는 것이다. 얼의 알고리즘은 대신 연속한 두 이미지의 차이만 저장한다. 차이 하나는 32비트 정수 하나에 담기고, 이 값을 전이 정수라고 부른다. 암호화하지 않은 첫 이미지와 전이 정수 전체가 있으면 동영상을 그대로 복원한다.

문제는 전이 정수를 계산하는 과정이 손실 압축이라는 점이다. 32비트 정수는 실제 차이의 근삿값일 뿐이라서 오류가 생기고 이미지가 잘못 나올 수 있다. 전이 하나가 제대로 동작할 확률은 매우 높지만, 동영상 전체를 오류 없이 재생할 확률은 상당히 낮다. 게다가 잘못 만들어진 이미지 위에 다음 차이를 다시 적용하므로 오류가 서로 쌓인다.

이를 막으려고 알고리즘은 첫 이미지만이 아니라 이미지의 일부 집합을 암호화하지 않은 원본으로 저장한다. 각 전이에서 알고리즘은 다음 이미지의 원본이 저장되어 있는지 확인한다. 저장되어 있으면 그 원본을 화면에 그대로 보여주고, 저장되어 있지 않으면 전이 정수로 다음 이미지를 만든다.

동영상의 나쁨은 전이 정수를 연속으로 사용한 최대 횟수다. 얼의 알고리즘은 이미지가 $L$개 이하인 동영상을 모두 처리한다. 동영상 모음의 이미지 개수와 얼이 원본으로 저장할 이미지 집합이 주어질 때, 동영상마다 나쁨을 구하라.

입력은 테스트 케이스 하나로 이루어진다.

첫 줄에 정수 여섯 개 $k$ ($1 \le k \le 100$), $n$ ($1 \le n \le 10^5$), $L$ ($1 \le L \le 10^9$), $a$ ($0 \le a \le L$), $b$ ($0 \le b \le L$), $g_1$ ($0 \le g_1 \le L$)이 공백으로 구분되어 주어진다. $g_0 = 0$으로 두고, 나머지 항은 다음과 같이 정한다.

$g_i = (a \cdot g_{i-1} + b) \bmod (L+1) \quad (2 \le i \le n)$

다음 $k$개의 줄 중 $j$번째 줄에는 정수 $w_j$ ($1 \le w_j \le L$) 하나가 주어진다. $w_j$는 $j$번째 동영상을 압축하지 않고 저장했을 때의 이미지 개수다. $j$번째 동영상의 이미지에는 $0$번부터 $w_j - 1$번까지 번호가 붙고, 얼이 원본으로 저장하는 이미지의 집합은 다음과 같다.

$\{g_i : 0 \le i \le n\} \cap \{0, 1, \dots, w_j - 1\}$

$g_0 = 0$이므로 $0$번 이미지는 언제나 원본으로 저장된다. 동영상은 $w_j$가 증가하는 순서로 주어진다.

동영상마다 나쁨을 한 줄에 하나씩, 입력에 주어진 순서대로 출력한다.

첫 번째 예제에서 원본으로 저장되는 이미지는 0번, 2번, 4번, 6번, 8번, 10번이다. 길이가 1인 동영상은 전이 정수가 아예 필요 없으므로 나쁨이 0이다. 길이가 3인 동영상은 0번에서 1번으로 갈 때만 전이 정수를 쓴다. 길이가 7인 동영상은 0번에서 1번, 2번에서 3번, 4번에서 5번으로 갈 때 전이 정수를 한 번씩 쓰지만 연속으로 두 번 쓰는 일은 없으므로 나쁨이 1이다. 길이가 14인 동영상은 11번, 12번, 13번 이미지를 전이 정수로 연달아 만들어야 하므로 나쁨이 3이다.