题目描述

小码君要赶上学校上学，但是路上有着非常非常多的红绿灯，已知相邻的两个路口距离为 $A_i$ 千米 $(1\le i < N)$，每个路口的红灯时间为 $R_i$，绿灯时间为 $G_i$，没有黄灯，现在有一辆车从距离 $1$ 号十字路口 $M$ 千米的位置出发，且此时所有路口的红绿灯刚好从红灯跳到绿灯，问这辆车通过每个路口的时间(不能闯红灯，这辆车的速度为 $1$ 千米每分钟)。

输入格式

第一行两个正整数 $N$ 和 $M$

第二行 $N-1$ 个正整数 $A_i$

第三行 $N$ 个正整数 $R_i$，为红灯时间（分钟）

第四行 $N$ 个正整数 $G_i$，为绿灯时间（分钟）

输出格式

共 $N$ 行，每行一个正整数，为这辆车通过每个十字路口的最早时间。

样例 #1

样例输入 #1

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

样例输出 #1

5
7
11
14
16

提示

对于 $50\%$ 的数据 $N\le 1000$；

对于 $100\%$ 的数据 $N\le 10^5$，$M,A_i\le 10$，$R_i，G_i\le 5$。