Problem Statement

You are given positive integers $N, X$ and integer sequences of length $N$: $S = (S_1, S_2, \dots, S_N), P = (P_1, P_2, \dots, P_N)$. Here, each element of $P$ is $1$ or $-1$.

You are given $Q$ queries. In each query, you are given integers $l, r$ satisfying $1 \leq l \leq r \leq N$, and you play the following game:

• Initially, your score is $0$, and integers $a, b$ are initialized as $a = 1, b = 1$.
• For $i = l, l+1, \dots, r$ in this order, perform the following operation:
• If $i$ is even, replace the value of $a$ with any integer between $1$ and $X$ (inclusive); if $i$ is odd, replace the value of $b$ with any integer between $1$ and $X$ (inclusive).
  • After that, if $ab \geq S_i$, add $P_i$ to your score. Otherwise, the score does not change. Note that $P_i$ can be negative.

For each query, find the maximum possible value of your score when the game ends.

Constraints

• $1 \le N, X, Q \le 10^5$
• $1 \le S_i \le 10^5$
• $P_i = 1$ or $P_i = -1$.
• For each query, $1 \le l \le r \le N$.
• All input values are integers.

Input

The input is given from Standard Input in the following format:

N X Q
S_1 S_2 \ldots S_N
P_1 P_2 \ldots P_N
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q

Each query is given in the following format:

l r

Output

Output $Q$ lines.

The $i$-th line should contain the maximum possible value of your score when the game ends in the $i$-th query.