Threshold Gate Parameter Assignment

You are given a digital circuit consisting of \(N+M\) gates numbered from \(0\) to \(N+M-1\). The first \(N\) gates (\(0\) to \(N-1\)) are threshold gates, and the remaining \(M\) gates (\(N\) to \(N+M-1\)) are input gates.

For every gate \(i\) with \(1 \le i \le N+M-1\), it is an input to exactly one threshold gate whose index is given by \(P[i]\) with \(0 \le P[i] \le N-1\), and it is guaranteed that \(P[i] < i\). (For convenience, assume \(P[0] = -1\).) Note that each threshold gate has at least one input while input gates have no inputs.

Each gate has a state, either \(0\) or \(1\). The initial states of the input gates are given by an array \(A\) of \(M\) integers; that is, for \(0 \le j \le M-1\), the initial state of the input gate numbered \(N+j\) is \(A[j]\).

Every threshold gate is assigned a parameter (its threshold value) from \(1\) to its number of inputs \(c\) (inclusive). A threshold gate with parameter \(p\) will output \(1\) if and only if at least \(p\) of its inputs are in state \(1\); otherwise, it outputs \(0\). (Note that when a threshold gate has \(c\) inputs, there are always exactly \(c\) possible parameter choices. In particular, if exactly \(x\) of the inputs are \(1\), then there are \(x\) choices for the parameter which result in an output of \(1\) and \(c-x\) choices which result in an output of \(0\).)

After the initial configuration is set up, the states of the input gates will be updated \(Q\) times. Each update is described by two integers \(L\) and \(R\) (with \(N \le L \le R \le N+M-1\)) indicating that for every input gate whose index is in the range \([L, R]\) (inclusive), its state is toggled (i.e. \(0\) becomes \(1\) and \(1\) becomes \(0\)). Once toggled, a gate keeps its new state until possibly toggled again by a later update.

Your task is to determine, after each update, how many different assignments of parameters for the threshold gates will result in gate \(0\) (which is always a threshold gate) having state \(1\). Two assignments are considered different if there exists a threshold gate whose parameter differs. Because the answer might be large, output it modulo \(1000002022\).

Input Format: The input begins with a line containing three integers \(N\), \(M\), and \(Q\). The next line contains \(M\) integers representing the initial states of the input gates \(N\) to \(N+M-1\). The following line contains \(N+M-1\) integers: for each \(i\) with \(1 \le i \le N+M-1\), the integer \(P[i]\) (note that \(P[0]\) is omitted and can be assumed to be \(-1\)). Each of the next \(Q\) lines contains two integers \(L\) and \(R\) (with \(N \le L \le R \le N+M-1\)), describing an update operation.

Output Format: For each update, output a single line containing one integer, the number of threshold gate parameter assignment schemes that result in gate \(0\) outputting \(1\), modulo \(1000002022\).

Example:

Input
3 4 2
1 0 1 0
0 1 2 1 1 0
3 3
4 6
Output
1
4

</p>

In the example above, the circuit has 3 threshold gates and 4 input gates. The parent array \(P\) is such that gate \(0\) takes inputs from gates 1 and 6, gate \(1\) takes inputs from gates 2, 4, and 5, and gate \(2\) takes input from gate 3. After processing the updates as described, the number of valid parameter assignments leading to gate \(0\) outputting \(1\) is 1 after the first update and 4 after the second update.

---

Note: All formulas are written in LaTeX; for instance, a threshold gate with \(c\) inputs and \(x\) ones among them yields \(x\) valid parameter choices to produce output \(1\) and \(c-x\) choices to produce output \(0\).

inputFormat

The first line contains three integers \(N\), \(M\), and \(Q\) separated by spaces.

The second line contains \(M\) integers \(A[0], A[1], \ldots, A[M-1]\) representing the initial states of input gates \(N\) to \(N+M-1\).

The third line contains \(N+M-1\) integers: for each \(i = 1, 2, \ldots, N+M-1\), the integer \(P[i]\) (with \(0 \le P[i] \le N-1\)).

Each of the next \(Q\) lines contains two integers \(L\) and \(R\) (with \(N \le L \le R \le N+M-1\)) describing an update (flip) operation on the input gates in the interval \([L, R]\).

outputFormat

For each update, output on a separate line a single integer which is the number of threshold gate parameter assignment schemes that yield gate \(0\) in state \(1\), modulo \(1000002022\).

sample

3 4 2
1 0 1 0
0 1 2 1 1 0
3 3
4 6

1
4

</p>