Gene Shuffle

Interview

Time limit1sMemory limit128 MB

Summary

Two permutations of 1..N are given; split [1,N] into the shortest pieces where each piece holds the same set of genes in both. - use plain English

Level: Medium5 of 10
Topics: Prefix sum, Hash map
Solved: No attempts yet

Problem

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.

Input

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.

Output

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.

Examples3

Example 1

Input

2
10
1 2 3 6 4 7 5 8 9 10
3 2 1 4 5 6 7 8 10 9
5
2 1 4 5 3
2 4 5 3 1

Expected output

1-3 4-7 8-8 9-10
1-1 2-5

Example 2
Input
```
1
1
1
1
```
Expected output
```
1-1
```

Example 3

Input

Expected output

1-1 2-2 3-3 4-4 5-5