Logo Daimayuan Online Judge

Home

时间限制:1 s 空间限制:1024 MB

#34. 红绿灯1

附加文件 统计

在一个城市,有一条笔直的公路,在这条公路上有 $n$个十字路口,每个路口都设有一个红绿灯,已知第$i(1\leq i < n)$到第$i+1$两个路口距离为$a_i$千米。第$i$个路口的红灯时间为$r_i$,绿灯时间为$g_i$,没有黄灯。

现在一辆车从距离$1$号路口$m$千米的位置出发,且此时所有路口的红绿灯刚好从红灯跳到绿灯,问这辆车通过每个路口的时间(不能闯红灯,这辆车的速度为$1$千米每分钟)。

注意:

  1. 这里距$1$号路口$m$千米的位置是远离$2$号路口方向的,也就是这个位置会距离$2$号路口$m+a_1$千米。

  2. 如果经过路口的时候,红绿灯刚好跳到绿灯,那么可以通过。如果刚好跳到红灯,那么无法通过。

输入格式

第一行两个正整数$n$和$m$。

第二行$n-1$个正整数$a_1, a_2, \dots, a_{n-1}$,表示路口之间的距离。

第三行 $n$个正整数$r_1, r_2, \dots, r_n$,表示红灯的时间。

第四行 $n$个正整数$g_1, g_2, \dots, g_n$,表示绿灯的时间。

输出格式

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

样例输入

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

样例输出

5
7
11
14
16

数据规模

对于 $50\%$的数据,$n\leq 1000$。

对于$100\%$的数据,$n\leq 10^5, 1\leq m, a_i\leq 10, 1\leq r_i, g_i\leq 5$。