#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;
#ifndef WAIMAI
#include "circuit.h"
#endif
#ifdef WAIMAI
#define debug(HEHE...) cout << "[" << #HEHE << "] : ", dout(HEHE)
void dout() {cout << '\n';}
template<typename T, typename...U>
void dout(T t, U...u) {cout << t << (sizeof...(u) ? ", " : ""), dout(u...);}
#else
#define debug(...) 7122
#endif
#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second
#define lpos pos*2
#define rpos pos*2+1
const int MOD = 1000002022;
const int SIZE = 2e5 + 5;
int n, m, ans;
vector<int> adj[SIZE];
int a[SIZE], coef[SIZE], all[SIZE], pre[SIZE];
int add(const int &x, const int &y) {
return x + y >= MOD ? x + y - MOD : x < -y ? x + y + MOD : x + y;
}
int mul(const int &x, const int &y) {
return 1ll * x * y % MOD;
}
struct Node {
int sum = 0, lazy = 0;
} node[SIZE * 4];
void build(int pos, int l, int r) {
if (l == r) {
if (a[l]) node[pos].sum = coef[l];
return;
}
int mid = (l + r) / 2;
build(lpos, l, mid);
build(rpos, mid + 1, r);
node[pos].sum = add(node[lpos].sum, node[rpos].sum);
}
void push(int pos, int l, int r) {
if (!node[pos].lazy) return;
node[pos].sum = add(pre[r], -add((l ? pre[l - 1] : 0), node[pos].sum));
if (l < r) {
node[lpos].lazy ^= 1;
node[rpos].lazy ^= 1;
}
node[pos].lazy = 0;
}
void pull(int pos, int l, int r) {
int mid = (l + r) / 2;
push(lpos, l, mid);
push(rpos, mid + 1, r);
node[pos].sum = add(node[lpos].sum, node[rpos].sum);
}
void upd(int pos, int l, int r, int L, int R) {
if (l == L && r == R) {
node[pos].lazy ^= 1;
return;
}
push(pos, L, R);
int mid = (L + R) / 2;
if (r <= mid) upd(lpos, l, r, L, mid);
else if (l > mid) upd(rpos, l, r, mid + 1, R);
else {
upd(lpos, l, mid, L, mid);
upd(rpos, mid + 1, r, mid + 1, R);
}
pull(pos, L, R);
}
void dfs0(int pos) {
int pro = 1;
for (int np : adj[pos]) {
dfs0(np);
pro = mul(pro, all[np]);
}
if (adj[pos].size()) pro = mul(pro, adj[pos].size());
all[pos] = pro;
}
void dfs(int pos, int cur) {
if (adj[pos].size() == 0) {
coef[pos - n] = cur;
return;
}
int sz = adj[pos].size();
vector<int> pL(sz), pR(sz);
FOR (i, 0, sz - 1) pL[i] = pR[i] = all[adj[pos][i]];
FOR (i, 1, sz - 1) pL[i] = mul(pL[i - 1], pL[i]);
for (int i = sz - 2; i >= 0; i--) pR[i] = mul(pR[i + 1], pR[i]);
FOR (i, 0, sz - 1) {
int pro = cur;
if (i > 0) pro = mul(pro, pL[i - 1]);
if (i < sz - 1) pro = mul(pro, pR[i + 1]);
dfs(adj[pos][i], pro);
}
}
void init(int N, int M, vector<int> P, vector<int> A) {
n = N, m = M;
FOR (i, 1, n + m - 1) adj[P[i]].pb(i);
dfs0(0);
dfs(0, 1);
FOR (i, 0, m - 1) {
a[i] = A[i];
pre[i] = add((i ? pre[i - 1] : 0), coef[i]);
}
build(1, 0, m - 1);
}
int count_ways(int L, int R) {
L -= n, R -= n;
upd(1, L, R, 0, m - 1);
push(1, 0, m - 1);
return node[1].sum;
}
/*
in1
3 4 3
-1 0 1 2 1 1 0
1 0 1 0
3 4
4 5
3 6
out1
2
0
6
*/
#ifdef WAIMAI
int main() {
int N, M, Q;
assert(3 == scanf("%d %d %d", &N, &M, &Q));
vector<int> P(N + M), A(M);
for (int i = 0; i < N + M; ++i) {
assert(1 == scanf("%d", &P[i]));
}
for (int j = 0; j < M; ++j) {
assert(1 == scanf("%d", &A[j]));
}
init(N, M, P, A);
for (int i = 0; i < Q; ++i) {
int L, R;
assert(2 == scanf("%d %d", &L, &R));
printf("%d\n", count_ways(L, R));
}
return 0;
}
#endif
