题目背景

即使是像萝卜这样不起眼的小木头，也有被人喜欢的日子呢！

帽子的表白真是突如其来，小萝卜拼尽全力才战胜了自己上扬的嘴角，没有在上课划水的时候笑出来。

今年的 2.14，终于！可以！两个人过了！

题目描述

帽子要摘一些小萝卜最喜欢的花装点礼物。

小萝卜最喜欢的花长在一棵根为 $1$ 的树上，其中每个节点都有一朵花。当帽子从点 $u$ 开始摘花时，花的芳香度 $w_v$ 定义为 $\operatorname{dis}(u,v)$，也即 $u$ 到 $v$ 的最短距离。帽子只能摘下一朵花。

帽子只有 $t$ 秒的时间。具体的，他从 $u$ 开始沿着边移动，当他向上爬一条边（即远离根）时消耗 $1$ 单位时间，向下滑一条边（即接近根）时不消耗时间，全过程中剩余时间不能少于 $0$。

小萝卜有 $q$ 个问题，每次形如：帽子从点 $x_i$ 出发，有 $t_i$ 时间，摘的花的最大芳香度是多少。各个询问相互独立。

特别的，有时候小萝卜会在帽子摘完花后才会问下一个问题，所以在一些测试点中你需要强制在线。

输入格式

第一行两个正整数 $n,q,d$，表示树的节点个数、询问个数、与是否强制在线。

接下来 $n-1$ 行，每行两个正整数 $u_i,v_i$，表示树上 $u_i,v_i$ 之间有一条边。

接下来 $q$ 行，每行两个非负整数 $x_i,t_i$，表示一组询问。特别的，若 $d=1$，设上一组询问的答案为 $ans$（第一组询问为 $0$），你需要将 $x_i,t_i$ 异或上 $ans$ 得到真实询问。

输出格式

$q$ 行每行一个非负整数，表示每个询问的答案。

5 3 0
1 2
1 3
3 4
4 5
1 2
1 4
2 2

2
3
3

10 5 1
1 2
1 3
3 4
2 5
4 6
4 7
7 8
8 9
9 10
1 0
4 2
2 4
2 1
8 0

0
4
3
2
8

提示

【样例解释】

对于样例 $1$，三个询问分别如下：

• 从 $1$ 出发，体力值为 $2$。此时能摘下的其中一朵芳香度最大的花是 $4$，芳香度为 $2$。帽子可以向上爬 $2$ 条边到达 $4$。
• 从 $1$ 出发，体力值为 $4$。此时能摘下的其中一朵芳香度最大的花是 $5$，芳香度为 $3$。帽子可以向上爬 $3$ 条边到达 $5$。
• 从 $2$ 出发，体力值为 $2$。此时能摘下的其中一朵芳香度最大的花是 $4$，芳香度为 $3$。帽子可以先向下滑一条边到 $1$，再向上爬 $2$ 条边到达 $4$。

对于样例 $2$，暂时不能给你一个明确的答复。

【数据范围】

本题开启捆绑测试。

子任务	分数	$n,q\le$	$d=$	特殊性质
$1$	$20$	$10^3$	$0$
$2$	$10$	$2\times10^5$		$\forall i,u_i+1=v_i$
$3$	$20$			$\forall i,t_i=n$
$4$
$5$	$30$		$1$

对于 $100\%$ 的数据，$1\le n,q\le 2\times10^5,d\in\{0,1\},1\le x_i\le n,0\le t_i\le n$。