{"raw_statement":[{"iden":"statement","content":"小 D 三岁就学会了出题。\n\n小 D 有一个正整数序列 $a_1, a_2, \\dots a_n$ 和一个整数序列 $b_1, b_2, \\dots ,b_n$。\n\n小 D 有 $q$ 次查询，每次给出 $x, y$，构造一个新的序列 $c_1,c_2,\\dots ,c_n$，其中 $c_i=\\begin{cases}1 & a_i=x \\\\-1 & a_i = y \\\\ 0 & \\text{else}\\end{cases}$。\n\n保证 $c_i$ 中至少存在一个 $1$ 与一个 $-1$。他想让你帮他找到一个区间 $[l,r]$，满足 $\\sum\\limits_{i = l}^r c_i = 0$，并使得 $\\sum\\limits_{i = l}^r b_i \\times [c_i \\neq 0]$ 最大，并且区间里的 $c_i$ 不能都为 $0$。你需要输出这个最大值。\n\n注：当条件 $[P]$ 为真时，$[P]=1$，否则 $[P]=0$。"},{"iden":"input","content":"第一行有两个整数 $n, q$。   \n第二行有 $n$ 个整数，第 $i$ 个整数表示 $a_i$。  \n第三行有 $n$ 个整数，第 $i$ 个整数表示 $b_i$。  \n接下来 $q$ 行，每行两个整数 $x,y$，表示一次询问。"},{"iden":"output","content":"对于每次询问，输出一行一个整数表示最大的 $\\sum\\limits_{i = l}^r b_i \\times [c_i \\neq 0]$。"},{"iden":"note","content":"### 数据规模与约定\n本题共 $20$ 个测试点。\n- 对于测试点 $1,2,3,4$，保证 $n, q ≤5000$。\n- 对于测试点 $5,6$，保证 $a$ 的取值不超过 $500$ 种。\n- 对于测试点 $7,8$，保证 $n \\le 150000$。$q \\le 500000$，$b_i>0$。\n- 对于测试点 $9$，保证 $n \\le 150000$，$q \\le 500000$。\n- 对于测试点 $10,11$，保证 $n \\le 200000$，$q \\le 500000$。\n- 对于测试点 $12,13,14$，保证 $b_i=1$。\n- 对于测试点 $15,16$，保证 $b_i>0$。\n\n对于所有测试点，$1 \\le n \\le 300000$，$1 \\le q \\le 1000000$，$1 \\le a_i \\le n$，$-10^9<b_i \\leq 10^9$，$1 \\leq x, y \\leq n$，$x \\neq y$，保证对于每次查询，$c_i$ 中均至少含有一个 $1$ 与一个 $-1$。\n\n"}],"translated_statement":null,"sample_group":[["5 3\n1 2 3 1 2\n-2 3 2 -1 2\n1 2\n1 3\n2 3\n","2\n1\n5\n"],["见附加样例文件中的 ex_sequence2.in","见附加样例文件中的 ex_sequence2.out"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}