시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 12 3 3 27.273%

문제

3133년에 우주 여행은 매우 흔한 일이 되었다. 차원 워프 드라이브를 이용하면 멀리 떨어져 있는 두 행성을 거의 즉시 이동할 수 있다.

차원 워프 드라이브는 상대 굴곡 양자화 우주(Relativistic Curved Quantized Space)의 법칙을 따른다. RCQS이론에 따르면 우주는 11차원으로 이루어져 있고, 각각은 자기 자신으로 굽어져 있다. 즉, 한 방향으로 계속해서 걸어간다면 출발한 지점으로 돌아올 수 있다.

이 이론에 의하면 우주는 양자화 되어져 있고, 각각의 차원에 대해서 가능한 위치는 총 11개가 있다. 0부터 10까지 있으며, 위치 11은 위치 0과 같다.

3075년에 첫 번째 워프 궤도가 발견되었다. 이러한 궤도를 이용하면 우주선은 현재 위치 좌표와 그 궤도의 좌표를 합한 좌표로 이동할 수 있다. (각각의 차원에 대해 적용) 한 번 발견된 워프 궤도는 여러 번 이용할 수 있다.

이후에 더 많은 워프 궤도가 발견되었고, 인간은 이 궤도를 이용해서 우주를 기하 급수적으로 식민지화 하기 시작했다.

현재 상근이의 위치와 가려고 하는 위치가 주어진다. 이 때, 몇 년이 되면 그 곳으로 갈 수 있는지 구하는 프로그램을 작성하시오.

예를 들어, 상근이가 현재 (0,0,0,0,0,0,0,0,0,0,0)에 있고, 가려고 하는 곳의 좌표가 (0,0,3,0,0,3,0,0,3,0,0)이라고 하자. 워프 궤도는 3075년에 (0,0,1,0,0,1,0,0,1,0,0)가 발견되었고, 3082년에 (0,0,1,0,0,2,0,1,0,0,0)이 발견되었다고 하자. 그럼, 3075년에 발견된 워프 궤도를 3번 이용하면 바로 갈 수 있다.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 다음과 같이 이루어져 있다.

  • 첫째 줄에 워프 궤도의 개수 n < 1000이 주어진다.
  • 둘째 줄에는 상근이가 여행을 시작하는 위치 좌표가 주어진다. 11차원이기 때문에 좌표는 총 11개의 숫자로 이루어져 있고, 문제에서 설명한 바와 같이 가능한 좌표값은 0과 10사이이다.
  • 셋째 줄에는 상근이가 가려고 하는 곳의 위치 좌표가 주어진다. 이 좌표는 시작 위치와는 항상 다르다.
  • 넷째 줄부터 n개 줄에는 총 12개의 숫자가 주어진다. 처음 11개 숫자는 워프 궤도의 좌표이며, 마지막 숫자는 그 궤도가 발견된 연도이다. 연도는 3075보다 크거나 같고, 100000보다 작거나 같다.

출력

각 테스트 케이스에 대해서 몇 년이 되면 상근이가 워프 궤도를 이용해서 도착 지점에 갈 수 있는지 출력한다. 만약, 세월이 아무리 흘러도 갈 수 없다면 "unreachable"을 출력한다.

예제 입력

3
2
0 0 0 0 0 0 0 0 0 0 0
0 0 3 0 0 3 0 0 3 0 0
0 0 1 0 0 1 0 0 1 0 0 3075
0 0 1 0 0 2 0 1 0 0 0 3082
2
0 0 0 0 0 0 0 9 0 0 0
0 0 4 0 0 6 0 0 2 0 0
0 0 1 0 0 1 0 0 1 0 0 3075
0 0 1 0 0 2 0 1 0 0 0 3082
3
0 0 0 0 0 0 0 0 0 0 0
0 0 4 0 0 6 0 0 3 0 0
0 0 1 0 0 1 0 0 1 0 0 3075
0 0 1 0 0 2 0 1 0 0 0 3082
1 2 3 4 5 6 7 5 4 3 2 3093

예제 출력

3075
3082
unreachable

힌트