셜록과 행렬 게임

오늘 셜록과 왓슨은 행렬을 소개하는 강의를 들었다. 셜록은 선형대수학에 별로 관심이 없는 프로그래머 중 하나이지만, 왓슨이 풀 수 있도록 행렬과 관련된 문제를 하나 생각해 냈다.

셜록은 왓슨에게 길이가 모두 N인 두 일차원 배열 A와 B를 주었다. 그는 왓슨에게 N개의 행과 N개의 열로 이루어진 행렬을 만들도록 요청했으며, 이 행렬에서 i^{}번째 행의 j^{}번째 원소는 A의 i번째 원소와 B의 j번째 원소의 곱이다.

(x, y)는 행렬에서 위쪽 행부터 0에서 시작하여 번호를 매긴 x번째 행과 왼쪽 열부터 0에서 시작하여 번호를 매긴 y번째 열에 있는 칸을 나타낸다고 하자. 그러면 부분 행렬은 각각 왼쪽 아래 칸과 오른쪽 위 칸인 (a, b) 및 (c, d)로 정의되며, ≥ c이고 d ≥ b이며, 이 부분 행렬은 c ≤ i ≤ a이고 b ≤ j ≤ d인 모든 칸 (i, j)로 구성된다. 부분 행렬의 합은 그 부분 행렬에 속한 모든 칸의 합으로 정의한다.

왓슨에게 도전 과제를 주기 위해, 셜록은 정수 K를 주고 왓슨의 행렬에 존재하는 모든 부분 행렬의 합 중 $K^{th}$번째로 큰 합을 출력하도록 요청했다. 이때 가장 큰 합부터 K를 1에서 시작하여 센다. (서로 다른 K 값이 같은 합에 대응할 수도 있다. 즉, 합이 같은 부분 행렬이 여러 개 존재할 수 있다.) 왓슨을 도와줄 수 있는가?

제한

1 ≤ T ≤ 20. 메모리 제한: 1GB. 1 ≤ K ≤ min($10^{5}$, 가능한 부분 행렬의 총개수). 0 ≤ $A_{1}$ ≤ $10^{3}$. 0 ≤ $B_{1}$ ≤ $10^{3}$. 0 ≤ C ≤ $10^{3}$. 0 ≤ D ≤ $10^{3}$. 0 ≤ $E_{1}$ ≤ $10^{3}$. 0 ≤ $E_{2}$ ≤ $10^{3}$. 1 ≤ F ≤ $10^{3}$.

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

시간 제한: 40초. 1 ≤ N ≤ 200.

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

시간 제한: 200초. 1 ≤ N ≤ $10^{5}$.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 아홉 정수 N, K, $A_{1}$, $B_{1}$, C, D, $E_{1}$, $E_{2}$, F가 한 줄에 주어진다. N은 배열 A와 B의 길이이고, K는 왓슨이 출력해야 하는 부분 행렬 합의 순위이며, $A_{1}$와 $B_{1}$는 각각 배열 A와 B의 첫 번째 원소이다. 나머지 다섯 값은 다음과 같이 배열의 원소를 생성하는 데 사용해야 하는 매개변수이다:

먼저 $x_{1}$ = $A_{1}$, $y_{1}$ = $B_{1}$, $r_{1}$ = 0, $s_{1}$ = 0로 정의한다. 그런 다음 아래 점화식을 사용하여 i = 2부터 N까지 $x_{i}$와 $y_{i}$를 생성한다:

• $x_{i}$ = ( C*$x_{i-1}$ + D*$y_{i-1}$ + $E_{1}$ )를 F로 나눈 나머지.

• $y_{i}$ = ( D*$x_{i-1}$ + C*$y_{i-1}$ + $E_{2}$ )를 F로 나눈 나머지.

또한 다음 점화식을 사용하여 i = 2부터 N까지 $r_{i}$와 $s_{i}$를 생성한다:

• $r_{i}$ = ( C*$r_{i-1}$ + D*$s_{i-1}$ + $E_{1}$ )를 2로 나눈 나머지.

• $s_{i}$ = ( D*$r_{i-1}$ + C*$s_{i-1}$ + $E_{2}$ )를 2로 나눈 나머지.

i = 2부터 N까지의 모든 i에 대해 $A_{i}$ = (-1)^{$r_{i}$} * $x_{i}$ 및 $B_{i}$ = (-1)^{$s_{i}$} * $y_{i}$로 정의한다.

각 테스트 케이스마다 Case #x: y를 포함하는 한 줄을 출력한다. 여기서 x는 1부터 시작하는 테스트 케이스 번호이고, y는 문제에서 정의한 행렬에서 $K^{th}$번째로 큰 부분 행렬의 합이다.

케이스 1에서는 생성 방법을 사용하면 생성된 배열 A와 B가 각각 $[1, -3]$와 $[1, -3]$이다. 따라서 만들어지는 행렬은 다음과 같다. $[1, -3]$ $[-3, 9]$ 가능한 모든 부분 행렬의 합을 내림차순으로 나열하면 $[9, 6, 6, 4, 1, -2, -2, -3, -3]$이다. K = 3이므로 답은 6이다.

케이스 2에서는 생성 방법을 사용하면 생성된 배열 A와 B가 각각 $[2]$와 $[2]$이다. 따라서 만들어지는 행렬은 다음과 같다. $[4]$ K = 1이므로 답은 4이다.

케이스 3에서는 생성 방법을 사용하면 생성된 배열 A와 B가 각각 $[1, 0]$와 $[2, -1]$이다. 따라서 만들어지는 행렬은 다음과 같다. $[2, -1]$ $[0, 0]$ 가능한 모든 부분 행렬의 합을 내림차순으로 나열하면 $[2, 2, 1, 1, 0, 0, 0, -1, -1]$이다. K = 3이므로 답은 1이다.