题目描述

给一棵 $n$ 个点的带边权的树，你需要维护一个序列，支持三种操作:

1. 在序列末尾插入一个点 $x$
2. 删除末尾的点
3. 求目前序列中 $[l,r]$ 区间内距离 $x$ 最远的点的距离

输入格式

第一行一个正整数 $n$。

接下来 $n-1$ 行每行三个正整数 $a,b,c$，表示树上有 $(a,b)$ 这条边，长度为 $c$。

接下来一行一个正整数 $q$。

接下来 $q$ 行每行一次操作：

• 1 x，表示操作一。
• 2，表示操作二。
• 3 l r x，表示操作三。

输出格式

若干，每行一个非负整数，为询问的答案。

样例

输入

5
1 2 -10
2 3 11
2 4 -2
1 5 -1
9
1 2
1 5
1 4
1 3
3 1 4 4
3 3 4 1
2
1 1
3 1 4 4

输出

9
1
0

数据范围

本题时间限制 $14$ 秒，空间限制 $256\text{MB}$。

对于所有数据，$1\le n\le 2\times 10^5$，$1\le q\le 5\times 10^5$，$-1000\le c\le 1000$，保证操作合法。

Subtask 1 共 $10$ 分，满足 $1\le n,q\le 5000$。

Subtask 2 共 $50$ 分，满足 $1\le n,q\le 10^5$。

Subtask 3 共 $40$ 分，没有附加限制。