반 합치기

Supervin은 1부터 N까지 번호가 매겨진 N개의 반을 가르치고 있다. 가장 최근 시험을 치른 후, 그는 각 반 학생들의 시험 점수가 연속된 정수의 수열을 이룬다는 것을 알아차렸다. 따라서 Supervin은 i번째 반의 점수를 두 정수 $L_{i}$와 $R_{i}$로 요약할 수 있다. 이는 i번째 반에 $R_{i}$ - $L_{i}$ + 1명의 학생이 있고, 각 x에 대해($L_{i}$ ≤ x ≤ $R_{i}$) 점수가 x인 학생이 정확히 한 명 있다는 뜻이다.

Supervin은 모든 반 학생들의 점수를 합친 뒤 점수를 비증가 순서로 정렬하려고 한다. 그는 이 목록에 관해 1부터 Q까지 번호가 매겨진 Q개의 질문이 있으며, i번째 질문에서는 $K_{i}$번째로 높은 점수가 무엇인지 알고 싶어 한다. ($K_{i}$가 학생 수보다 크면 i번째 질문의 답은 0이다.)

Supervin이 모든 질문에 답하도록 도와주자. 답이 많을 수 있으므로 모든 답을 출력하는 대신, 답했다는 증거로 모든 1 ≤ i ≤ Q에 대한 ($S_{i}$ × i)의 합을 출력한다. 여기서 $S_{i}$는 i번째 질문의 답이다.

제한

1 ≤ T ≤ 100. 테스트 세트별 시간 제한: 180초. 메모리 제한: 1 GB. 1 ≤ N ≤ 4 × $10^{5}$. 모든 i에 대해 0 ≤ $A_{i}$ < $M_{i}$. 모든 i에 대해 0 ≤ $B_{i}$ < $M_{i}$. 모든 i에 대해 0 ≤ $C_{i}$ < $M_{i}$. 0 ≤ $X_{1}$ < $M_{1}$. 0 ≤ $X_{2}$ < $M_{1}$. 0 ≤ $Y_{1}$ < $M_{2}$. 0 ≤ $Y_{2}$ < $M_{2}$. 0 ≤ $Z_{1}$ < $M_{3}$. 0 ≤ $Z_{2}$ < $M_{3}$. 모든 i에 대해 1 ≤ $M_{i}$ ≤ $10^{9}$.

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

Q = 1.

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

1 ≤ Q ≤ $10^{5}$.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 네 줄로 구성된다. 첫 번째 줄에는 위에서 설명한 두 정수 N과 Q가 주어진다. 그다음 세 줄에는 각각 다음 형식으로 여섯 개의 정수가 주어진다.

• $X_{1}$ $X_{2}$ $A_{1}$ $B_{1}$ $C_{1}$ $M_{1}$

• $Y_{1}$ $Y_{2}$ $A_{2}$ $B_{2}$ $C_{2}$ $M_{2}$

• $Z_{1}$ $Z_{2}$ $A_{3}$ $B_{3}$ $C_{3}$ $M_{3}$

이 값들은 다음과 같이 $L_{i}$, $R_{i}$, $K_{i}$를 생성하는 데 사용된다.

다음을 정의한다.

• i = 3부터 N까지, $X_{i}$ = ($A_{1}$ × $X_{i - 1}$ + $B_{1}$ × $X_{i - 2}$ + $C_{1}$)를 $M_{1}$로 나눈 나머지.

• i = 3부터 N까지, $Y_{i}$ = ($A_{2}$ × $Y_{i - 1}$ + $B_{2}$ × $Y_{i - 2}$ + $C_{2}$)를 $M_{2}$로 나눈 나머지.

• i = 3부터 Q까지, $Z_{i}$ = ($A_{3}$ × $Z_{i - 1}$ + $B_{3}$ × $Z_{i - 2}$ + $C_{3}$)를 $M_{3}$로 나눈 나머지.

또한 다음을 정의한다.

• i = 1부터 N까지, $L_{i}$ = min($X_{i}$, $Y_{i}$) + 1.

• i = 1부터 N까지, $R_{i}$ = max($X_{i}$, $Y_{i}$) + 1.

• i = 1부터 Q까지, $K_{i}$ = $Z_{i}$ + 1.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x는 1부터 시작하는 테스트 케이스 번호이고, y는 모든 1 ≤ i ≤ Q에 대한 ($S_{i}$ × i)의 합이며, $S_{i}$는 i번째 질문의 답이다.

예제 케이스 #1에서 생성된 배열 X, Y, Z는 다음과 같다.

• $X = [3, 1, 3, 0, 8]$.

• $Y = [2, 7, 7, 2, 6]$.

• $Z = [4]$.

따라서,

• $L = [3, 2, 4, 1, 7]$.

• $R = [4, 8, 8, 3, 9]$.

• $K = [5]$.

각 반 학생들의 점수는 $[3, 4]$, $[2, 3, 4, 5, 6, 7, 8]$, $[4, 5, 6, 7, 8]$, $[1, 2, 3]$, $[7, 8, 9]$이다. 이는 모든 반 학생들의 점수를 합치면 $[3, 4, 2, 3, 4, 5, 6, 7, 8, 4, 5, 6, 7, 8, 1, 2, 3, 7, 8, 9]$이라는 뜻이다. 이를 비증가 순서로 정렬하면 $[9, 8, 8, 8, 7, 7, 7, 6, 6, 5, 5, 4, 4, 4, 3, 3, 3, 2, 2, 1]$이다. 따라서 5번째로 높은 점수를 받은 학생의 점수는 7이다. 그러므로 $S = [7]$이고, 답은 7 × 1 = 7이다.

추가 예제 - 테스트 세트 2

예제 케이스 #1에서는 Q의 값을 제외한 모든 매개변수가 예제 케이스 #1과 같다. 따라서 L과 R의 값 및 모든 반 학생들의 점수를 합친 결과는 여전히 예제 케이스 #1과 같다. 하지만 이제 질의는 $K = [5, 9, 40, 23, 12]$이다. 5번째, 9번째, 12번째로 높은 점수를 받은 학생들의 점수는 각각 7, 6, 4이다. 학생이 20명뿐이므로 23번째와 40번째 학생은 존재하지 않는다. 따라서 $S = [7, 6, 0, 0, 4]$이고, 답은 7 × 1 + 6 × 2 + 0 × 3 + 0 × 4 + 4 × 5 = 7 + 12 + 20 = 39이다.

예제 케이스 #2에서 생성된 배열 X, Y, Z는 다음과 같다.

• $X = [0]$.

• $Y = [0]$.

• $Z = [0, 1]$.

따라서,

• $L = [1]$.

• $R = [1]$.

• $K = [1, 2]$.

따라서 학생은 한 명뿐이고 $S = [1, 0]$이므로, 답은 1 × 1 + 0 × 2 = 1이다.