Background

The testdata for this problem has been updated.

Problem Description

Given two sequences $A$ and $B$ of length $n$, define the sequence $C_i=\max\limits_{j=1}^i A_j$.

Define the current value as $\prod\limits_{i=1}^n \min(B_i,C_i)$.

Now there are $q$ operations. Each operation modifies one position in sequence $A$ or $B$, and the number will increase. You need to output the value after each modification.

Input Format

The first line contains two integers $n,q$.

The second line contains $n$ integers representing $A_i$.

The third line contains $n$ integers representing $B_i$.

The next $q$ lines each contain three integers $opt,x,y$. If $opt=0$, it means an operation on sequence $A$; if $opt=1$, it means an operation on sequence $B$. Set the $x$-th element of the corresponding sequence to $y$. It is guaranteed that $y$ is not smaller than the original element.

Output Format

Output $q$ lines, each being the value after the corresponding modification.

Since the answer can be very large, output it modulo $10^9+7$.

3 1
2 1 3
1 2 3
1 3 5

6

Hint

For all testdata, $1 \le n,q\le 10^5,0\le A_i,B_i,y \le 10^9$.

For 20% of the Constraints, $1\le n,q\le 1000$.

For another 10% of the Constraints, $opt=1$.

For another 20% of the Constraints, $opt=0$.

For 80% of the Constraints, $n,q\le 50000$.

Translated by ChatGPT 5