1751: 中山市第十二届义务教育段学生信息学邀请赛:糖果共享（share）
题目描述
糖果共享（share）
【问题描述】
Jimmy 要和其他同学们一起分享老师带来的糖果了！ 可是， 老师不想让同学们这么快就 领到糖果，于是决定跟大家玩一个分享糖果的游戏。
老师让 n 个同学们围成一圈坐在一起。接下来， 对于第 i 个同学， 老师会在第 ti 秒发给 TA 一份糖果； 每次得到糖果之后，第 i 个同学会固定等待 pi 秒， 然后把糖果分给身旁的第 i + 1 个同学（特殊的情况是， 第 n 个同学会把糖果分给第 1 个同学）。注意每个同学既可以 从老师那里得到糖果， 也可以从旁边的同学那里得到糖果， 而且老师发的糖果足够多， 同学 们只要收到了糖果， 就一定能将糖果分出去。同学们的分糖果动作非常快， 可以认为是不占 用时间的。
在参与游戏的同时， Jimmy 很想知道他的几个好朋友们最快什么时候能得到糖果。你能 帮帮他吗？
【输入格式】
第一行一个整数 n，表示同学们的数量。
第二行 n 个整数 t1 , t2 , · · · , tn ，表示每个同学收到老师给的糖果的时刻。
第三行 n 个整数 p1 , p2 , · · · , pn，表示每个同学收到糖果之后、将糖果分出去之前等待的 时间。
第四行一个整数 q，表示 Jimmy 的询问数量。
接下来 q 行， 每行一个整数 xi ，表示 Jimmy 想问第 xi 个同学最快什么时候能得到糖 果。
【输出格式】
输出共 q 行，每行一个整数，表示每个询问对应的答案。
输入格式
第一行一个整数 n，表示同学们的数量。
第二行 n 个整数 t1 , t2 , · · · , tn ，表示每个同学收到老师给的糖果的时刻。
第三行 n 个整数 p1 , p2 , · · · , pn，表示每个同学收到糖果之后、将糖果分出去之前等待的 时间。
第四行一个整数 q，表示 Jimmy 的询问数量。
接下来 q 行， 每行一个整数 xi ，表示 Jimmy 想问第 xi 个同学最快什么时候能得到糖 果。
输出格式
输出共 q 行，每行一个整数，表示每个询问对应的答案。
输入样例 复制
3
4 1 5
3 10 100
2
2
3输出样例 复制
7
8提示
【测试点约束】
对于 30% 的数据，保证 1 ≤ n, q ≤ 5000。
对于 100% 的数据，保证 1 ≤ n, q ≤ 2 × 105 ，1 ≤ ti , pi ≤ 109 ，1 ≤ xi ≤ n。
【样例 1 解释】
以下是游戏开始后，每个时刻发生的事件：
1. 第 3 秒，第 1 个同学领到了老师给的一份糖果；
2. 第 7 秒，第 1 个同学将糖果分给了第 2 个同学（糖果是老师给的）；
3. 第 8 秒，第 2 个同学将糖果分给了第 3 个同学（糖果是第 1 个同学给的）； 4. 第 10 秒，第 2 个同学领到了老师给的一份糖果；
5. 第 11 秒，第 2 个同学将糖果分给了第 3 个同学（糖果是老师给的）； 6. 第 13 秒，第 3 个同学领到了老师给的一份糖果；
可知，第 2 个同学最快在第 7 秒得到了糖果；第 3 个同学最快在第 8 秒得到了糖果。
接下来， 游戏还会继续下去， 同学们还会继续互相分糖果， 但是不会再改变 Jimmy 问 题的答案了。