Problem A
Åboulevarden

Bars along Aarhus River. Source: Kenny Arne Lang Antonsen, CC BY-SA 4.0

Your study group is planning a pub crawl in the bars along one side of the Aarhus River.

All the bars are nice and inviting, but each serves only one kind of beer. The members of your group have different, varying, and even conflicting preferences in beverages, so you switch bars often.

You have a map of the $N$ bars located along the river, and want to construct a navigation system for the night out. The portion of the river along which bars are located crosses through the inner part of town in a relatively straight fashion, and every bar takes up about the same amount of space, so you model the positions of the bars as evenly spaced points on a straight line.

When the system is finished, it should take as input your group’s current location (i.e., the current bar) and the name of a beer, and return directions to a nearest bar serving that beer. This way, you will have a foolproof way to continue the crawl even when your natural navigation skills inevitably fall short.

Input

The first line contains an integer $1 \leq N \leq 150\, 000$, the number of bars along the river. Then follow $N$ lines, one for each bar. The $i$th line contains the name of the beer served at the $i$th bar. Each beer name consists of upper- or lowercase letters from the English alphabet, digits, and/or hyphens.

The next line contains an integer $1 \leq Q \leq 50\, 000$, the number of navigation queries. Then follow $Q$ navigation queries, each on a separate line. Each query consists on an integer $X$ with $0 \leq X < N$, specifying a bar, and a beer name $S$. There is at least one bar serving $S$. (This may be include bar $X$.)

You can assume that the input file is no larger than 10 MiB.

Output

For each navigation query $X$, $S$, output a line with an integer $D$ representing the navigation result.

There should be a bar at location $X + D$ serving beer $S$. Additionally, among such valid $D$, you should output a result that requires you to pass the fewest number of bars (i.e., the absolute value $|D|$ should be minimised). If there are still multiple options any one will be accepted.

5
Limfjordsporter
Hof
X-mas
Hof
1664
3
1 Limfjordsporter
0 Hof
1 1664

-1
1
3

3
Top
Gulddame
Limfjordsporter
3
1 Gulddame
0 Gulddame
2 Gulddame

0
1
-1

7
Juleren
Giraf
Elephant
NightingAle
Juleren
Elephant
Giraf
4
0 Elephant
3 Juleren
4 Giraf
6 NightingAle

2
1
2
-3