Where Are My Genes

Scientists study how one species evolved into another by tracing how an ancestor's genome changed into a descendant's. Closely related species share many genes, and a good way to compare them is to see how the shared genes changed position.

One of the most common mutations that reorder a genome's genes is the reversal. Model a genome as a sequence of $N$ genes, where each gene is an integer from $1$ to $N$. A reversal reverses the order of a block of consecutive genes. It is described by two indices $(i, j)$ with $1 \le i \le j \le N$ and reverses the genes at positions $i$ through $j$. Applied to the genome $[g_1, \dots, g_{i-1}, g_i, g_{i+1}, \dots, g_{j-1}, g_j, g_{j+1}, \dots, g_N]$, it produces $[g_1, \dots, g_{i-1}, g_j, g_{j-1}, \dots, g_{i+1}, g_i, g_{j+1}, \dots, g_N]$.

For example, applying the reversal $(3, 6)$ to [1, 2, 3, 4, 5, 6, 7] gives [1, 2, 6, 5, 4, 3, 7]. Applying the reversal $(1, 3)$ after that gives [6, 2, 1, 5, 4, 3, 7].

A scientist wants to apply a series of reversals to a genome and then query the final position of several genes. Answer those queries.

The input contains several test cases.

• The first line of a test case contains an integer $N$ ($1 \le N \le 50000$), the number of genes in the genome. The genome initially holds the integers from $1$ to $N$ in increasing order.
• The second line contains an integer $R$ ($0 \le R \le 1000$), the number of reversals to apply.
• Each of the next $R$ lines contains two integers $i$ and $j$ ($1 \le i \le j \le N$) separated by a single space, describing one reversal.
• The next line contains an integer $Q$ ($0 \le Q \le 100$), the number of gene queries.
• Each of the next $Q$ lines contains one integer, a gene whose final position you must report.

The reversals are applied in the given order. The end of the input is a line containing $N = 0$, which must not be processed.

For each test case, print $Q + 1$ lines. The first line must contain the word Genome, then a single space, then the test case number (test cases are numbered starting from $1$). Each of the following $Q$ lines must contain a single integer: the final position of the corresponding queried gene.