输入长度为 $n$ 的串 $S$ ，求 $S$ 的最长双回文子串 $T$,即可将 $T$ 分为两部分$X$ ， $Y$ ， （ $∣X∣,∣Y∣ \geq 1$ ）且 $X$ 和 $Y$ 都是回文串。

有一颗 $n$（$n<20000$）个节点的树，每条边都有边权。接下来由聪聪和可可分别随即选一个点，如果两点之间简单路径上的边权和是 $3$ 的倍数，则判聪聪赢，否则可可赢。

聪聪非常爱思考问题，希望知道对于这张图自己的获胜概率是多少。

墨墨购买了一套 $N$ 支彩色画笔（其中有些颜色可能相同）。墨墨会向你发布如下指令：

1. Q L R 代表询问你从第 $L$ 支画笔到第 $R$ 支画笔中共有几种不同颜色的画笔。

2. R P Col 把第 $P$ 支画笔替换为颜色 $Col$ 。