사탕

Supervin은 사탕을 좋아한다. 오늘 단골 사탕 가게에서 사탕 N개를 판매하는데, 이 사탕들은 한 줄로 나열되어 있다. 줄의 i번째 사탕(1부터 센다)의 단맛은 Si이다. 사탕의 단맛은 음수일 수도 있는데, 이는 그 사탕이 쓴맛이라는 뜻이다.

Supervin은 단 사탕을 좋아한다. 하지만 단맛의 합이 D보다 크면 그에게도 너무 달다. 또한 Supervin은 단맛이 홀수인 사탕을 "홀수 사탕"이라 부르는데, 홀수 사탕을 O개보다 많이 먹고 싶지 않다. 즉, 홀수 사탕이란 단맛이 2로 나누어떨어지지 않는 사탕이다. 게다가 Supervin은 시간이 없어서 연속한 사탕 한 묶음만 먹을 수 있다.

따라서 그는 홀수 사탕이 O개 이하이면서 단맛의 합이 최대가 되도록, 단 D를 넘지 않는 연속한 비어 있지 않은 사탕 묶음을 먹으려 한다. Supervin이 얻을 수 있는 단맛 합의 최댓값을 구하라. 조건을 만족하는 연속한 묶음이 없으면 IMPOSSIBLE을 출력한다.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. T개의 테스트 케이스가 이어진다. 각 테스트 케이스는 두 줄로 이루어진다. 첫 줄에는 위에서 설명한 세 정수 N, O, D가 주어진다. 둘째 줄에는 일곱 정수 X1, X2, A, B, C, M, L이 주어지며, 이 값들로 Si를 다음과 같이 생성한다.

다음과 같이 정의한다.

• Xi = (A × Xi - 1 + B × Xi - 2 + C) modulo M, i = 3부터 N까지.
• Si = Xi + L, i = 1부터 N까지.

각 테스트 케이스마다 Case #x: y를 한 줄에 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이고, y는 Supervin이 얻을 수 있는 단맛 합의 최댓값이다. 문제의 조건을 만족하는 연속한 묶음이 없으면 IMPOSSIBLE을 출력한다.

• 1 ≤ T ≤ 100.
• 2 ≤ N ≤ 5 × 105.
• 0 ≤ O ≤ N.
• -1015 ≤ D ≤ 1015.
• 0 ≤ X1, X2, A, B, C ≤ 109.
• 1 ≤ M ≤ 109.