#include <bits/stdc++.h>
using namespace std;
void tpm(long long int a[], long long int b[], long long int c[],
         long long int s, long long int m, long long int e) {
  long long int l1 = m - s + 1;
  long long int l2 = e - m;
  long long int t1[l1], y1[l1], c1[l1];
  long long int t2[l2], y2[l2], c2[l2];
  for (long long int i = 0; i < l1; i++) {
    t1[i] = a[s + i];
    y1[i] = b[s + i];
    c1[i] = c[s + i];
  }
  for (long long int i = 0; i < l2; i++) {
    t2[i] = a[m + 1 + i];
    y2[i] = b[m + 1 + i];
    c2[i] = c[m + 1 + i];
  }
  long long int i = 0, j = 0;
  long long int k = s;
  while (i < l1 && j < l2) {
    if (t1[i] < t2[j]) {
      a[k] = t1[i];
      b[k] = y1[i];
      c[k] = c1[i];
      i++;
      k++;
    } else if (t1[i] == t2[j]) {
      if (y1[i] < y2[j]) {
        a[k] = t1[i];
        b[k] = y1[i];
        c[k] = c1[i];
        i++;
        k++;
      } else {
        a[k] = t2[j];
        b[k] = y2[j];
        c[k] = c2[j];
        j++;
        k++;
      }
    } else {
      a[k] = t2[j];
      b[k] = y2[j];
      c[k] = c2[j];
      j++;
      k++;
    }
  }
  while (i < l1) {
    a[k] = t1[i];
    b[k] = y1[i];
    c[k] = c1[i];
    i++;
    k++;
  }
  while (j < l2) {
    a[k] = t2[j];
    b[k] = y2[j];
    c[k] = c2[j];
    j++;
    k++;
  }
}
void sor(long long int a[], long long int b[], long long int c[],
         long long int s, long long int e) {
  if (s < e) {
    long long int m = (s + e) / 2;
    sor(a, b, c, s, m);
    sor(a, b, c, m + 1, e);
    tpm(a, b, c, s, m, e);
  }
}
long long int upperIndex(long long int arr[], long long int n,
                         long long int y) {
  long long int l = 0, h = n - 1;
  while (l <= h) {
    long long int mid = (l + h) / 2;
    if (arr[mid] <= y)
      l = mid + 1;
    else
      h = mid - 1;
  }
  return h;
}
int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  long long int n;
  cin >> n;
  long long int a[n + 1];
  long long int sum[n];
  vector<long long int> v;
  for (long long int i = 1; i <= n - 1; i++) {
    cin >> a[i];
    if (i > 1)
      sum[i] = sum[i - 1] + a[i];
    else
      sum[i] = a[i];
    v.push_back(sum[i]);
  }
  sort(v.begin(), v.end());
  long long int c = 0;
  long long int x;
  for (long long int i = 0; i < v.size(); i++) {
    if (v[i] > 0) {
      if (i == 0) x = v[i];
    } else {
      c++;
      if (i == 0) x = v[i];
    }
    if (v[i] == 0) {
      cout << -1;
      exit(0);
    }
  }
  for (long long int i = 0; i < v.size(); i++) {
    if (v[i] != x) {
      cout << -1;
      exit(0);
    } else {
      if (x != -1)
        x++;
      else
        x = 1;
    }
  }
  long long int m = 1 + c;
  vector<long long int> ans;
  ans.push_back(m);
  if (ans[0] < 1 || ans[0] > n) {
    cout << -1;
    exit(0);
  }
  for (long long int i = 1; i <= n - 1; i++) {
    ans.push_back(sum[i] + m);
    if (ans[i] < 1 || ans[i] > n) {
      cout << -1;
      exit(0);
    }
  }
  for (long long int i = 0; i < n; i++) {
    cout << ans[i] << " ";
  }
}

### Prompt

Your task is to create a cpp solution to the following problem:

An array of integers p_1, p_2, ..., p_n is called a permutation if it contains each number from 1 to n exactly once. For example, the following arrays are permutations: [3, 1, 2], [1], [1, 2, 3, 4, 5] and [4, 3, 1, 2]. The following arrays are not permutations: [2], [1, 1], [2, 3, 4].

Polycarp invented a really cool permutation p_1, p_2, ..., p_n of length n. It is very disappointing, but he forgot this permutation. He only remembers the array q_1, q_2, ..., q_{n-1} of length n-1, where q_i=p_{i+1}-p_i.

