Increasing Sequences Product

We are given two sequences A and B of length \( n \). Define the sequence \( C \) such that \( C_i=\max_{1\le j\le i}A_j \) for \( 1\le i\le n \). The current value is defined as

\[ V=\prod_{i=1}^{n}\min(B_i, C_i). \]

There are \( q \) operations. Each operation increases one element in either the sequence A or B (the new value is strictly larger than the previous value). After each operation, you are required to output the current value V computed with the updated sequences.

inputFormat

The first line contains two integers n and q (the length of the sequences and the number of operations).

The second line contains n integers representing the sequence A.

The third line contains n integers representing the sequence B.

Each of the next q lines contains an operation in the format:

T pos x

Here, T is either 1 or 2. If T is 1, update A[pos] to x; if T is 2, update B[pos] to x. It is guaranteed that the new value x is greater than the current value at that position.

outputFormat

Output q lines, each containing a single integer, which is the current value \( V=\prod_{i=1}^{n}\min(B_i, C_i) \) after the corresponding operation.

sample

3 3
1 3 2
2 1 3
1 1 4
2 2 5
2 1 6

6
24
48

</p>