树

又是人民群众喜闻乐见的数据结构构题！

题目想必大家都听说过。给定一棵有根树，支持 $8$ 个操作：

1. 令 $x$ 为树的根。
2. Link - Cut：即把点 $x$ 的父亲改为 $y$。
3. 把点 $x$ 的权增加 $v$。
4. 查询点 $x$ 的权。
5. 把 $x$ 到 $y$ 的路径上的所有点的权增加 $v$。
6. 查询 $x$ 到 $y$ 上的所有点的权的最小值。
7. 把 $x$ 这棵子树中的所有点的权增加 $v$。
8. 查询 $x$ 这棵子树中所有点的权的最小值。

输入格式

第一行两个数 $n, m$，表示树的大小为 $n$，操作数为 $m$。

接下来 $n$ 行，第 $i+1$ 行有两个数 $f, v$，表示点 $i$ 的父亲是 $f$，初始权值为 $v$。保证 $f<i$。若 $f=0$，则 $i$ 为根。

接下来 $m$ 行，每行为以下格式之一，且恰好与题目描述中的 $8$ 个操作对应：

1. E x
2. LC x y
3. CV x v
4. QV x
5. CP x y v
6. QP x y
7. CS x v
8. QS x

保证所有操作合法。

输出格式

对于 QV、QP、QS，输出对应的答案。

Samples

6 10
0 620
1 540
2 719
3 8
4 740
1 234
CP 3 4 87
E 3
LC 2 4
QP 6 1
QV 6
CV 5 663
LC 6 5
QS 3
CS 4 328
QS 6

234
234
95
562

数据范围与规模

对于 $100\%$ 的数据，满足 $n\le 10^5,m \le 10^5$。