U258758 神秘石头（smst）

地上有些申必石头。

牟德强用这些申必石头摆成一颗基环树，每个石头有一个申必值 $a_i$，和神秘值 $b_i$，定义两个石头 $u,v$ 的两种最短路径，分别为以 $a_i \times b_i$ 为点权的最短路$Dis_{u,v}$ 和以 $a_i+b_i$ 为点权的最短路 $diS_{u,v}$。 虽然牟德强很强，但是他外强中干，所以你需要帮助他完成以下操作： 1. `Ca u x` 将 $a_u$ 改为 $x$ 2. `Cb u x` 将 $b_u$ 改为 $x$ 3. `Qa u v` 查询 $Dis_{u,v}$ 4. `Qb u v` 查询 $diS_{u,v}$ 5. `L u v a b` 将 $u \rightarrow v$ 的路径删除，增加一个新申必石头编号为现在的申必石头数，权值为 $a,b$，删除边 $u \rightarrow v$，增加 $u \rightarrow newstone \rightarrow v$

第一行一个数 $N$ 表示石头数。 接下来 $N$ 行，每行两个数 $u,v$ 表示有边 $u \rightarrow v$。 接下来 $N$ 行每行 $2$ 个数分别是 $a_i$ 和 $b_i$。 接下来一行一个数 $M$ 表示操作个数。 接下来 $M$ 行，形式如上。

对于每一个询问输出一行答案。

| 子任务 | $N$ | $M$ | 特殊性质 | | :-----------: | :-----------: | :-----------: | :-----------: | | $1$ | $\le2$ | $=1$ | | | $2$ | $\le3$ | $\le3$ | | | $3$ | $\le4$ | $\le4$ | 没有操作 $3,4$ | | $4$ | $\le5$ | $\le5$ | 没有操作 $5$ | | $5$ | $\le100$ | $=1$ | | | $6$ | $\le500$ | $\le 500$ | 没有操作 $3,4$ | | $7$ | $\le10^3$ | $=1$ | | | $8$ | $\le10^3$ | $\le500$ | 没有操作 $5$ | | $9$ | $\le10^3$ | $\le10^3$ | 基环树只有环 | | $10$ | $\le10^3$ | $\le10^3$ | 没有操作 $1,2,5$ | | $11$ | $\le10^5$ | $=1$ | | | $12$ | $\le10^5$ | $\le10^3$ | 没有操作 $5$ | | $13$ | $\le10^5$ | $\le10^5$ | 基环树只有环 | | $14$ | $\le10^5$ | $\le10^5$ | 基环树只有环 | | $15$ | $\le10^5$ | $\le10^5$ | 没有操作 $3,4$ | | $16$ | $\le10^5$ | $\le10^5$ | 没有操作 $1,2,5$ | | $17$ | $\le10^5$ | $\le10^5$ | 没有操作 $1,2$ | | $18$ | $\le10^5$ | $\le10^5$ | 没有操作 $5$ | | $19$ | $\le10^5$ | $\le10^5$ | $a_i,b_i \le 1$ | | $20$ | $\le10^6$ | $\le10^6$ | 没有操作 $3,4$ | 对于所有数据有 $2 \le N,M \le 10^6 ,1 \le a_i,b_i \le 10^9$。