/*
|---------------------------------------------|
| Author : Le Hoang An |
| From : Bien Hoa Gifted High School |
|---------------------------------------------|
| ADOMINATION |
|---------------------------------------------|
*/
#pragma GCC optimize("02,unroll-loops")
#include <bits/stdc++.h>
#define f0(i, n) for(int i=0; i<n; i++)
#define f1(i, n) for(int i=1; i<=n; i++)
#define fi first
#define se second
#define pb push_back
#define ep emplace_back
#define el cout << "\n";
#define sz(A) (int)A.size()
#define FOR(i, l, r) for (int i = l; i <= r; i++)
#define FOD(i, r, l) for (int i = r; i >= l; i--)
#define all(x) x.begin(), x.end()
#define Albaz \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL);
#define Ado signed main()
using namespace std;
//#define int long long
#define itn int
typedef long long ll;
typedef pair<int, int> ii;
typedef unsigned long long ull;
typedef string str;
typedef vector<int> vi;
const int maxn = 100002;
const int mod = 1e4 + 7;
const ll inf = 1e18;
#define bit(mask, i) ((mask>>i)&1)
#define lon(x) ((1ll) << (x))
template <class X, class Y>
bool maximize(X &x, const Y&y)
{
if(x<y)
{
x=y;
return true;
}
else return false;
}
template <class X, class Y>
bool minimize(X &x, const Y&y)
{
if(x>y)
{
x=y;
return true;
}
else return false;
}
void file()
{
#define TASK "relativnost"
if(fopen(TASK".INP", "r"))
{
freopen(TASK".INP", "r", stdin);
freopen(TASK".OUT", "w", stdout);
}
}
void addmod(ll &x, ll y){
x += y;
if(x >= mod) x -= mod;
}
void submod(ll &x, ll y){
x -= y;
if(x < 0) x += mod;
}
void mulmod(ll &x, ll y){
x = (x * y) % mod;
}
int n, k, q, g[maxn], c[maxn];
namespace sub1{
ll sub = 0, total = 0;
vector<vector<ll>> dp;
void solve(){
while(q--){
int pos, ng, nc; cin >> pos >> ng >> nc;
g[pos] = ng; c[pos] = nc;
dp.assign(n + 1, vector<ll>(k + 1, 0));
sub = 0; total = 1;
FOR(i, 1, n) total = (total * (c[i] + g[i])) % mod;
dp[0][0] = 1;
FOR(i, 1, n){
FOR(j, 0, k - 1){
dp[i][j] = dp[i - 1][j] * c[i] % mod;
if(j > 0) dp[i][j] = (dp[i][j] + dp[i - 1][j - 1] * g[i] % mod) % mod;
}
}
FOR(j, 0, k - 1) addmod(sub, dp[n][j]);
cout << (total - sub + 1ll * mod * mod) % mod << " ";
}
}
}
namespace sub2{
const int kmax = 21;
static ll poly[4 * maxn][kmax];
static ll prodv[4 * maxn];
struct Query{
int pos, ng, nc;
Query(int _pos = 0, int _ng = 0, int _nc = 0){
pos = _pos; ng = _ng; nc = _nc;
}
};
vector<Query> que;
struct SegTree{
void Merge(int node, int L, int R){
int tmp[kmax];
FOR(i, 0, k - 1) tmp[i] = 0;
FOR(i, 0, k - 1){
int Ai = poly[L][i];
if(Ai == 0) continue;
FOR(j, 0, k - 1){
int ij = i + j;
if(i + j >= k) continue;
int Bj = poly[R][j];
tmp[ij] = (tmp[ij] + 1ll * Ai * Bj % mod) % mod;
}
}
FOR(t, 0, k - 1) poly[node][t] = tmp[t];
prodv[node] = (prodv[L] * prodv[R]) % mod;
}
void build(int node, int l, int r){
if(l == r){
FOR(t, 0, k - 1) poly[node][t] = 0;
poly[node][0] = c[l];
if(k > 1) poly[node][1] = g[l];
prodv[node] = (c[l] + g[l]) % mod;
return;
}
int mid = (l + r) >> 1;
build(node * 2, l, mid);
build(node * 2 + 1, mid + 1, r);
Merge(node, node * 2, node * 2 + 1);
}
void update(int node, int l, int r, int pos){
if(l == r){
FOR(t, 0, k - 1) poly[node][t] = 0;
poly[node][0] = c[l];
if(k > 1) poly[node][1] = g[l];
prodv[node] = (c[l] + g[l]) % mod;
return;
}
int mid = (l + r) >> 1;
if(pos <= mid) update(node * 2, l, mid, pos);
else update(node * 2 + 1, mid + 1, r, pos);
Merge(node, node * 2, node * 2 + 1);
}
} tree;
void solve(){
FOR(i, 1, q){
int pos, ng, nc; cin >> pos >> ng >> nc;
que.ep(pos, ng, nc);
}
tree.build(1, 1, n);
for(const auto &[pos, ng, nc] : que){
g[pos] = ng; c[pos] = nc;
tree.update(1, 1, n, pos);
ll total = prodv[1];
ll sub = 0;
FOR(t, 0, k - 1) addmod(sub, poly[1][t]);
cout << (total - sub + 1ll * mod * mod) % mod << " ";
}
}
}
Ado
{
Albaz;
file();
cin >> n >> k;
FOR(i, 1, n) cin >> g[i];
FOR(i, 1, n) cin >> c[i];
cin >> q;
if(n <= 1000 && q <= 1000) return sub1::solve(), 0;
return sub2::solve(), 0;
return 0;
}
