题目描述

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

给定一棵有根树，支持如下 $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_i,v_i$，表示点 $i$ 的父亲是 $f_i$，初始权值为 $v_i$。保证 $f_i<i$。若 $f_i=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

保证所有操作合法。

Ȩֵv<=1000

输出格式

对于每个 QV、QP、QS 操作，输出一行一个整数，表示对应询问的答案。

样例输入

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

数据范围