유전자 재배열

서로 가까운 두 종, 예를 들어 양배추와 순무의 유전체(게놈)에는 비슷한 유전자들이 들어 있을 수 있습니다. 다만 진화 과정에서 일어난 유전체 자리바꿈 때문에, 같은 유전자라도 각 유전체 안에서 나타나는 순서는 서로 다를 수 있습니다.

여러분이 할 일은 두 유전자 서열을 비교하여 두 유전체에 공통으로 존재하는 구간을 찾는 것입니다. 여기서 공통 구간이란, (순서는 달라도 되므로) 두 유전체에서 정확히 같은 유전자 집합을 담고 있는 연속된 위치 구간을 뜻합니다.

이 문제에서 유전자는 염기 A, C, G, T의 나열로 표기하지 않고, 각각 하나의 정수로 부호화합니다. 비교하는 두 유전체는 같은 정수들로 이루어지며, 각 유전체는 $1, 2, \ldots, N$ 의 순열입니다. 여기서 $N$ 은 유전체의 길이입니다.

공통 구간 $[i, j]$ 는 $1 \le i \le j \le N$ 을 만족하는 구간으로, 첫 번째 유전체의 $i$ 번째부터 $j$ 번째까지 위치에 있는 유전자(정수)들의 집합이 두 번째 유전체의 같은 위치들에 있는 유전자들의 집합과 정확히 일치하는 구간을 말합니다. (순서는 달라도 됩니다.)

출력해야 하는 것은 최소 공통 구간입니다. 이는 유전체 전체 $[1, N]$ 을 연속된 공통 구간들로 가장 잘게 나눈 분할의 각 조각을 뜻합니다. 구체적으로, 첫 번째 유전체의 앞에서부터 $k$ 개 유전자의 집합과 두 번째 유전체의 앞에서부터 $k$ 개 유전자의 집합이 같아질 때마다 위치 $k$ 바로 뒤에 경계를 둡니다. (위치 $0$ 과 $N$ 은 항상 경계입니다.) 이렇게 만들어진, 이웃한 두 경계 사이의 각 구간이 하나의 최소 공통 구간입니다.

첫 번째 줄에는 뒤따르는 테스트 케이스의 개수를 나타내는 정수 하나가 주어집니다. 각 테스트 케이스의 형식은 다음과 같습니다.

• 한 줄에 유전체의 길이를 나타내는 정수 $N$ 이 주어집니다. ($1 \le N \le 100{,}000$)
• 한 줄에 첫 번째 유전체를 나타내는 $1, \ldots, N$ 의 순열이 주어집니다.
• 한 줄에 두 번째 유전체를 나타내는 $1, \ldots, N$ 의 순열이 주어집니다.

같은 줄에 있는 정수들은 공백 하나로 구분됩니다.

각 테스트 케이스마다, 두 유전체에 공통인 최소 공통 구간들을 왼쪽에서 오른쪽 순서로 나열하여 한 줄에 출력합니다. 각 구간은 시작 위치와 끝 위치를 붙임표로 이은 i-j 형태로 쓰고, 이웃한 구간은 공백 하나로 구분합니다.