{"raw_statement":[{"iden":"background","content":">「因为，人类的历史与成长，就是战争的历史与成长。没有纷争，就没有成长。满足于现状，就等于人类放弃了生存。月之民每天都为地上人考虑着。地上人的历史，就是月之民创造的。」\n\n「我对月之民还是很了解的。这么说吧，她们在各式各样的异世界的居民中，属于最恶劣的那一类。超级排他，超级没自由，虚构的乐园，虽然擅长鄙视别人，但无法容忍自己被当成笨蛋。她们甚至认为其他世界的居民连杂菌都不如。」\n\n「最重要的问题是，月之民敌视着幻想乡，就是这样的。」 \n\n「没想到竟然会把地上人送到月面上来，之前丝毫没有过这种想法呢。那些眼里容不下一点沙子的月之民，竟然会使用这种不入流的手段。」\n\n「幻想乡被作为人质绑架了，可以这么认为吧？要是想拯救幻想乡的话，就不许对月之都动手，就是这种不人道的策略。」\n\n遥遥 $38$ 万公里航程之外，于此故乡之星倒映之海，打败不共戴天之敌，击碎永久不得醒之梦。\n\n> 不倶戴天の敵、$\\stackrel{じょうが}{嫦娥}$よ。見てるか！？    \n> 不共戴天之敌，嫦娥啊。你在看着吗！？"},{"iden":"statement","content":"### 简要题意\n\n给定一个长度为 $n$ 的序列，序列中每个元素是一个二元组 $(c_i,a_i)$，分别表示颜色与权值。\n\n现在有 $q$ 次询问，每次给出一个区间 $[l,r]$，求：\n\n$$\\max\\limits_{k=1}^n \\left\\{\\min\\limits_{l\\le i \\le r,c_i=k} a_i\\right\\}$$\n\n特别地，如果 $[l,r]$ 内没有颜色为 $k$ 的值，后面的部分定义为 $0$。\n### 原始题意\n纯狐的能力是纯化，一旦灵梦身上的污秽被纯化，则必死无疑。\n\n灵梦携带了 $n$ 张一字排开的灵符用于转嫁污秽，但纯狐依旧可以纯化附着在上面的污秽，置灵梦于死地。\n\n具体地，每次纯狐命中一个区间 $[l_i,r_i]$ 中的所有灵符，灵梦需要在此之前净化这些灵符上面的污秽。  \n每张灵符有固定的颜色 $c_i$，经过激烈的战斗，每张灵符上沾染了 $a_i$ 单位的污秽。  \n同种颜色的灵符之间相互作用，净化区间内一批相同颜色的灵符，其灵力花费为这些灵符上污秽的最小值。  \n由于逸散的灵力可以为其他灵符所吸收，灵梦只需知道该区间内所有颜色的灵符净化花费的最大值，此为她净化一次的灵力花费。\n\n给定 $\\{c_i\\}$ 和 $\\{a_i\\}$，每次给出纯狐的一种可能的攻击 $l_i,r_i$，问灵梦净化一次的灵力花费。注意只是计算，每次给出答案后并不改变 $\\{c_i\\}$ 和 $\\{a_i\\}$。"},{"iden":"input","content":"第一行两个整数 $n,q$，表示序列长度与询问次数。\n\n第二行 $n$ 个整数，依次为 $c_1,c_2,\\cdots,c_n$。\n\n第三行 $n$ 个整数，依次为 $a_1,a_2,\\cdots,a_n$。\n\n接下来 $q$ 行，每行两个整数 $l,r$，表示每次询问给出的区间。"},{"iden":"output","content":"共 $q$ 行，每行一个整数，表示本次询问的答案。"},{"iden":"note","content":"### 样例 1 解释\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/yu9grxjy.png)\n\n如图，数字代表权值，背景色代表颜色。\n\n- 对于区间 $[3,4]$，出现的两种颜色对应的权值最小值为 $10$ 和 $4$，取最大值答案为 $10$。\n- 对于区间 $[3,9]$，出现的三种颜色对应的权值最小值为 $1,4$ 和 $4$，取最大值答案为 $4$。\n- 对于区间 $[4,8]$，出现的三种颜色对应的权值最小值为 $1,4$ 和 $4$，取最大值答案为 $4$。\n- 对于区间 $[3,6]$，出现的两种颜色对应的权值最小值为 $9$ 和 $4$，取最大值答案为 $9$。\n- 对于区间 $[3,3]$，出现的一种颜色对应的权值最小值为 $10$。\n其余同理。\n\n### 数据范围及约定\n\n$$\n\\def\\arraystretch{1.5}\n\\begin{array}{|c|c|c|c|c|c|}\\hline\n\\textbf{Subtask} & \\bm{n\\le } & \\bm{q\\le} & \\textbf{特殊性质} & \\textbf{Subtask 依赖} & \\textbf{分值}\\\\\\hline\n1 & 100 & 100 & - & - & 10\\\\\\hline\n2 & 2 \\times 10^5 & 2\\times 10^5 & \\textbf A & - & 20\\\\\\hline\n3 & 2 \\times 10^5 & 2\\times 10^5 & - & 2 & 30\\\\\\hline\n4 & 2 \\times 10^5 & 10^6 & - & 1,3 & 40\\\\\\hline\n\\end{array}\n$$\n\n特殊性质 $\\textbf A$：所有的 $c_i \\leq 10$。\n\n对于全部数据，保证 $1 \\leq n \\leq 2\\times10^5$，$1 \\leq q \\leq 10^6$，$1 \\le c_i,a_i \\le n$，$l \\leq r$。"}],"translated_statement":null,"sample_group":[["10 10\n3 2 2 1 2 1 3 2 1 2 \n10 4 10 4 9 8 1 4 9 4 \n3 4\n3 9\n4 8\n3 6\n3 3\n9 10\n5 8\n5 8\n6 8\n5 8\n","10\n4\n4\n9\n10\n9\n8\n8\n8\n8\n"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}