题目背景

「因为，人类的历史与成长，就是战争的历史与成长。没有纷争，就没有成长。满足于现状，就等于人类放弃了生存。月之民每天都为地上人考虑着。地上人的历史，就是月之民创造的。」

「我对月之民还是很了解的。这么说吧，她们在各式各样的异世界的居民中，属于最恶劣的那一类。超级排他，超级没自由，虚构的乐园，虽然擅长鄙视别人，但无法容忍自己被当成笨蛋。她们甚至认为其他世界的居民连杂菌都不如。」

「最重要的问题是，月之民敌视着幻想乡，就是这样的。」

「没想到竟然会把地上人送到月面上来，之前丝毫没有过这种想法呢。那些眼里容不下一点沙子的月之民，竟然会使用这种不入流的手段。」

「幻想乡被作为人质绑架了，可以这么认为吧？要是想拯救幻想乡的话，就不许对月之都动手，就是这种不人道的策略。」

遥遥 $38$ 万公里航程之外，于此故乡之星倒映之海，打败不共戴天之敌，击碎永久不得醒之梦。

不倶戴天の敵、$\stackrel{じょうが}{嫦娥}$よ。見てるか！？
不共戴天之敌，嫦娥啊。你在看着吗！？

题目描述

简要题意

给定一个长度为 $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\}$。

输入格式

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

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

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

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

输出格式

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

提示

样例 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$。