Gene Shuffle

The genomes of two related species — for example, cabbage and turnip — may share many of the same genes. Because genome transpositions occur during evolution, the order in which those genes appear can differ from one genome to the other.

Your task is to compare two gene sequences and find the segments that are common to both genomes: contiguous stretches of positions that contain exactly the same set of genes in both genomes, even though the genes may be arranged in a different order.

Here a gene is not spelled out with the bases A, C, G, and T. Instead, each gene is encoded as a single integer. The two genomes being compared use the same integers: each genome is a permutation of the numbers $1, 2, \ldots, N$, where $N$ is the length of the genome.

A common segment $[i, j]$ is an interval with $1 \le i \le j \le N$ such that positions $i$ through $j$ of the first genome contain exactly the same set of genes (integers) as positions $i$ through $j$ of the second genome, possibly in a different order.

You must report the minimal common segments: the pieces of the finest partition of the whole genome $[1, N]$ into consecutive common segments. Concretely, place a boundary right after position $k$ whenever the first $k$ genes of the first genome form the same set as the first $k$ genes of the second genome (positions $0$ and $N$ are always boundaries). Each interval between two consecutive boundaries is one minimal common segment.

The first line contains a single integer: the number of test cases that follow. Each test case has the following format:

• One line with an integer $N$ with $1 \le N \le 100{,}000$: the length of the genome.
• One line with a permutation of the integers $1, \ldots, N$, giving the first genome.
• One line with a permutation of the integers $1, \ldots, N$, giving the second genome.

On each line, the integers are separated by single spaces.

For each test case, print a single line listing the minimal common segments common to the two genomes, ordered from left to right. Write each segment as its start and end position joined by a hyphen (i-j), and separate consecutive segments with a single space.