Optimal Candy Merging

At a party there are n students numbered from \(1,2,3,\ldots,n\). They are initially divided into k groups (numbered \(1,2,3,\ldots,k\)). The i-th student is assigned to group \(a_i\) and given \(b_i\) candies. Note that the organizer (teacher V) is not part of any group and does not hold any candies.

The party has m rounds of activities. In each round one of the following events occurs:

1. Change X Y: Move all students in group \(X\) to group \(Y\). After that, group \(X\) is deleted (it becomes empty).
2. Query: Teacher V wonders, if one were to merge all the remaining groups into one big group (the merging is only hypothetical and does not affect the actual groups), what is the minimum possible value of the maximum number of candies held by any student in that big group? Since candies can be split, the answer might be a rational number. Output the answer modulo \(10^9+7\) (see note below).

Merging process:

Assume a group \(G_i\) has \(S_i\) students and total candy \(F_i\), with its maximum candy count among its members being \(M_i\). When merging group \(G_1\) into group \(G_2\) (where \(S_1>0\) and \(S_2>0\)) the following two steps are performed:

1. All students in \(G_1\> have their candy count reset to \(0\) and their group changed to \(G_2\).
2. Then every student currently in \(G_2\) (including those moved from \(G_1\)) has \(\dfrac{F_1}{S_1+S_2}\) added to their candy count.

Note: Merging \(G_1\) into \(G_2\) can produce a different final result than merging \(G_2\) into \(G_1\>.

The hypothetical merger proceeds by repeatedly merging two groups until only one remains. In each binary merge the order is chosen arbitrarily. Your task in each Query is to choose an order of merges (including the choice of which group remains the "base") so that the final maximum candy count among all students is minimized. Output that minimum possible final maximum candy count modulo \(10^9+7\). (If the answer is a rational number \(\frac{p}{q}\), output \(p \cdot q^{-1} \bmod (10^9+7)\); see the hint for details.)

Input constraints and note: All operations are applied sequentially. A Change operation merges two groups by transferring all of one group into the other (and deleting the former). The Query operation does not actually change the groups. It only asks for the optimal result if one were to merge all current groups optimally.

You may assume that the initial number of groups \(k\) and the number of events \(m\) are small enough that an \(O(k^2)\) solution per query is acceptable.

inputFormat

The first line contains three integers \(n\), \(k\) and \(m\) — the number of students, the number of groups, and the number of events.

The second line contains \(n\) integers \(a_1, a_2, \ldots, a_n\) where \(a_i\) is the initial group of the \(i\)-th student.

The third line contains \(n\) integers \(b_1, b_2, \ldots, b_n\) where \(b_i\) is the number of candies the \(i\)-th student initially has.

Then follow \(m\) lines. Each line is either in the format:

• Change X Y
• Query

Note: After a Change X Y operation, all students in group \(X\) are moved to group \(Y\), and group \(X\) is deleted. The Query operations do not change the groups.

outputFormat

For each Query operation, output one line containing the minimum possible final maximum candy count (computed as a rational number modulo \(10^9+7\)).

If the answer is a fraction \(\frac{p}{q}\), output \(p \cdot q^{-1} \bmod (10^9+7)\).

sample

3 3 3
1 2 3
1 2 3
Query
Change 1 2
Query

3
3

</p>