Cho một mảng \(A[]\) có \(n\) phần tử được đánh số từ \(1\) đến \(N\).
Gọi mảng cộng dồn \(S[]\) của mảng \(A[]\) là một mảng mà \(S[i] = A[1] + A[2] + \dots + A[i]\).

Ví dụ:
Ta có mảng \(A = \{1, 3, 5, -4, 9\}\)
Thì ta sẽ có mảng \(S = \{1, 4, 9, 5, 14\}\)

Giải thích ví dụ:

• \(S[1] = A[1] = 1\)
• \(S[2] = A[1] + A[2] = 1 + 3 = 4\)
• \(S[3] = A[1] + A[2] + A[3] = 1 + 3 + 5 = 9\)
• \(S[4] = A[1] + A[2] + A[3] + A[4] = 1 + 3 + 5 + (-4) = 5\)
• \(S[5] = A[1] + A[2] + A[3] + A[4] + A[5] = 1 + 3 + 5 + (-4) + 9 = 14\)

Xây dựng mảng cộng dồn:
Ta có nhận xét như sau:

• \(S[i - 1] = A[1] + A[2] + \dots + A[i - 1]\)
• \(S[i] = A[1] + A[2] + \dots + A[i - 1] + A[i]\)
  \(\Rightarrow S[i] = S[i - 1] + A[i]\)

Vậy muốn xây dựng mảng cộng dồn \(S[]\) từ mảng \(A[]\) chúng ta sẽ thực hiện những bước sau:

• Bước 1: Tạo mảng \(A\) và mảng \(S\).
• Bước 2: Đặt \(S[0] = 0\).
• Bước 3: Cho \(i\) chạy từ \(1\) đến \(n\), chúng ta sẽ dễ dàng có \(S[i] = S[i - 1] + A[i]\).

Ứng dụng của mảng cộng dồn:
Ta có nhận xét như sau:
Đặt \(l, r\) là \(2\) số tự nhiên sao cho \(1 \le l \le r \le\) độ dài mảng \(A\).

• \(S[l] = A[1] + \dots + A[l]\)
• \(S[r] = A[1] + \dots + A[r]\)
  \(\Rightarrow S[r] - S[l - 1] = A[l] + \dots + A[r]\)
  Vậy chúng ta có thể tính tổng một đoạn con liên tiếp từ \(l\) đến \(r\) của mảng \(A\) trong \(O(1)\).

Input

• Dòng 1: Một số nguyên \(N\) là độ dài của mảng \(A[]\) (\(1 \le N \le 10^7\)).
• Dòng 2: Gồm \(N\) số nguyên \(A[1], A[2], \dots, A[N]\) (\(-10^9 \le A[i] \le 10^9\)).

Output

• Các phần tử từ \(1\) đến \(N\) của mảng \(S[]\) được in ra trên một dòng, cách nhau bởi dấu cách.

Example

5
1 3 5 -4 9

1 4 9 5 14