题目背景

小 L 有许多喜欢的游戏角色，他把这些游戏角色按照一定的关系联系起来。这些游戏角色和他们之间的关系构成了一棵树，小 L 把这棵树称之为「关系树」。

题目描述

关系树是由 $n$ 个点和 $n-1$ 条无向边组成的一棵树。

对于一张给定的图 $G$，定义图 $G$ 对于点集 $E$ 的 顶点导出子图 为点集 $E$ 和所有的 两个端点都属于 $E$ 且属于原图 $G$ 的边组成的图。

定义一张图是 整洁的，当且仅当图中任意两点 $u,v$，$u$ 和 $v$ 不连通 或 距离不超过 $k$。

小 L 想要知道对于一组 $l,r(l \leq r)$，有多少对 $(a,b)$，满足 $l\leq a\leq b\leq r$，且所有序号在 $a$ 和 $b$ 之间（包括 $a,b$）的点组成的顶点导出子图是 整洁的。不仅如此，他还想问你所有的区间长度（即 $b-a+1$）之和。

因为小 L 喜欢问问题，所以你一共需要回答 $q$ 组询问。

输入格式

第一行有三个整数 $n$，$q$，$k$，意义如上。

接下来 $n-1$ 行，每行两个整数 $u$，$v$，描述一条边。

接下来 $q$ 行，每行两个整数 $l$，$r$，表示一组询问。

输出格式

$q$ 行，每行两个整数，依次为满足的 $(a,b)$ 组数和所有的区间长度之和。

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

6 10
10 20
14 30

提示

样例 1 解释

形成的关系树如图

满足的 $(a,b)$ 有 $(1,1),(1,2),(1,3),(1,4),(2,2),(2,3),(2,4),(2,5),(3,3),(3,4),(3,5),(4,4),(4,5),(5,5)$。

三组询问的答案依次为 $6,10$，$10,20$，$14,30$。

数据规模与约定

本题采用捆绑测试。

• Subtask 1 ( $10\%$ )：$n\leq 2000$。
• Subtask 2 ( $30\%$ )：$n\leq 2\times 10^4$，形成的关系树为一条链。
• Subtask 3 ( $60\%$ )：$n\leq 2\times 10^4$。
• Subtask 4 ( 加强版数据，时限 $4.5s$ )：无特殊限制。

对于 $100\%$ 的测试点，保证 $1\leq n \leq 8\times 10^4$，$1\leq q \leq 10^5$，$0\leq k <n$，$1\leq u,v,l,r \leq n$。