시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 256 MB 39 13 12 60.000%

문제

4명의 여신에 의해 수호되고 있는 이(異)세계는 오늘도 여전히 신도들을 모으기 위한 전쟁이 일어나고 있다. 최근 전쟁에서 계속 패하기만 했던 여신 이나는 다음 전쟁에서는 꼭 이기리라 다짐하고 다른 여신들의 행동 패턴을 분석하였다. 결국 이나는 모든 여신들의 이동을 수치화하는데 성공했으며 이를 단위 이동이라 부르기로 했다.

단위 이동의 몇 가지 특징을 정리해보면 다음과 같다.

  1. 여신들은 투명하진 않지만 초월적인 존재이기 때문에 차원을 마음대로 넘나들 수 있다.
  2. 여신들은 간결함을 좋아하기 때문에 정수 좌표로만 이동한다.
  3. 여신들의 이동은 원점을 기준으로 한다.
  4. n차원 공간의 단위 이동 (x1, x2, ..., xn)이 있다고 하자. 여신들은 게으르기 때문에 x1, x2, ..., xn 중 적어도 한 가지 값은 1임이 보장된다. 또한, 단위 이동 (x1, x2, ..., xn)에서 처음 나오는 1의 위치가 xi라면 x1, x2, ..., xi-1은 0이 보장된다.

어떤 좌표가 주어졌을 때 단위 이동을 적당한 순서로 조합하여 도달할 수 있으면 이동 가능한 위치, 없으면 불가능한 위치라고 한다. 이때, 각 단위 이동은 몇 번이고 사용할 수 있다.

만약 도달 가능한 위치의 경우, 가장 적은 수의 단위 이동을 사용해 이동했을 때 사용된 단위 이동의 수를 최단 이동 횟수라고 한다. 즉, 어떤 위치로의 이동 횟수 x가 같은 위치로 움직이는 다른 모든 이동 횟수 y에 대해 x ≤ y를 만족 한다면 x는 최단 이동 횟수이다.

예를 들어 여신들이 2차원 공간에서 움직인다고 가정하자. 만약 단위 이동의 집합이 {(1, 0), (0, 1)}이라면 (2, 1)은 (1, 0)+(1, 0)+(0, 1)과 같이 표현할 수 있으므로 이동 가능한 위치이고 다른 어떤 이동보다 이보다 적은 횟수로 움직일 수 있지 않으므로 최단 이동 횟수는 3이다. 반면에 (-1, 1)로는 이동할 수 없다. 즉 단위 이동의 횟수는 항상 음이 아닌 정수여야 한다.

이나는 특정 위치가 주어졌을 때 다른 여신들이 그 위치로 움직일 수 있는지 없는지를 빠르게 판단하고, 그 위치까지 가는데 필요한 최단 이동 횟수를 계산하는 알고리즘을 설계하여 다음 전쟁 때 사용하려 한다. 하지만 할 일이 많기에 신실한 신도인 당신에게 이 일을 맡기기로 했다.

여신 이나를 도와 전쟁에서 승리하기 위한 알고리즘을 설계하자.

입력

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 각 테스트 케이스의 첫 줄에는 차원의 수를 나타내는 양의 정수 n(1 ≤ n ≤ 500)이 주어진다. 다음 줄부터 여신들의 단위 이동들이 n개의 줄에 걸쳐 주어진다. i번째 줄에는 i번 단위 이동을 나타내는 n개의 정수 xij(1 ≤ i ≤ n, 1 ≤ j ≤ n, -1,000 ≤ xij ≤ 1,000)가 빈칸을 사이에 두고 주어진다. 그다음 줄에는 특정 위치의 좌표를 나타내는 n개의 정수 yi(1 ≤ i ≤ n, -5×108 ≤ yi ≤ 5×108)가 주어진다.

출력

각 테스트 케이스별로 한 줄에 한 개씩 다른 여신들이 주어진 특정 좌표에 도달할 수 있다면 1, 없다면 0을 출력한다. 만약 도달할 수 있다면, 같은 줄에 추가로 최단 이동 횟수를 빈칸으로 구분하여 출력한다.

예제 입력

3
1
1
5
2
1 0
0 1
-1 1
3
1 1 1
0 1 -1
0 0 1
1 2 0

예제 출력

1 5
0
1 2

힌트