题目描述

Alice和Bob是好朋友，有一天他们带了$n$个孩子过独木桥。 为了方便，我们将问题抽象如下： 将独木桥看成一个长度无限长的实数轴，将每个孩子看作数轴上的一个实数点。数轴从左到右坐标不断增大。 孩子的位置用相对于数轴原点的点的坐标来表示。初始时$n$个点在$n$个互不相同的整点上。 每个点有一个初始朝向（从左向右或从右向左）。任何时刻所有的点都会以每秒$1$单位长度的速度匀速向所朝的方向移动。当某一时刻两个点同时移动到了同一个位置上，它们会立即改变自己的朝向（从左向右变成从右向左，反之亦然），然后继续移动。 有$q$次询问，每次询问给定$k_i$与$t_i$，询问在$t_i$秒后，孩子$k_i$目前的位置。 Bob无法同时关注这么多的孩子，请你帮帮他。

输入

第一行一个整数$n$表示孩子数，孩子从$0$开始编号。 第二行$n$个整数$p_i$，表示孩子们的初始位置。 第三行$n$个整数$d_i$，表示孩子们的初始朝向。$d_i = 0$则初始向左，$d_i = 1$则初始向右。 第四行一个整数$q$表示询问数。 接下来$q$行每行两个正整数$k_i$,$t_i$表示一个询问，询问在$t_i$秒后，孩子$k_i$（按输入顺序）目前的位置。

输出

$q$行每行一个整数表示答案。

输入样例

5
1 3 5 8 9
1 1 1 0 0
3
3 2
0 7 
1 5

输出样例

7
1
4

提示

【数据规模及约定】 对于20%的数据，$n,p_i,t_i≤10$。 另有10%的数据，$d_i$均相同。 另有20%的数据，$q≤10$。 另有15%的数据，$t_i≤100$。 另有20%的数据，$n≤1000$。 对于100%的数据，1≤n,q≤2×10^5，0≤k_i<n，0≤p_i,t_i≤10^9，di∈\{0,1\}。

评测数据说明

本题使用按题意独立构造、双实现核对的训练数据，共10个测试点，非原站或官方原始数据。总分100分。