Company: Tredence
Difficulty: medium
Falling Bananas There are N bananas situated on a coordinate axis at positions X 1 , X 2 , ..., X N . The height of the i th banana is H i . If the i th banana falls, then other bananas in the coordinate range [X i + 1, X i + H i ] both inclusive also fall. This is a chain reaction and it pushes the other bananas too. Your task is to find the maximum coordinate that each banana reaches when it falls. Input Format The input consists of: First line: A single integer N denoting the number of bananas. Second line: N integers X 1 , X 2 , ..., X N denoting the coordinates of each banana. Third line: N integers H 1 , H 2 , ..., H N denoting the height of each banana. Output Format For each banana, print the output in a new line. Constraints 1 ≤ N ≤ 10 5 1 ≤ X i , L i ≤ 10 12 Note: The array X is always ordered in ascending order. Examples Input: 7 5 6 9 11 12 16 20 2 3 1 3 5 1 1 Output: 18 17 15 17 21 17 21 In this example, the bananas fall in a chain reaction based on their heights and posit