题目描述

救赎

虚无

重生

你为何哭泣？

Luvia 给你一棵包含 $n$ 个节点（编号 $1$ ~ $n$）的树，以及 $q$ 次查询 $l,\ r,\ x$。

你需要回答：当树的根节点为 $x$ 时，编号在 $l$ ~ $r$ 范围内的所有节点的最近公共祖先（LCA）。

（注：LCA 指深度最深的公共祖先节点）

输入格式

第一行两个整数 $n$，$q$（$1 ≤ n,\ q ≤ 3×10^5$）。

接下来 $n-1$ 行，每行两个整数 $x$，$y$（$1 ≤ x,\ y ≤ n$），表示节点 $x$ 和 $y$ 之间有一条边。

保证输入的边构成一棵树。

接下来 $q$ 行，每行一个查询 $l,\ r,\ x$（$1 ≤ l ≤ r ≤ n$，$1 ≤ x ≤ n$）。

输出格式

输出 $q$ 行，第 $i$ 行包含一个整数，表示第 $i$ 次查询的答案。

样例

8 6
1 2
1 3
1 7
2 4
3 5
3 6
5 8
5 6 1
1 4 7
6 8 4
1 8 4
4 7 2
5 5 3

3
1
1
4
2
5