MEX 점수 구하기

음이 아닌 정수로 이루어진 길이 $N$의 수열 $A$, 길이 $N+1$의 수열 $B$, 길이 $N$의 수열 $C$가 주어진다. 수열 $B$의 인덱스는 $0$부터 $N$까지이고, 나머지 수열의 인덱스는 $1$부터 $N$까지이다.

비어 있지 않은 수열 $X$의 $\operatorname{mex}(X)$는 $X$에 등장하지 않는 가장 작은 음이 아닌 정수이다.

구간 $[s,e]$의 점수를 다음과 같이 정의한다.

$Q$개의 질의가 주어진다. 각 질의 $[l,r]$에 대해, $l\le s\le e\le r$을 만족하는 모든 구간 $[s,e]$의 점수 중 최댓값을 구하여라.

입력은 다음과 같은 형식으로 주어진다.

$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$

각 질의에 대해, 조건을 만족하는 구간 점수의 최댓값을 한 줄에 하나씩 출력한다.

• $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$).