16855번 - 일해라, 류트!

디디포스 주식회사에 다니는 류트는 회사의 코딩 테스트를 출제하는 업무를 맡게 되었다. 그는 '고양이 소개팅'이란 문제를 출제했지만, 일하기 귀찮다는 이유로 정해를 짜지 않았고^[1] 디디에 의해 해고당했다. 일자리를 잃은 류트는 러시아로 이사를 가서 새로운 직업을 찾게 되었다.

우여곡절 끝에 러시아의 화학 공학 기업에서 근무하게 된 류트는 블라디보스토크에서 모스크바로 몇 개의 파이프를 거쳐 여러 화학 약품을 옮기려고 한다. 블라디보스토크에서 모스크바로 화학 약품을 파이프를 통해 수송하려면 총 M개의 파이프 P₁, P₂, ..., P_M을 차례로 거쳐야 한다. 각각의 i = 1, 2, ..., M 에 대하여 P_i의 길이는 L_i이다.

류트가 옮기려는 화학 약품은 총 N가지 종류이다. 편의상 이들에 1, 2, 3, ..., N의 번호를 붙이자. 참고로, 각각의 1 ≤ i < j ≤ N에 대하여 화학 약품 i는 화학 약품 j 보다 먼저 수송되어야 한다.

각각의 i = 1, 2, ..., N에 대하여 화학 약품 i의 점성계수는 r_i이다. 점성계수가 r인 화학 약품을 길이가 L인 파이프로 시각 t부터 흘려보내기 시작했다면, 이 화학 약품은 시각 t+rl 직전에 해당 파이프를 완전히 빠져나온다. 다시 말해, [t, t+rl) 동안 해당 파이프를 통과한다.

류트는 여러 화학 약품이 섞일 것을 염려하여, 각각의 i = 1, 2, ..., M에 대하여 하나의 화학 약품이 P_i를 통과한 후, C_i 만큼의 시간이 지나기 이전에는 다른 화학 약품이 P_i에 들어오는 일이 없도록 하고자 한다. (이러한 C_i들은 류트가 나름의 기준을 가지고 정해놓은 값으로 입력을 통해 주어질 것이다.)

또한, i = 1, 2, ..., M-1에 대하여 화학 약품이 P_i를 빠져 나온 직후에 바로 P_i+1로 들어가야한다. 다시 말해, 화학 약품이 파이프들을 거쳐 흘러가는 도중에 멈추어서는 안 된다.

류트가 시각 0부터 시작하여 화학 약품들을 파이프로 흘려보낸다고 하자. 류트는 최소 시간 안에 수송 작업을 완료하고자 한다. 류트가 최소 시간 안에 수송 작업을 완료할 경우 i = 1, 2, ..., N에 대하여 화학 약품 i가 P_N을 빠져나오는 시각을 T_i라 하자. 이 때, T₁, T₂, ..., T_N을 구해보자.

^[1] 실제로 정해를 짜지 않았습니다.😡 이를 한심하게 여긴 디디가 대신 풀어준 바람에 류트는 풀이도 모릅니다.

입력의 첫 줄에 N, M이 사이에 공백을 두고 주어진다.

입력의 둘째 줄에 L₁, L₂, ..., L_M이 사이에 공백을 두고 주어진다.

입력의 셋째 줄에 C₁, C₂, ..., C_M이 사이에 공백을 두고 주어진다.

입력의 넷째 줄에 r₁, r₂, ..., r_N이 사이에 공백을 두고 주어진다.

출력의 첫 줄에 T₁, T₂, ..., T_N을 사이에 공백을 두고 출력한다.

• 1 ≤ N ≤ 2,000,000
• 1 ≤ M ≤ 2,500
• 각각의 i = 1, 2, ..., N에 대하여 1 ≤ r_i ≤ 100
• 각각의 i = 1, 2, ..., M에 대하여 1 ≤ L_i ≤ 10,000, 1 ≤ C_i ≤ 100
• 주어지는 입력은 모두 정수이다.