MEX Interval Score

You are given a length-$N$ sequence $A$ of nonnegative integers, a length-$(N+1)$ sequence $B$, and a length-$N$ sequence $C$. The indices of $B$ range from $0$ to $N$, while the other sequences are indexed from $1$ to $N$.

For a nonempty sequence $X$, $\operatorname{mex}(X)$ is the smallest nonnegative integer that does not occur in $X$.

The score of an interval $[s,e]$ is defined as

You are given $Q$ queries. For each query $[l,r]$, find the maximum score among all intervals $[s,e]$ satisfying $l\le s\le e\le r$.

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

$N\ Q$ $A_1\ A_2\ \cdots\ A_N$ $B_0\ B_1\ \cdots\ B_N$ $C_1\ C_2\ \cdots\ C_N$ $l_1\ r_1$ $l_2\ r_2$ $\vdots$ $l_Q\ r_Q$

For each query, print the maximum score of a valid interval on its own line.

• $1\le N,Q\le 300\,000$.
• $0\le A_i\le N$ ($1\le i\le N$).
• $0\le B_j\le 1\,000\,000\,000$ ($0\le j\le N$).
• $0\le C_i\le 1\,000\,000\,000$ ($1\le i\le N$).
• $1\le l_q\le r_q\le N$ ($1\le q\le Q$).