클래스 통합

Supervin은 1번부터 N번까지 번호가 붙은 N개의 클래스를 가르친다. 가장 최근 시험을 채점한 뒤, 그는 각 클래스의 학생 점수가 연속한 정수들의 수열을 이룬다는 사실을 알아냈다. 따라서 Supervin은 i번째 클래스의 점수 분포를 두 정수 Li와 Ri로 요약할 수 있다. 즉 i번째 클래스에는 Ri - Li + 1명의 학생이 있고, 각 x(Li ≤ x ≤ Ri)에 대해 점수가 x인 학생이 정확히 한 명씩 있다.

Supervin은 모든 클래스의 학생 점수를 하나로 모아 내림차순으로 정렬하려고 한다. 이 목록에 대해 Q개의 질문(1번부터 Q번까지 번호가 붙음)이 주어지며, i번째 질문에서는 Ki번째로 높은 점수가 무엇인지 알고 싶어 한다. (Ki가 전체 학생 수보다 크면 i번째 질문의 답은 0이다.)

Supervin이 모든 질문에 답하도록 도와줄 수 있는가? 답이 너무 많을 수 있으므로, 모두 출력하는 대신 답을 구했다는 증거를 출력한다. 즉 1 ≤ i ≤ Q인 모든 i에 대해 (Si × i)의 합을 출력하라. 여기서 Si는 i번째 질문의 답이다.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어지며, 각 테스트 케이스는 네 줄로 이루어진다. 첫 줄에는 위에서 설명한 두 정수 N과 Q가 주어진다. 다음 세 줄에는 각각 다음과 같은 형식으로 여섯 개의 정수가 주어진다.

• X1 X2 A1 B1 C1 M1
• Y1 Y2 A2 B2 C2 M2
• Z1 Z2 A3 B3 C3 M3

이 값들은 Li, Ri, Ki를 다음과 같이 생성하는 데 사용된다.

먼저 다음과 같이 정의한다.

• Xi = (A1 × Xi - 1 + B1 × Xi - 2 + C1) modulo M1, i = 3부터 N까지.
• Yi = (A2 × Yi - 1 + B2 × Yi - 2 + C2) modulo M2, i = 3부터 N까지.
• Zi = (A3 × Zi - 1 + B3 × Zi - 2 + C3) modulo M3, i = 3부터 Q까지.

그리고 다음과 같이 정의한다.

• Li = min(Xi, Yi) + 1, i = 1부터 N까지.
• Ri = max(Xi, Yi) + 1, i = 1부터 N까지.
• Ki = Zi + 1, i = 1부터 Q까지.

각 테스트 케이스마다 Case #x: y 형식의 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이고, y는 1 ≤ i ≤ Q인 모든 i에 대해 (Si × i)의 합이다. Si는 i번째 질문의 답이다.

• 1 ≤ T ≤ 100.
• 1 ≤ N ≤ 4 × 105.
• 모든 i에 대해 0 ≤ Ai < Mi.
• 모든 i에 대해 0 ≤ Bi < Mi.
• 모든 i에 대해 0 ≤ Ci < Mi.
• 0 ≤ X1 < M1.
• 0 ≤ X2 < M1.
• 0 ≤ Y1 < M2.
• 0 ≤ Y2 < M2.
• 0 ≤ Z1 < M3.
• 0 ≤ Z2 < M3.
• 모든 i에 대해 1 ≤ Mi ≤ 109.