In the heart of the bustling city, Anh Ba opened a humble rice stall that quickly attracted many customers thanks to its delicious flavors and reasonable prices. Every day, the line in front of the stall grew longer as everyone wanted to enjoy his steaming hot rice bowls.

One day, Anh Ba decided to track the total money collected from each customer to better manage his revenue. Each customer who comes to buy rice will pay a certain amount, and the total revenue of the stall will gradually increase with each person. Your task is to help Anh Ba calculate the total amount of money the stall has collected after serving each customer.

Given a list of ~N~ customers, where the ~i^{th}~ customer buys a rice bowl for ~x_{i}~ dong, you need to compute the total amount of money collected by the stall after serving each customer and print the corresponding results.

Input

• The first line contains an integer ~N~ ~(1 ≤ N ≤ 10^5)~ — the number of customers visiting the stall.
• The second line contains ~N~ positive integers ~x_1, x_2,...,x_N~ ~(1 ≤ x_i ≤ 10^{9})~ — the price each ~i^{th}~ customer pays for their rice bowl.

Output

• Print ~N~ integers on a single line, where the ~i^{th}~ number represents the total amount of money collected by the stall after serving the ~i^{th}~ customer.

Example Input:

5  
2 3 7 1 5  

Example Output:

2 5 12 13 18  

Explanation:

• Customer ~1~ pays ~2~ dong → Total money: ~2~
• Customer ~2~ pays ~3~ dong → Total money: ~2 + 3 = 5~
• Customer ~3~ pays ~7~ dong → Total money: ~5 + 7 = 12~
• Customer ~4~ pays ~1~ dong → Total money: ~12 + 1 = 13~
• Customer ~5~ pays ~5~ dong → Total money: ~13 + 5 = 18~