在一块场地上一些运动员在训练跑步。场地是由 \(n\) 个休息室和 \(n - 1\) 条双向道路组成的树形结构。每条道路连接两个休息室，道路的两侧都是墙壁。

有 \(m\) 个运动员同时在这块场地上训练跑步。第 \(i\) 个运动员从第 \(a_i\) 个休息室出发，出发时面朝第 \(b_i\) 个休息室。为了避免迷路，运动员在场地内训练时，总是右手贴着墙跑步。例如，下图是场地的俯视图，如果运动员从 \(1\) 号休息室出发，且出发时面朝 \(3\) 号休息室，那么他将会沿着 \(1,3,5,3,6,3,1,4,1,2,1,\dots\) 的路线循环跑步。

根据教练的安排， 所有运动员每天必须刚好跑 \(p\) 条道路。每天跑步结束后，每个运动员都会将自己跑过的最后一条道路封堵，使双向都无法通行。如果有多个运动员跑过的最后一条道路相同，则这条道路会被其中编号最小的一个运动员封堵。到了下一天，每个运动员会接着前一天跑步结束时所在的休息室以及朝向，出发再跑 \(p\) 条道路。

道路被封堵会对后续的跑步路线产生影响。每个运动员都会在若干天后被困在某个休息室中，即这个休息室的所有道路都已经被封堵。一个运动员被困住之后，以后每天都不再跑步。

现在请你写一个程序计算：每个运动员是在哪一天结束后被困在了哪一个休息室中？每条道路在第几天被哪个运动员封堵？

第一行三个整数 \(n,m,p\) 。

为了方便描述树的平面形态，本题采用有根树的方式输入。根节点是第 \(1\) 个休息室，位于场地的最北方。输入数据的第 \(2\) 行包含 \(n - 1\) 个数 \(f_2,f_3,\cdots,f_n\) ，表示 \(2\sim n\) 的父亲编号。每个节点的父亲都在自己的北方（可能偏东或偏西），兄弟关系的节点按照编号递增的顺序自西向东排列。

接下来 \(m\) 行，每行两个整数 \(a_i,b_i\) ，表示第 \(i\) 个运动员第一天出发时所在的休息室和朝向。保证休息室 \(a_i,b_i\) 有一条道路直接相连。

输出第 \(1\sim m\) 行，每行两个整数 \(x_i,y_i\) ，表示第 \(i(=1,2,\cdots,n)\) 个运动员在第 \(x_i\) 天结束后被困在了第 \(y_i\) 个休息室中。

接下来 \(n-1\) 行，每行两个数 \(z_i,w_i\) ，表示第 \(i(=2,3,\cdots,n)\) 个休息室与父亲之间的道路时在第 \(z_i\) 天被第 \(w_i\) 个运动员封堵。如果一条道路一直不会被封堵则 \(z_i=w_i=0\) 。

样例1解释

训练场地的地形，见“问题描述”中的插图

• 第 \(1\) 天，运动员 \(1\) 的路线是 \(2\to1\to3\to5\) ，运动员 \(2\) 的路线是 \(4\to1\to2\to1\) ；
  训练结束后，运动员 \(1\) 封堵休息室 \(3,5\) 之间的道路，运动员 \(2\) 封堵休息室 \(2,1\) 之间的道路；
  从此，运动员 \(1\) 被困在休息室 \(5\) 。
• 第 \(2\) 天，运动员 \(2\) 的路线是 \(1\to3\to6\to3\) ，然后封堵休息室 \(6,3\) 之间的道路。
• 第 \(3\) 天，运动员 \(2\) 的路线是 \(3\to1\to4\to1\) ，然后封堵休息室 \(4,1\) 之间的道路。
• 第 \(4\) 天，运动员 \(2\) 的路线是 \(1\to3\to1\to3\) ，然后封堵休息室 \(1,3\) 之间的道路；
  从此，运动员 \(2\) 被困在休息室 \(3\) 。

样例2解释

训练场地如图所示

• 运动员 \(1\) ：
  第 \(1\) 天的路线是 \(1\to6\to7\to6\to1\to8\) ，
  第 \(2\) 天的路线是 \(8\to10\to8\to10\to8\to10\) 。
• 运动员 \(2\) ：
  第 \(1\) 天的路线是 \(9\to1\to2\to3\to2\to4\) 。
• 运动员 \(3\) ：
  第 \(1\) 天的路线是 \(10\to8\to1\to9\to1\to2\) ，
  第 \(2\) 天的路线是 \(2\to3\to2\to5\to2\to3\) 。

数据范围

每组测试数据范围如下表所示

• 性质 \(\mathrm{A}\) ：每个休息室的父亲 \(f_i=1\) ，所有运动员出发时的休息室 \(a_i=1\) ，且 \(p\) 是偶数。
• 性质 \(\mathrm{B}\) ：每个休息室的父亲 \(f_i =i-1\) 。

所有测试数据：
\(1\leq n\leq 250\;000\)
\(0\leq m\leq 50\;000\)
\(1\leq p\leq 10^9\)
\(1\leq f_i\leq i-1\)
\(1\leq a_i,b_i\leq n\)
保证休息室 \(a_i,b_i\) 有一条道路直接相连