题目背景

本题时限较小，请采用较快的读入方式，以下是出题人提供的快读模板：

typedef long long LL;
inline LL read(){
	register LL x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
	return x*f;
}

当然你也可以采用自己的读入方法。

题目描述

在一次聚会上，一共有 $n$ 名学生，他们的编号分别为 $1,2,3,\cdots,n$，他们被分成 $k$ 组，组的编号分别为 $1,2,3,\ldots,k$。

小 V 老师负责组织这场聚会，在聚会的开始，第 $i$ 名学生被分到了第 $a_i$ 组，并拿到了 $b_i$ 颗糖果。（小 V 既不属于任何组别，也没有任何糖果。在接下来的活动中，小 V 作为组织者的身份。）

这一次聚会一共有 $m$ 轮活动，对于每一轮活动，可能发生以下两种情况之一：

1. Change X Y，表示把所有组别为 $X$ 的学生的组别改为 $Y$（修改后 $X$ 即为空组），并把组 $X$ 删除。
2. Query，表示小 V 想要知道，如果把剩下的组合并（定义见下） 成一大组，那么这一大组内拥有最多糖果的学生的糖果数最少可能是多少。

定义一个组 $G_i$ 的大小就是这个组内含有学生的个数，记为 $S_i$。

合并：将大小为 $S_1(S_1>0)$ 的组 $G_1$ 合并到大小为 $S_2(S_2>0)$ 的组 $G_2$，其中 $G_1$ 组内所有学生拥有糖果数之和为 $f$，则：

1. 第一步，将原先 $G_1$ 中所有学生的糖果数都变为 $0$，并将他们的组别改为 $G_2$。
2. 第二步，将目前 $G_2$ 中每位学生（包括原先 $G_1$ 中的学生）的糖果数加上 $\dfrac{f}{S_1+S_2}$（糖果数不一定为整数块）。

注意：

1. $G_1$ 合并到 $G_2$ 的最后结果可能会与 $G_2$ 合并到 $G_1$ 的最后结果不同。
2. Query 中的合并不会真实发生。即在这一次情况过后，所有学生的糖果数与所在组与此次操作未发生前一致。

请将每次 Query 中的答案对 $10^9+7$ 取模。（可能是分数取模，如果不知道如何取模请见提示说明）

输入格式

第一行三个整数 $n,m,k$。

第二行 $n$ 个整数 $a_{1\ldots n}$。

第三行 $n$ 个整数 $b_{1\ldots n}$。

接下来 $m$ 行，每行对应一种情况。具体格式参见题目描述或输入输出样例。

输出格式

输出若干行整数表示答案。

3 3 2
1 1 2
3 4 5
Query
Change 2 1
Query

666666677
5

提示

【样例解释】

第一次 Query 时，将第二组合并到第一组，此时三名学生的糖果数分别为 $\dfrac{14}{3},\dfrac{17}{3},\dfrac{5}{3}$，糖果数最多的同学有 $\dfrac{17}{3}$ 块糖果，取到了最小值，对 $10^9+7$ 取模后为 $666666677$。

第二次 Query 时，所有学生都在同一组，而糖果数最多的同学有 $5$ 块糖果。

【数据范围】

对于 $100\%$ 的数据，满足 $1 \leq n \leq 10^6,\ 1\leq m \leq 2\times k-1,\ 1 \leq a_i\leq k \leq n,\ 1 \leq b_i \leq 10^5$。数据保证合法，初始时每组是非空的。

不熟悉有理数取模的请看此处。