雷电法王——小铭
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