시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 14 8 6 60.000%

문제

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

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

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

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

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

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

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


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

입력

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

입력의 둘째 줄에 L1, L2, ..., LM이 사이에 공백을 두고 주어진다.

입력의 셋째 줄에 C1, C2, ..., CM이 사이에 공백을 두고 주어진다.

입력의 넷째 줄에 r1, r2, ..., rN이 사이에 공백을 두고 주어진다.

출력

출력의 첫 줄에 T1, T2, ..., TN을 사이에 공백을 두고 출력한다.

제한

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

예제 입력 1

3 3
3848 3073 1988
73 67 76
3 21 46

예제 출력 1

26727 198706 502312

화학 약품 1은 0초에 P1으로 들어가 11544(=3×3848)초에 P1을 빠져나와 P2로 들어간다. 이후, 20763(=11544+3×3073)초에 P2를 빠져나와 P3로 들어가며, 최종적으로 26727(=20763+3×1988)초에 P3을 빠져나온다.

화학 약품 2는 P1으로 들어가는 시각이 11617(=11544+73)초 이후여야 하며, P2로 들어가는 시각이 20830(=20763+67)초 이후여야 하며, P3로 들어가는 시각이 26803(=26727+76)초 이후여야 한다. 이 모두를 만족하는 가장 이른 P1으로 흘려보내기 시작하는 시각은 11617초이다. 이 경우, 최종적으로 P3를 빠져나오는 시각은 198706(=11617+21×(3848+3073+1988))초 이다.

같은 방식으로, 류트가 최소 시각 안에 수송 작업을 완료하고자 할 경우, 화학 약품 3은 502312초에 P3를 빠져나오게 됨을 쉽게 확인할 수 있다.