Description

简要题意

给定一个长度为 $n$ 的序列，序列中每个元素是一个二元组 $(c_i,a_i)$，分别表示颜色与权值。

现在有 $q$ 次询问，每次给出一个区间 $[l,r]$，求：

$$\max\limits_{k=1}^n \left\{\min\limits_{l\le i \le r,c_i=k} a_i\right\}$$

特别地，如果 $[l,r]$ 内没有颜色为 $k$ 的值，后面的部分定义为 $0$。

原始题意

纯狐的能力是纯化，一旦灵梦身上的污秽被纯化，则必死无疑。

灵梦携带了 $n$ 张一字排开的灵符用于转嫁污秽，但纯狐依旧可以纯化附着在上面的污秽，置灵梦于死地。

具体地，每次纯狐命中一个区间 $[l_i,r_i]$ 中的所有灵符，灵梦需要在此之前净化这些灵符上面的污秽。
每张灵符有固定的颜色 $c_i$，经过激烈的战斗，每张灵符上沾染了 $a_i$ 单位的污秽。
同种颜色的灵符之间相互作用，净化区间内一批相同颜色的灵符，其灵力花费为这些灵符上污秽的最小值。
由于逸散的灵力可以为其他灵符所吸收，灵梦只需知道该区间内所有颜色的灵符净化花费的最大值，此为她净化一次的灵力花费。

给定 $\{c_i\}$ 和 $\{a_i\}$，每次给出纯狐的一种可能的攻击 $l_i,r_i$，问灵梦净化一次的灵力花费。注意只是计算，每次给出答案后并不改变 $\{c_i\}$ 和 $\{a_i\}$。

Input Format

第一行两个整数 $n,q$，表示序列长度与询问次数。

第二行 $n$ 个整数，依次为 $c_1,c_2,\cdots,c_n$。

第三行 $n$ 个整数，依次为 $a_1,a_2,\cdots,a_n$。

接下来 $q$ 行，每行两个整数 $l,r$，表示每次询问给出的区间。

Output Format

共 $q$ 行，每行一个整数，表示本次询问的答案。

10 10
3 2 2 1 2 1 3 2 1 2 
10 4 10 4 9 8 1 4 9 4 
3 4
3 9
4 8
3 6
3 3
9 10
5 8
5 8
6 8
5 8

10
4
4
9
10
9
8
8
8
8

Hint

样例 1 解释

如图，数字代表权值，背景色代表颜色。

• 对于区间 $[3,4]$，出现的两种颜色对应的权值最小值为 $10$ 和 $4$，取最大值答案为 $10$。
• 对于区间 $[3,9]$，出现的三种颜色对应的权值最小值为 $1,4$ 和 $4$，取最大值答案为 $4$。
• 对于区间 $[4,8]$，出现的三种颜色对应的权值最小值为 $1,4$ 和 $4$，取最大值答案为 $4$。
• 对于区间 $[3,6]$，出现的两种颜色对应的权值最小值为 $9$ 和 $4$，取最大值答案为 $9$。
• 对于区间 $[3,3]$，出现的一种颜色对应的权值最小值为 $10$。 其余同理。

数据范围及约定

$$\def\arraystretch{1.5} \begin{array}{|c|c|c|c|c|c|}\hline \textbf{Subtask} & \bm{n\le } & \bm{q\le} & \textbf{特殊性质} & \textbf{Subtask 依赖} & \textbf{分值}\\\hline 1 & 100 & 100 & - & - & 10\\\hline 2 & 2 \times 10^5 & 2\times 10^5 & \textbf A & - & 20\\\hline 3 & 2 \times 10^5 & 2\times 10^5 & - & 2 & 30\\\hline 4 & 2 \times 10^5 & 10^6 & - & 1,3 & 40\\\hline \end{array}$$

特殊性质 $\textbf A$：所有的 $c_i \leq 10$。

对于全部数据，保证 $1 \leq n \leq 2\times10^5$，$1 \leq q \leq 10^6$，$1 \le c_i,a_i \le n$，$l \leq r$。