32294번 - 수열과 개구리

문제

길이가 $n$이고 양의 정수로 구성된 수열 $a$와 $b$가 있습니다. 두 수열의 인덱스는 1ドル$부터 시작합니다.

이 수열 위에 개구리 한 마리가 있습니다. 개구리는 초기에 어떤 정수 위치 1ドル \le x \le n$에서 출발하며, 자신의 위치가 수열 밖$^\dagger$이 될 때까지 다음을 반복합니다.

• $b_x$초 동안 기다린 뒤, 위치 $x-a_x$로 이동하거나 위치 $x+a_x$로 이동합니다. 이때 이동한 위치가 $x$의 새로운 값이 됩니다.

개구리가 시작하는 위치 $x$에 대해, 개구리의 위치가 수열 밖이 될 수 있는 최초의 시각을 $f(x)$초라고 정의할 때, 여러분은 $f(1),f(2),\cdots,f(n)$의 값을 모두 구해야 합니다.

$^\dagger$ 어떤 위치 $x$에 대해서, 1ドル \le x \le n$이면 수열 안, $x<1$ 또는 $x>n$이면 수열 밖이라고 부릅니다.

입력

첫 번째 줄에 두 수열의 길이 $n$이 주어집니다. (1ドル \le n \le 2 \cdot 10^5$)

두 번째 줄에 $n$개의 정수 $a_1,a_2,\dots,a_n$이 공백으로 구분되어 주어집니다. (1ドル \le a_i \le n$)

세 번째 줄에 $n$개의 정수 $b_1,b_2,\dots,b_n$이 공백으로 구분되어 주어집니다. (1ドル \le b_i \le 10^6$)

출력

한 줄에 $f(1),f(2),\cdots,f(n)$의 값을 공백으로 구분하여 순서대로 출력합니다.

문제의 제한에 따라 모든 1ドル \le i \le n$에 대해 $f(i)$가 유한함을 증명할 수 있습니다.

제한

노트

출력이 32비트 정수의 최댓값을 초과할 수 있음에 유의하세요. 값을 저장하기 위해 다음을 사용할 것을 권장합니다.

• C/C++: long long
• Java: long
• Python: int (별도의 처리를 할 필요가 없습니다.)
• 이외의 언어: 언어별 레퍼런스를 참고합니다.