사탕

Supervin은 사탕 먹는 것을 좋아한다. 오늘 그가 가장 좋아하는 사탕 가게에서는 일렬로 배열된 N개의 사탕을 판매한다. 줄에서 1부터 세었을 때 i번째 사탕의 단맛 수준은 $S_{i}$이다. 사탕의 단맛 수준은 음수일 수도 있으며, 이는 사탕의 맛이 쓰다는 뜻임에 유의하라.

Supervin은 단 사탕을 먹는 것을 좋아한다. 하지만 단맛 수준의 합이 D보다 크면 그에게도 너무 달다. 또한 Supervin은 단맛 수준이 홀수인 사탕이 "odd"임을 알고 있으며, 홀수인 사탕을 O개보다 많이 먹고 싶어 하지 않는다. 다시 말해, 홀수인 사탕은 단맛 수준이 2로 나누어떨어지지 않는 사탕이다. 게다가 Supervin은 서두르고 있으므로 연속한 사탕 부분집합 하나만 먹을 수 있다.

따라서 그는 홀수인 사탕이 최대 O개이고, 단맛 수준의 합이 D를 넘지 않으면서 최대가 되는 연속한 비어 있지 않은 사탕 부분집합을 먹고 싶어 한다. 그가 얻을 수 있는 단맛 수준의 합의 최댓값을 구하려면 Help Supervin하고, 이러한 제약 조건을 만족하는 연속 부분집합이 없다면 IMPOSSIBLE을 반환한다.

제한

1 ≤ T ≤ 100. 테스트 세트별 시간 제한: 40초. 메모리 제한: 1 GB. 2 ≤ N ≤ 5 × $10^{5}$. 0 ≤ O ≤ N. -$10^{15}$ ≤ D ≤ $10^{15}$. 0 ≤ $X_{1}$, $X_{2}$, A, B, C ≤ $10^{9}$. 1 ≤ M ≤ $10^{9}$.

작은 데이터셋(테스트 세트 1 - 공개)

L = 0.

큰 데이터셋(테스트 세트 2 - 비공개)

-5 × $10^{8}$ ≤ L ≤ 0.

입력의 첫째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 두 줄로 이루어진다. 첫째 줄에는 위에서 설명한 세 정수 N, O, D가 주어진다. 둘째 줄에는 일곱 정수 $X_{1}$, $X_{2}$, A, B, C, M, L이 주어지며, 이 값들은 다음과 같이 값 $S_{i}$을 생성하는 데 사용된다.

다음과 같이 정의한다.

• i = 3부터 N까지, $X_{i}$ = (A × $X_{i - 1}$ + B × $X_{i - 2}$ + C)를 M으로 나눈 나머지.

• i = 1부터 N까지, $S_{i}$ = $X_{i}$ + L.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x은 1부터 시작하는 테스트 케이스 번호이고, y은 Supervin이 얻을 수 있는 단맛 수준의 합의 최댓값이다. 문제의 제약 조건을 만족하는 가능한 연속 부분집합이 없다면 IMPOSSIBLE을 출력한다.

예제 케이스 #1에서 생성된 단맛 값의 배열 $S_{i}$은 $[1, 1, 2, 3, 5, 8]$이며, 굵게 밑줄 친 수가 홀수이다. Since Supervin은 홀수인 사탕을 하나만 먹을 수 있으므로, 다섯 번째와 여섯 번째 사탕을 선택하면 단맛 수준의 합의 최댓값을 얻을 수 있다.

예제 케이스 #2에서 생성된 단맛 값의 배열 $S_{i}$은 예제 케이스 #1와 같다. 하지만 이번에는 Supervin이 단맛 수준의 합이 -100보다 큰 사탕들을 먹을 수 없으므로, 제약 조건을 만족하는 연속한 사탕 부분집합이 없다.

참고: 이 문제의 큰 데이터셋에는 인터프리터 방식의 느린 언어를 사용하는 것을 권장하지 않는다.

추가 예제 - 테스트 세트 2

예제 케이스 #1에서 생성된 단맛 값의 배열 $S_{i}$은 $[-6, -7, -9, 2, 4, 3, 1, -8, -6, -7]$이며, 굵게 밑줄 친 수가 홀수이다. Since Supervin은 홀수인 사탕을 하나만 먹을 수 있고 단맛 수준의 합이 8보다 큰 사탕들을 먹을 수 없으므로, 다섯 번째와 여섯 번째 사탕을 선택하면 단맛 수준의 합의 최댓값을 얻을 수 있다.

예제 케이스 #2에서 생성된 단맛 값의 배열 $S_{i}$은 예제 케이스 #1와 같다. 하지만 이번에는 Supervin이 홀수인 사탕을 두 개 먹을 수 있다. 따라서 다섯 번째, 여섯 번째, 일곱 번째 사탕을 선택하면 단맛 수준의 합의 최댓값을 얻을 수 있다.

예제 케이스 #3에서 생성된 단맛 값의 배열 $S_{i}$은 $[-15, -16, -18, -7, -5, -6, -8, -17, -15, -16]$이며, 굵게 밑줄 친 수가 홀수이다. 단맛 수준의 합의 최댓값이 음수일 수도 있음에 유의하라.