99052 - 历史

通过次数

1

提交次数

1

Time Limit : 1 秒
Memory Limit : 128 MB

历史里有个东西“我的附庸的附庸不是我的附庸”(非现代·欧洲) 又有一个东西是“我的附庸的附庸还是我的附庸”(非现代·中国) 现在给你 N 对 X,Y 的关系(意义为 Y 为 X 的附庸),求 M 个被查询者分别在欧洲以及中国有几个附庸

Input

共 n+3 行

第 1 行:整数 n

第 2~n+1 行:整数对 X,Y

第 n+2 行:一个整数 m

第 n+3 行:共 m 个整数表示待查询者

Output

共 m 行 每行两个数,分别表示被查询者分别在欧洲以及中国有几个附庸 若数据出错(即此人没有出现过)请输出按照其无附庸处理

Examples

Input

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

Output

2 2
0 0
0 0
1 3

Hint

10%的数据:0≤n≤10 40%的数据:0≤n≤5000 100%的数据:0≤n≤10000;0≤m≤30000;0≤出现的所有人的编号≤5000