题目背景

本题数据已更新

题目描述

给定两个长度为 $n$ 的序列 $A$ 和 $B$，定义序列 $C_i=\max\limits_{j=1}^i A_j$。

定义当前的价值是 $\prod\limits_{i=1}^n \min(B_i,C_i)$。

现在有 $q$ 次操作，每次操作将会修改序列 $A$ 或者 $B$ 中的一个位置，将会把数字变大。现在请求出每次修改之后的价值。

输入格式

第一行两个整数 $n,q$。

第二行 $n$ 个整数表示 $A_i$。

第三行 $n$ 个整数表示 $B_i$。

接下来 $q$ 行，每行三个整数 $opt,x,y$，如果 $opt=0$ 表示对序列 A 操作，如果 $opt=1$ 则是对序列 $B$ 操作，把序列中第 $x$ 个元素变成 $y$，保证 $y$ 不小于原来的元素。

输出格式

输出 $q$ 行，表示每次修改之后的价值。

由于答案很大，请对 $10^9+7$ 取模后输出。

3 1
2 1 3
1 2 3
1 3 5

6

提示

对于所有数据，满足 $1 \le n,q\le 10^5,0\le A_i,B_i,y \le 10^9$。

对于 20% 的数据范围，满足 $1\le n,q\le 1000$

对于另外 10% 的数据范围，满足 $opt=1$

对于另外 20% 的数据范围，满足 $opt=0$

对于 80% 的数据范围，满足 $n,q\le 50000$