在冒险岛这款游戏中，有一个著名的山洞副本，里面有丰富的宝藏，引来了许多勇者前来挑战。

不幸的是，山洞中有 N 个怪物，第 i 个怪物的防御力为 A_i , 奖励值为 B_i ， M 个勇者依次前来挑战。 

假设一位勇者初始的战斗力为 X , 当你的战斗力**大于**怪物的防御力 A_i 时，你才可以击败它，并且获得奖励值 B_i 的战斗力提升。

幸运的是，每位勇者都深知自己的战斗力不一定充足,所以他会在进入山洞战斗前进行训练,以此来提升他的战斗力，并且勇者都是很聪明的，每位勇者都可以选择**任意顺序**来击败怪物,一个怪物只能被击败一次。

**具体来说：假设训练总天数为 n ,** **勇者第 i 天的战斗力提升为** min(i,n-i+1) 

因为勇者都希望自己能尽快穿越山洞，请你帮助每位勇者计算他**最少**训练多少天可以击败所有怪物？

你可以认为不同的勇者之间是**互相独立**的，副本中的怪物会重新恢复状态。

第一行 1 个正整数 N , 表示怪物的数量

第二行 N 个正整数 A_1, A_2, \ldots, A_N。即每个怪物的防御力

第三行 N 个正整数 B_1, B_2, \ldots, B_N。即每个怪物的奖励值

第四行 1 个正整数 M , 表示有 M 个勇者前来挑战

接下来 M 行，每行输入 1 个正整数 X , 表示这名勇者的初始战斗力值

输出 1 行 M 个整数，表示每名勇者最少需要训练的天数。

样例说明

- 第一组样例中，一共有 3 位勇者前来挑战。

- 第一位勇者锻炼 4 天 , 攻击力为 1+1+2+2+1=7 ，然后可以击败所有怪物

- 第二位勇者锻炼 2 天 , 攻击力为 5+1+1=7 ，可以击败所有怪物

- 第三位勇者锻炼 3 天 , 攻击力为 4+1+2+1=8 ，可以击败所有怪物

数据范围

- 对于 30\% 的数据，1\le  N , M  \le 100 ,  1\ \leq X,A_i,B_i \leq 100

- 对于 100\% 的数据， 1\le  N,M \leq 2\times 10^5 , 1\leq  X,A_i,B_i \leq 10^9