题目描述

塔子哥是leetcode周赛的忠实玩家，他总共有$n$个账号，每个账号的分数分别为$a_i$，现在我们记录了他$m$次的比赛记录，塔子哥每次都会使用分数最低的账号参赛，请问塔子哥每次参赛后，他的所有账号的最大得分是多少

输入描述

输入包含三行

第一行两个正整数$n,m(l≤n,m≤10^5)$，分别表示塔子哥的账号个数和塔子哥新参加的比赛记录数。

第二行$n$个整数$a_i(0\le a_i\le 10^9)$，表示塔子哥每个账号目前的分数。

第三行 $m$ 个整数$b_j(0\le b_j\le 10^9)$，分别表示塔子哥每次比赛后，分数的变化值

(例如如果塔子哥使用分数为 $x$的账号参赛，那么他在参加完第$j$场数的变化值。比赛后，该账号分数会变为$x+b_j$。)

输出描述

输出包含$m$行，每行一个整数，表示塔子哥参与完第$j$场比赛后，他的所有账号的最大得分

样例

输入

5 4
1145 1200 1300 1500 1600
10 270 450 500

输出

1600
1600
1650
1800

解释

第一次和第二次询问都加在1145上，数组变成 [1425,1200,1300,1500,1600]，第三次和第四次分别加在1200和1300上