题目描述

    随着网购在H国兴起,其物流业也随之开始发展。

    H国可共有$N$座城市,由$1 \sim N$编号,物流公司的总部设在1号城市。

    城市之间由$N-1$条单向主干道连接。从物流公司总部所在的城市出发,总能经过唯一的一条仅包含主干道的道路,到达其余$N-1$座城市。除此之外,城市间还有$M$条单向次干道。所有的道路间都不会构成环。

    为了减缓道路的压力,每单位货物经过道路$i$都会被收取$V_{i}$的费用。

    另外,每条道路还有一个额定运载量$W_{i}$。如果该条道路运输的货物少于$W_{i}$,则每少一单位货物要多被收取$P_{i}$的费用;如果该条道路运输的货物多于$W_{i}$,则每多一单位要多被收取$Q_{i}$的费用。

    随着环境的变化,主干道的额定运载量会随之发生一些变化。你的任务是帮助物流公司预算每一次运输的成本。

    你需要实现两种操作:

    (1)$C~x~y~k$,表示将城市$x$和城市$y$之间的主干道的额定运载量增加$k$

    (2)$Q~x~d$,表示询问将$d$单位的货物从物流公司总部运输到城市$x$花费的最小费用。

    注:如果某条边的额定运载量$W_{i}<0$,我们在运输货物时认为它的额定运载量为0,但实际的$W_{i}$值不变。

输入格式

    第一行2个整数$N$$M$

    接下来$N-1$行,描述$N-1$条主干道,每行6个整数$u,v,W_{i},V_{i},P_{i},Q_{i}$。其中$u,v$表示城市$u$$v$有一条单向道路。

    接下来$M$行,描述$M$条次干道,格式同上。

    接下来一个整数$T$,表示有$T$次操作。

    接下来$T$行,每行表示一个操作,格式见题目描述。

输出格式

    对于每一次类型(2)的询问,输出最小费用。

样例输入

6 1
1 2 2 2 2 2
1 3 3 3 2 2
2 4 2 2 1 2
2 5 3 1 2 3
5 6 3 3 2 1
3 6 2 1 1 1
3
Q 6 6
C 6 2 -1
Q 6 6

样例输出

35
34

数据范围与约定

  • 对于100%的数据:$0 \leq W_{i} \leq 1000,0 \leq V_{i},P_{i},Q_{i} \leq 20,|k| \leq 100,0 \leq d \leq 1000$
  • 保证类型(2)的询问不会很多,计算过程和最终结果都不会超过maxlongint。