#include "circuit.h"
#include "bits/stdc++.h"
using namespace std;
#define int long long
#include <vector>
const int MAXN = 2e5 + 12;
const int MOD = 1e9 + 2022;
int n, m;
vector<int> adj[MAXN];
int contrib[MAXN];
int ans;
int a[MAXN];
int lazy[MAXN];
int Y[MAXN];
const int S = 320;
int sum[S];
int state[S];
int tot[S];
void calc_y(int node) {
Y[node] = adj[node].size();
Y[node] = max(1ll, Y[node]);
for(int x: adj[node]) {
calc_y(x);
Y[node] *= Y[x];
Y[node] %= MOD;
}
}
void propagate(int node) {
for(int x: adj[node]) {
lazy[x] *= lazy[node];
lazy[x] %= MOD;
propagate(x);
}
}
void init(int32_t N, int32_t M, std::vector<int32_t> P, std::vector<int32_t> A) {
for(int i=0; i<M; i++) contrib[i] = 1;
for(int i=1; i<N+M; i++) adj[P[i]].push_back(i);
for(int i=0; i<M; i++) a[i] = A[i];
n = N;
m = M;
ans = 0;
calc_y(0);
for(int i=0; i<N+M; i++) lazy[i] = 1;
for(int i=0; i<N; i++) {
int len = adj[i].size();
int pre[len], suf[len];
for(int j=0; j<len; j++) {
pre[j] = Y[adj[i][j]];
suf[j] = Y[adj[i][j]];
}
for(int j=1; j<len; j++) {
pre[j] *= pre[j-1];
pre[j] %= MOD;
}
for(int j=len-2; j>=0; j--) {
suf[j] *= suf[j+1];
suf[j] %= MOD;
}
for(int j=0; j<len; j++) {
if(j > 0) lazy[adj[i][j]] *= pre[j-1];
lazy[adj[i][j]] %= MOD;
if(j + 1 < len) lazy[adj[i][j]] *= suf[j+1];
lazy[adj[i][j]] %= MOD;
}
}
propagate(0);
for(int i=0; i<N+M; i++) {
contrib[i] = lazy[i];
}
for(int i=0; i<M; i++) {
sum[i / S] += a[i] * contrib[i + N];
sum[i / S] %= MOD;
state[i / S] = 0;
tot[i / S] += contrib[i + N];
tot[i / S] %= MOD;
}
for(int i=N; i<N+M; i++) {
if(a[i-N]) ans = (ans + contrib[i]) % MOD;
}
}
int32_t count_ways(int32_t L, int32_t R) {
L -= n;
R -= n;
if(R - L <= 2 * S) {
for(int i=L; i<=R; i++) {
int og = a[i] ^ state[i / S];
a[i] ^= 1;
ans += MOD - og * contrib[i + n];
ans %= MOD;
sum[i / S] += MOD - og * contrib[i + n];
sum[i / S] %= MOD;
og ^= 1;
ans += og * contrib[i + n];
ans %= MOD;
sum[i / S] += og * contrib[i + n];
sum[i / S] %= MOD;
}
return ans;
}
while(L % S != 0) {
int i = L;
int og = a[i] ^ state[i / S];
a[i] ^= 1;
ans += MOD - og * contrib[i + n];
ans %= MOD;
sum[i / S] += MOD - og * contrib[i + n];
sum[i / S] %= MOD;
og ^= 1;
ans += og * contrib[i + n];
ans %= MOD;
sum[i / S] += og * contrib[i + n];
sum[i / S] %= MOD;
L++;
}
while(R % S != S - 1) {
int i = R;
int og = a[i] ^ state[i / S];
a[i] ^= 1;
ans += MOD - og * contrib[i + n];
ans %= MOD;
sum[i / S] += MOD - og * contrib[i + n];
sum[i / S] %= MOD;
og ^= 1;
ans += og * contrib[i + n];
ans %= MOD;
sum[i / S] += og * contrib[i + n];
sum[i / S] %= MOD;
R--;
}
for(int i=L; i<=R; i+=S) {
if(state[i / S]) {
ans += MOD - sum[i / S];
ans %= MOD;
}
else {
ans += MOD + sum[i / S] - tot[i / S];
ans %= MOD;
}
state[i / S] ^= 1;
if(state[i / S]) {
ans += sum[i / S];
ans %= MOD;
}
else {
ans += MOD + tot[i / S] - sum[i / S];
ans %= MOD;
}
}
return ans;
}
#undef int
#include "circuit.h"
#include <cassert>
#include <cstdio>
#include <vector>
int main() {
int N, M, Q;
assert(3 == scanf("%d %d %d", &N, &M, &Q));
std::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;
}
/*
g++ circuit.cpp -std=c++17 -O2 -o circuit
./circuit < input.txt
*/
Compilation message
/usr/bin/ld: /tmp/ccjf97yR.o: in function `main':
stub.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cc4WpyVR.o:circuit.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
