S 國(guó)有 $N$ 個(gè)城市，編號(hào)從 $1$ 到 $N$。城市間用 $N-1$ 條雙向道路連接，滿足從一個(gè)城市出發(fā)可以到達(dá)其它所有城市。每個(gè)城市信仰不同的宗教，如飛天面條神教、隱形獨(dú)角獸教、絕地教都是常見(jiàn)的信仰。為了方便，我們用不同的正整數(shù)代表各種宗教，S 國(guó)境內(nèi)總共有 $C$ 種不同的宗教。
S 國(guó)的居民常常旅行。旅行時(shí)他們總會(huì)走最短路，并且為了避免麻煩，只在信仰和他們相同的城市留宿。當(dāng)然旅程的終點(diǎn)也是信仰與他相同的城市。S 國(guó)政府為每個(gè)城市標(biāo)定了不同的旅行評(píng)級(jí)，旅行者們常會(huì)記下途中（包括起點(diǎn)和終點(diǎn)）留宿過(guò)的城市的評(píng)級(jí)總和或最大值。
在 S 國(guó)的歷史上常會(huì)發(fā)生以下幾種事件：
1、$CC\;x\;c$：城市 $x$ 的居民全體改信了 $c$ 教；
2、$CW\;x\;w$：城市 $x$ 的評(píng)級(jí)調(diào)整為 $w$；
3、$QS\;x\;y$：一位旅行者從城市 $x$ 出發(fā)，到城市 $y$，并記下了途中留宿過(guò)的城市的評(píng)級(jí)總和；
4、$QM\;x\;y$：一位旅行者從城市 $x$ 出發(fā)，到城市 $y$，并記下了途中留宿過(guò)的城市的評(píng)級(jí)最大值。
由于年代久遠(yuǎn)，旅行者記下的數(shù)字已經(jīng)遺失了，但記錄開(kāi)始之前每座城市的信仰與評(píng)級(jí)，還有事件記錄本身是完好的。請(qǐng)根據(jù)這些信息，還原旅行者記下的數(shù)字。
為了方便，我們認(rèn)為事件之間的間隔足夠長(zhǎng)，以致在任意一次旅行中，所有城市的評(píng)級(jí)和信仰保持不變。

輸入的第一行包含整數(shù) $N$，$Q$ 依次表示城市數(shù)和事件數(shù)。
接下來(lái) $N$ 行，第 $i+1$ 行兩個(gè)整數(shù) $W_i$ ，$C_i$ 依次表示記錄開(kāi)始之前，城市 $i$ 的評(píng)級(jí)和信仰。
接下來(lái) $N-1$ 行每行兩個(gè)整數(shù) $x$，$y$ 表示一條雙向道路。
接下來(lái) $Q$ 行，每行一個(gè)操作，格式如上所述。

對(duì)每個(gè) $QS$ 和 $QM$ 事件，輸出一行，表示旅行者記下的數(shù)字。

5 6
3 1
2 3
1 2
3 3
5 1
1 2
1 3
3 4
3 5
QS 1 5
CC 3 1
QS 1 5
CW 3 3
QS 1 5
QM 2 4

8
9
11
3

數(shù)據(jù)范圍與提示：
對(duì)所有的數(shù)據(jù)，$Q≤10^5 , C≤10^5$ ，對(duì)所有 $QS$ 和 $QM$ 事件，起點(diǎn)和終點(diǎn)城市的信仰相同；在任意時(shí)刻，城市的評(píng)級(jí)總是不大于 $10^4$ 的正整數(shù)，且宗教值不大于 $C$。