Ants and the Ladybug

Ants farm aphids: the aphids give off sweet honeydew that the ants drink, so the ants protect the aphids from their fiercest enemy, the ladybug. On a tree beside the anthill lives a colony of aphids that feeds on the tree's leaves and branch points.

The tree has $n$ places, its leaves and branch points, numbered from $1$ to $n$ and joined by $n-1$ branches, so between any two places there is exactly one simple route. The tree is patrolled by $k$ guard-ants, numbered from $1$ to $k$; each ant stands on a place of its own, and no place holds more than one ant.

A ladybug lands on one of the places. The ants then try to chase her away, and they all move at the same speed: crossing one branch takes one unit of time. Each landing is resolved by the following rules:

• If an ant already stands on the ladybug's place, she takes off at once, that ant is credited with chasing her away, and no ant moves for this landing.
• Otherwise every ant heads toward her along the unique route from its place to hers, but an ant sets off only if no other ant stands on that route (its own place excepted); an ant that is blocked this way does not move at all and stays where it is.
• All ants that set off advance together, one branch per unit of time.
• If two or more ants would enter the same place at the same moment, only the lowest-numbered of them enters it; each of the others stops on its place and wanders no further.
• The moment an ant reaches the ladybug's place it chases her away and stays there; at that instant every other ant also stops on the place it currently occupies.

The ladybug is stubborn and keeps returning, landing on the tree again and again. Each time she lands, the ants set off afresh from wherever they now stand.

Write a program that, given the tree, the ants' starting places, and the ladybug's successive landing places, reports for each ant its final place and how many times that ant chased the ladybug away.

The first line holds one integer $n$ ($1 \le n \le 5000$), the number of places. Each of the next $n - 1$ lines holds two integers $a$ and $b$ ($1 \le a, b \le n$): a branch joins places $a$ and $b$.

The next line holds one integer $k$ ($1 \le k \le 1000$ and $k \le n$), the number of ants. Each of the following $k$ lines holds one integer in $[1, n]$: the starting place of the $i$-th ant. All starting places are distinct.

The next line holds one integer $l$ ($1 \le l \le 500$), how many times the ladybug lands. Each of the following $l$ lines holds one integer in $[1, n]$: a landing place, given in the order the landings happen.

Print $k$ lines. On the $i$-th line print two integers separated by a single space: the final place of the $i$-th ant and the number of times that ant chased the ladybug away.

The picture below shows the tree of the first example.

In that example the branches are $1-2$, $1-3$, and $2-4$; ant $1$ starts at place $1$ and ant $2$ starts at place $2$. The ladybug first lands on place $2$: ant $2$ is already there, so it chases her away at once and nobody moves. She then lands on place $4$: the route from ant $1$ (place $1$) to place $4$ runs through place $2$, where ant $2$ stands, so ant $1$ stays put, while ant $2$ walks from place $2$ to place $4$ in one step and chases her away again. In the end ant $1$ is still at place $1$ with $0$ chases, and ant $2$ is at place $4$ with $2$ chases.