D. 橘猫的背包问题
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

一天，橘猫打算教塑料 01 背包，经过一番惊心动魄的讲解，塑料总算是略懂一二。

在课程结束时，橘猫打算布置 $$$10^4$$$ 个 01 背包的作业给塑料，但是造 $$$10^4$$$ 个题的数据疑似有点太麻烦了，于是他想了一道新题目：

"橘猫有 $$$n$$$ 个价格、价值不等的物品，第 $$$i$$$ 个物品的价格为 $$$p_i$$$，价值为 $$$v_i$$$。

现在塑料要来购买橘猫的物品。橘猫将所有物品按照编号顺序排成一排，并选定了一段编号区间 $$$[L,R]$$$，要求塑料只能购买编号在区间 $$$[L,R]$$$ 内的物品。

已知塑料带了 $$$P$$$ 块钱过来，请你输出他买到的物品的价值之和的最大值。

但为了让你加深对 $$$01$$$ 背包的印象，接下来我会给出 $$$Q$$$ 次独立的询问，每次询问会给出塑料可以购买的物品的编号区间和塑料携带的金额，对于每次询问，你都要输出他买到的物品的价值之和；

同时，为了让你能够老老实实地做 $$$Q$$$ 次 $$$01$$$ 背包，本题强制在线。"

塑料写了一个对每个询问区间都跑一遍 $$$01$$$ 背包的解法，但是太慢了 TAT，他希望可以尽快得到结果，于是他找到了正在参加校赛的你，请你帮帮他。

Input

本题每个测试点仅有一组测试数据。

第一行输入一个正整数 $$$n$$$ ($$$1 \leq n \leq 10^3$$$)，表示物品的数量；

第二行输入 $$$n$$$ 个正整数 $$$p_1,p_2,...,p_n$$$ ($$$1 \leq p_i \leq 10^4$$$)，表示物品的价格；

第三行输入 $$$n$$$ 个正整数 $$$v_1,v_2,...,v_n$$$ ($$$1 \leq v_i \leq 10^5$$$)，表示物品的价值；

第四行输入一个正整数 $$$Q$$$ ($$$1 \leq Q \leq 10^4$$$)，表示塑料的个数；

接下来 $$$Q$$$ 行，每行给出第 $$$i$$$ 个塑料可以挑选的编号区间和他携带的金额的加密值 $$$iL_i$$$, $$$iR_i$$$, $$$iP_i$$$ ($$$0 \leq iL_i,iR_i \leq n$$$, $$$0 \leq iP_i \leq 10^4$$$)。

为了得到真实的 $$$L_i$$$, $$$R_i$$$, $$$P_i$$$，你需要进行以下解密：

设 $$$last$$$ 为上一次询问的答案（第一次询问时 $$$last = 0$$$），则

$$$L_i = ((iL_i + last) \bmod n) + 1$$$

$$$R_i = ((iR_i + last) \bmod n) + 1$$$

此时若 $$$L_i \gt R_i$$$，则交换 $$$L_i$$$ 和 $$$R_i$$$。

$$$P_i = ((iP_i + last) \bmod 10000) + 1$$$

Output

对于每组测试数据的每个询问，输出一个正整数 $$$x$$$，表示塑料能够购得物品的最大价值。

Example
Input
5
2 3 1 5 4
3 4 1 2 8
3
2 3 7
1 5 2
2 5 6
Output
3
8
10
Note

解密后的 $$$L_i$$$, $$$R_i$$$, $$$P_i$$$ 如下：

第一组的 2 3 7 解密后为 3 4 8

第二组的 1 5 2 解密后为 4 5 6

第三组的 2 5 6 解密后为 1 4 15。