말 팔기

만수르는 말을 키운다. 지금은 카자흐스탄에서 말을 가장 많이 가진 사람이지만, $N$년 전에는 그저 젊은이였고 말도 한 마리뿐이었다.

해에 시간 순서대로 0번부터 $N-1$번까지 번호를 매긴다. $N-1$번 해가 가장 최근이다. $i$번 해의 날씨는 말이 불어나는 정도를 정하고, 그 비율은 양의 정수 $X[i]$이다. $i$번 해 연초에 말이 $h$마리 있었다면 그 해 연말에는 $h \times X[i]$마리가 된다.

말은 연말에만 판다. $i$번 해 연말의 말값은 한 마리에 양의 정수 $Y[i]$이고, 그 해 연말에 가진 말 중 몇 마리를 팔지에는 제한이 없다.

만수르는 지난 $N$년 동안 파는 시기를 가장 잘 골랐다면 돈을 얼마나 벌 수 있었을지 궁금하다. 저녁 동안 기억이 점점 또렷해져서 만수르는 값을 $M$번 고친다. 한 번 고칠 때마다 $X[i]$ 하나 또는 $Y[i]$ 하나가 새 값으로 바뀌고, 고친 내용은 그대로 쌓인다. 같은 자리를 여러 번 고치기도 한다.

처음 값으로 벌 수 있는 돈의 최댓값과, 값을 한 번 고칠 때마다 벌 수 있는 돈의 최댓값을 구한다. 답이 매우 클 수 있으므로 $10^9+7$로 나눈 나머지를 출력한다.

첫째 줄에 해의 수 $N$이 주어진다.

둘째 줄에 $X[0]$부터 $X[N-1]$까지 $N$개의 정수가 공백으로 구분되어 주어진다.

셋째 줄에 $Y[0]$부터 $Y[N-1]$까지 $N$개의 정수가 공백으로 구분되어 주어진다.

넷째 줄에 고치는 횟수 $M$이 주어진다.

이어지는 $M$개의 줄에는 고치는 내용이 한 줄에 하나씩 type pos val 형식으로 주어진다. type이 1이면 $X[pos]$를 val로 바꾸고, 2이면 $Y[pos]$를 val로 바꾼다.

제한:

• $1 \le N \le 500\,000$
• $0 \le M \le 100\,000$
• $1 \le X[i] \le 10^9$, $1 \le Y[i] \le 10^9$ (처음 값도, 고친 뒤의 값도 모두 이 범위에 있다)
• type은 1 또는 2이고, $0 \le pos \le N-1$, $1 \le val \le 10^9$

$M+1$개의 줄을 출력한다.

첫째 줄에는 처음 값으로 벌 수 있는 돈의 최댓값을 출력한다. 이어지는 $i$번째 줄에는 앞에서부터 $i$개의 수정을 모두 반영한 뒤 벌 수 있는 돈의 최댓값을 출력한다.

각 값은 $10^9+7$로 나눈 나머지이다.