Mansur's Horse Trading

Mansur, following in the footsteps of his ancestors, loves breeding horses. In his youth, exactly N years ago, he had only one horse. With his ambition to become rich, he started horse breeding, and now he owns the largest horse ranch in Kazakhstan.

The N years are numbered from 0 to N-1 in chronological order (i.e. year N-1 is the most recent year). In each year i, the weather affects the breeding. At the beginning of year i, if Mansur has h horses, then after breeding the number of horses becomes:

\( h \times X[i] \)

At the end of each year, Mansur can sell an arbitrary number of horses, each at a price of Y[i] recorded for that year. Being a wise seller, he wants to know the maximum revenue he can obtain over the N years if he sells at the best possible time in each year.

Note that Mansur updates his records M times. In each update he changes either an element of X or an element of Y. After each update, the changes are cumulative and he asks you to recalculate the maximum revenue using the updated arrays. Since the answer might be very large, output it modulo \(10^9+7\).

Optimal Strategy

Assume that Mansur starts with 1 horse. In each year i, after breeding his number of horses becomes \(X[i]\) times what he had at the start of that year. He then decides whether to sell all his horses at that year or wait. Because the decision is linear, it turns out that the optimal strategy is to choose a single year \(k\) (\(0\le k\le N-1\)) and sell all horses in that year. The revenue if he sells in year \(k\) is given by:

\(\Bigl(\prod_{i=0}^{k} X[i]\Bigr) \times Y[k]\)

Thus, the maximum revenue is

\(\max_{0 \le k \le N-1} \left(\prod_{i=0}^{k} X[i] \times Y[k]\right)\)

inputFormat

The first line contains two integers N and M -- the number of years and the number of updates.

The second line contains N positive integers: X[0], X[1], ..., X[N-1].

The third line contains N positive integers: Y[0], Y[1], ..., Y[N-1].

Then follow M lines. Each update is represented by three integers:

• If the first integer is 1, then the update is to set X[index] = new_value.
• If the first integer is 2, then the update is to set Y[index] = new_value.

After each update, you should compute the maximum revenue obtainable over the N years using the updated arrays, and output the result modulo \(10^9+7\).

outputFormat

For each update, output a single line containing the maximum revenue modulo \(10^9+7\>.

sample

5 3
2 3 1 5 2
3 1 4 2 7
2 2 6
1 3 4
2 0 10

420
336
336

</p>