Given n and q=q_1, q_2, ..., q_{n-1}, help Polycarp restore the invented permutation.

Input

The first line contains the integer n (2 ≤ n ≤ 2⋅10^5) — the length of the permutation to restore. The second line contains n-1 integers q_1, q_2, ..., q_{n-1} (-n < q_i < n).

Output

Print the integer -1 if there is no such permutation of length n which corresponds to the given array q. Otherwise, if it exists, print p_1, p_2, ..., p_n. Print any such permutation if there are many of them.

Examples

Input


3
-2 1


Output


3 1 2 

Input


5
1 1 1 1


Output


1 2 3 4 5 

Input


4
-1 2 2


Output


-1

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
void tpm(long long int a[], long long int b[], long long int c[],
         long long int s, long long int m, long long int e) {
  long long int l1 = m - s + 1;
  long long int l2 = e - m;
  long long int t1[l1], y1[l1], c1[l1];
  long long int t2[l2], y2[l2], c2[l2];
  for (long long int i = 0; i < l1; i++) {
    t1[i] = a[s + i];
    y1[i] = b[s + i];
    c1[i] = c[s + i];
  }
  for (long long int i = 0; i < l2; i++) {
    t2[i] = a[m + 1 + i];
    y2[i] = b[m + 1 + i];
    c2[i] = c[m + 1 + i];
  }
  long long int i = 0, j = 0;
  long long int k = s;
  while (i < l1 && j < l2) {
    if (t1[i] < t2[j]) {
      a[k] = t1[i];
      b[k] = y1[i];
      c[k] = c1[i];
      i++;
      k++;
    } else if (t1[i] == t2[j]) {
      if (y1[i] < y2[j]) {
        a[k] = t1[i];
        b[k] = y1[i];
        c[k] = c1[i];
        i++;
        k++;
      } else {
        a[k] = t2[j];
        b[k] = y2[j];
        c[k] = c2[j];
        j++;
        k++;
      }
    } else {
      a[k] = t2[j];
      b[k] = y2[j];
      c[k] = c2[j];
      j++;
      k++;
    }
  }
  while (i < l1) {
    a[k] = t1[i];
    b[k] = y1[i];
    c[k] = c1[i];
    i++;
    k++;
  }
  while (j < l2) {
    a[k] = t2[j];
    b[k] = y2[j];
    c[k] = c2[j];
    j++;
    k++;
  }
}
void sor(long long int a[], long long int b[], long long int c[],
         long long int s, long long int e) {
  if (s < e) {
    long long int m = (s + e) / 2;
    sor(a, b, c, s, m);
    sor(a, b, c, m + 1, e);
    tpm(a, b, c, s, m, e);
  }
}
long long int upperIndex(long long int arr[], long long int n,
                         long long int y) {
  long long int l = 0, h = n - 1;
  while (l <= h) {
    long long int mid = (l + h) / 2;
    if (arr[mid] <= y)
      l = mid + 1;
    else
      h = mid - 1;
  }
  return h;
}
int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  long long int n;
  cin >> n;
  long long int a[n + 1];
  long long int sum[n];
  vector<long long int> v;
  for (long long int i = 1; i <= n - 1; i++) {
    cin >> a[i];
    if (i > 1)
      sum[i] = sum[i - 1] + a[i];
    else
      sum[i] = a[i];
    v.push_back(sum[i]);
  }
  sort(v.begin(), v.end());
  long long int c = 0;
  long long int x;
  for (long long int i = 0; i < v.size(); i++) {
    if (v[i] > 0) {
      if (i == 0) x = v[i];
    } else {
      c++;
      if (i == 0) x = v[i];
    }
    if (v[i] == 0) {
      cout << -1;
      exit(0);
    }
  }
  for (long long int i = 0; i < v.size(); i++) {
    if (v[i] != x) {
      cout << -1;
      exit(0);
    } else {
      if (x != -1)
        x++;
      else
        x = 1;
    }
  }
  long long int m = 1 + c;
  vector<long long int> ans;
  ans.push_back(m);
  if (ans[0] < 1 || ans[0] > n) {
    cout << -1;
    exit(0);
  }
  for (long long int i = 1; i <= n - 1; i++) {
    ans.push_back(sum[i] + m);
    if (ans[i] < 1 || ans[i] > n) {
      cout << -1;
      exit(0);
    }
  }
  for (long long int i = 0; i < n; i++) {
    cout << ans[i] << " ";
  }
}

```