Two Operations

在一次聚会上，一共有 $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$ 取模。（可能是分数取模，如果不知道如何取模请见**提示说明**） ## Input 第一行三个整数 $n,m,k$。 第二行 $n$ 个整数 $a_{1\ldots n}$。 第三行 $n$ 个整数 $b_{1\ldots n}$。 接下来 $m$ 行，每行对应一种情况。具体格式参见题目描述或输入输出样例。 ## Output 输出若干行整数表示答案。 [samples] ## Background **本题时限较小，请采用较快的读入方式，以下是出题人提供的快读模板：** ```cpp 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; } ``` 当然你也可以采用自己的读入方法。 ## Note 【样例解释】 第一次 `Query` 时，将第二组合并到第一组，此时三名学生的糖果数分别为 $\dfrac{14}{3},\dfrac{17}{3},\dfrac{5}{3}$，糖果数最多的同学有 $\dfrac{17}{3}$ 块糖果，取到了最小值，对 $10^9+7$ 取模后为 $666666677$。 第二次 `Query` 时，所有学生都在同一组，而糖果数最多的同学有 $5$ 块糖果。 --- 【数据范围】 | 数据点 | $n$ | $m$ | $k$ | $a_i$ | $b_i$ | | -----------: | -----------: | -----------: | -----------: | -----------: | -----------: | | $1$ | $\le 10$ |无特殊限制 | $\le 10$ | $\le 10$ | $\le 100$ | | $2$ | $\le 100$ | $\le 10$ | $\le 100$ | $\le 100$ | $\le 100$ | | $3$ | $\le 10^5$ | $=1$ | $\le 10^5$ | $\le 10^5$ | $\le 10^5$ | | $4$ | $\le 10^5$ | 无特殊限制 | $=1$ | $=1$ | $\le10^5$ | | $5$ | $\le 10^3$ |无特殊限制 | $\le 5$ | $\le 5$ | $\le 100$ | | $6$ | $\le 10^4$ | $\le 10^3$ | $\le 10^4$ | $\le 10^4$ | $\le 10^5$ | | $7$ | $\le 10^4$ | $\le 5\times10^3$ | $\le 10^4$ | $\le 10^4$ | $\le 10^5$ | | $8$ | $\le 10^5$ | 无特殊限制 | $\le 10^5$ | $\le 10^5$ | $\le 10^5$ | | $9 $| $\le 5\times10^5$ | 无特殊限制 | $5\times10^5$ | $5\times10^5$ | $\le 10^5$ | | $10$ | $\le 10^6$ | 无特殊限制 | $\le 10^6$ | $\le 10^6$ | $\le 10^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$。**数据保证合法，初始时每组是非空的。** 不熟悉有理数取模的请看[此处](/problem/solution/P2613)。