Background

小铭喜欢被电，感觉实在太爽了，一天，小铭想连续被电，他家有一个无限大的草原/*没有野马*/，现在小铭有2n个特斯拉电磁塔，特斯拉电磁塔对应后会在中间形成一条电流稳定的击穿空气，因为小铭有强迫症，他把特斯拉电磁塔（没错，小铭可以移动电磁塔！）放在X轴和Y轴上并且各放n个，为了安全，小铭让X轴和Y轴的特斯拉电磁塔一一对应且电流互不相交，现在小铭想知道他从（0,0）跑到(x,y)会被电多少下，因为小铭很有钱（刘宝宝公司CEO），所以他雇你来解决这个问题。

Input

第一行输入一个整数n，2n表示有多少个斯特拉电磁塔。
第二行n个整数，为X轴上的电磁塔位置。
第三行n个整数，为Y轴上的电磁塔位置。
第四行一个整数m，表示有多少组查询。
随后m行，每行包含两个正整数x和y，表示小铭指定的各个点的横、纵坐标。

Output

共m行，每行包含一个非负整数，表示小铭每个问题的答案。

Sample 1

Input

5
1 2 3 4 5
5 4 3 2 1
3
1 2
5 3
2 3

Output

3
5
5

Output Explanation

0 0 1 2 3 4 5 Y
0 / / / / /
1 / / !->3/

2 / / / !->5
3 / / /
4 / /
5 / !->5
X
我知道很难看懂，我也很绝望。大概就是（1，2）经过<1,1>,<2,2>,<3,3>三条线，另外两个点都过五条线。

Limitation

1000ms，512MB

Hint

对于40%的数据： n, m ≤ 10;
另有20%的数据： n, m ≤ 100;
另有20%的数据： n, m ≤ 1000;
对于100%的数据： n, m ≤ 10^5,1 ≤ x, y < 2^31。
made by chrB