该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

我们大家都知道：因为蚜虫可以生产蜂蜜滴来供蚂蚁食用，所以有时蚂蚁会去保护蚜虫，尤其是对付他们的天敌瓢虫。

在一个树上有 n 个节点，和 k 只蚂蚁。一只瓢虫威胁了这棵树上蚜虫的安全， 于是蚂蚁们出动了。这个瓢虫总会停留在树上的某一个节点，一旦瓢虫着陆了，所有的 k 只蚂蚁对从他们当前的位置出发，前往瓢虫的位置（去赶走瓢虫）。我们可以认为整个过程遵循如下规则：

• 这棵树上的任何两个节点之间有且仅有一条路，所有的蚂蚁沿着唯一的路径前往瓢虫停靠的位置。
• 如果有一只蚂蚁到达了瓢虫停靠的位置，瓢虫马上就被赶走了
• 如果有另外一只蚂蚁在某一只蚂蚁通往瓢虫的路径上，那么距离瓢虫较远的那个蚂蚁停止移动，停留在当前的节点上
• 如果有多只蚂蚁尝试进入同一个节点，只有编号最小的蚂蚁能够到达，其他的蚂蚁停留在他们当前的位置上
• 赶走瓢虫的那只蚂蚁会停留在瓢虫的位置上

瓢虫被赶走之后会停靠在树上的另外一个节点上。这是所有的蚂蚁会重新出发， 尝试再一次赶走瓢虫。为了简化过程，我们假设从一个节点移动到相邻的节点需要话费一个单位时间。

Input Format

• 第 1 行: 一个整数 n，表示树上的节点个数(1<=n<=5000)
• 第 2..N 行: 第 i+1 行包含了一个两个整数: A_i, B_i，表示从节点 A_i 到节点 B_i 有一条边直接相连。
• 第 N+1 行: 有一个整数 k，表示树上蚂蚁的只数(1<=k<=1000, k<=n)
• 第 N+2..N+1+k 行: 第 N+1+i 行有一个整数 P_i，表示第 i 只蚂蚁开始时的位置， 任何两个蚂蚁的初始位置不相同
• 第 N+2+k 行:有一个整数 h，表示瓢虫一共在树上停留了多少次。(1<=h<=500)
• 接下来的 h 行，每行一个整数，表示瓢虫依次停留的位置。

Output Format

输出一共包含 k 行，第 i 行有两个整数 C_i 和 D_i。分别表示第 i 个蚂蚁最终停留的位置和这个蚂蚁赶走瓢虫的次数。

Sample

【输入样例】

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

【输出样例】

1 0
4 2

【输入解释】

第1只蚂蚁最终停留在第1个结点，赶走瓢虫的次数为 0次。
第2只蚂蚁最终停留在第4个结点，赶走瓢虫的次数为 2次。

Hint

1<=n<=5000;

1<=k<=1000, k<=n;

1<=h<=500.