Ants and the Ladybug

Memory limit: 32 MB

As we all know ants are able to raise aphides. Aphides produce sweet honey dew, which is drank by ants. Ants defend aphides against the bitterest enemies of theirs - ladybugs. On the tree near to the anthill there lives such culture of aphides. Aphides feed on leaves and ramifications of the tree. There are ant-guards (numbered from to ). A ladybug threatens the culture, she always sits in places where aphides appear, (i.e. on leaves or ramifications). When a ladybug sits on the tree guard-ants set off in her direction in order to chase her away. They comply with the following rules:

• between any two chosen places on the tree (leaves or ramifications) there is exactly one way to go without turning back - each of the ants starts going along such route to the place of ladybug's landing,
• if there is an ant in the place of the ladybug's landing, the ladybug takes off immediately,
• if there is another ant on the route to the ladybug landing place, then the ant that is farther from the ladybug stops its wandering and remains on its current position,
• if two or more ants try to get to the same ramification of the tree, only one reaches it - the one with the least number, the others stay on their positions (leaves or ramifications),
• an ant which gets to the place of ladybug's landing chases it away and stays on this position.

Task

Write a program which:

• reads from the standard input the description of the tree, the start positions of ants, and places where the ladybug lands,
• for each ant finds its final position and number of times this ant chased the ladybug away,
• writes the result to the standard output.

Input

In the first line of the standard input there is one integer , equal to the number of leaves and ramifications on the tree, . We assume that leaves and ramifications are numbered from to . Each of the following lines describes a branch --- a description consist of two integers and , it means that a given branch connects places and of the tree. The branches allow to get from one place to the another. In the -st line there is one integer , and ; is equal to number of ants that guard the tree. In each of the following lines one positive integer (not greater than ) is written. An integer written in -th line is a start position of the -th ant. There is no position on the tree (neither leaf nor ramification) with more than one ant. In the line there is one integer , , says how many times a ladybug lands on the tree. In each of the following lines one positive integer (not greater than ) is written. These numbers describe the places in which the ladybug successively lands.

Output

Your program should write lines to the standard output. In the -th line there should be written two integers separated by a single space - the final position of the -th ant (number of a ramification or a leaf) and the number indicating how many times the -th ant chased the ladybug away.

Example

For the input data:

4
1 2
1 3
2 4
2
1
2
2
2
4

the correct result is:

1 0
4 2

Task author: Krzysztof Lorys.