#include <bits/stdc++.h>
using namespace std;
const long long int pinf = ((long long int)2e18);
const long long int ninf = ((long long int)-2e18);
const long long int mod = 1000000007;
struct custom_hash {
  static uint64_t splitmix64(uint64_t x) {
    x += 0x9e3779b97f4a7c15;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
  }
  size_t operator()(uint64_t x) const {
    static const uint64_t FIXED_RANDOM =
        chrono::steady_clock::now().time_since_epoch().count();
    return splitmix64(x + FIXED_RANDOM);
  }
};
long long int find_mex(vector<long long int> a) {
  unordered_map<long long int, long long int, custom_hash> umap;
  for (auto i : a) {
    umap[a[i]]++;
  }
  for (long long int i = 0;; i++) {
    if (!umap[i]) {
      return i;
    }
  }
  return 0;
}
long long int sum_dig(long long int n) {
  long long int count = 0;
  while (n) {
    count += n % 10;
    n /= 10;
  }
  return count;
}
long long int _pow(long long int a, long long int b) {
  if (!b) return 1;
  long long int temp = _pow(a, b / 2);
  temp = (temp * temp);
  if (b % 2) return (a * temp);
  return temp;
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  {
    long long int max_f = 0, ma, count1 = 0, p, ans = 1, j, k, i,
                  min_e = INT_MAX, max_e = INT_MIN, count = 0, change = 0, m,
                  min_ops = INT_MAX, q, W, max_sum = 0, temp_sum = 0, even = 0,
                  odd = 0, n;
    cin >> n;
    vector<long long int> d(n - 1), pref(n), sol;
    for (i = 0; i < n - 1; i++) {
      cin >> d[i];
    }
    pref[0] = 0;
    for (i = 1; i < n; i++) {
      pref[i] = pref[i - 1] + d[i - 1];
    }
    long long int p1 = (-1) * (*min_element(pref.begin(), pref.end())) + 1;
    set<long long int> s;
    s.insert(p1);
    sol.push_back(p1);
    for (i = 1; i < n; i++) {
      s.insert(p1 + pref[i]);
      sol.push_back(p1 + pref[i]);
    }
    if (s.size() == n) {
      count = 1;
      for (auto i : s) {
        if (i != count) {
          ans = 0;
          break;
        }
        count++;
      }
    } else {
      ans = 0;
    }
    if (ans) {
      for (i = 0; i < n; i++) {
        cout << sol[i] << " ";
      }
    } else {
      cout << -1;
    }
  }
  return 0;
}

### Prompt

Create a solution in CPP for 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;
const long long int pinf = ((long long int)2e18);
const long long int ninf = ((long long int)-2e18);
const long long int mod = 1000000007;
struct custom_hash {
  static uint64_t splitmix64(uint64_t x) {
    x += 0x9e3779b97f4a7c15;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
  }
  size_t operator()(uint64_t x) const {
    static const uint64_t FIXED_RANDOM =
        chrono::steady_clock::now().time_since_epoch().count();
    return splitmix64(x + FIXED_RANDOM);
  }
};
long long int find_mex(vector<long long int> a) {
  unordered_map<long long int, long long int, custom_hash> umap;
  for (auto i : a) {
    umap[a[i]]++;
  }
  for (long long int i = 0;; i++) {
    if (!umap[i]) {
      return i;
    }
  }
  return 0;
}
long long int sum_dig(long long int n) {
  long long int count = 0;
  while (n) {
    count += n % 10;
    n /= 10;
  }
  return count;
}
long long int _pow(long long int a, long long int b) {
  if (!b) return 1;
  long long int temp = _pow(a, b / 2);
  temp = (temp * temp);
  if (b % 2) return (a * temp);
  return temp;
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  {
    long long int max_f = 0, ma, count1 = 0, p, ans = 1, j, k, i,
                  min_e = INT_MAX, max_e = INT_MIN, count = 0, change = 0, m,
                  min_ops = INT_MAX, q, W, max_sum = 0, temp_sum = 0, even = 0,
                  odd = 0, n;
    cin >> n;
    vector<long long int> d(n - 1), pref(n), sol;
    for (i = 0; i < n - 1; i++) {
      cin >> d[i];
    }
    pref[0] = 0;
    for (i = 1; i < n; i++) {
      pref[i] = pref[i - 1] + d[i - 1];
    }
    long long int p1 = (-1) * (*min_element(pref.begin(), pref.end())) + 1;
    set<long long int> s;
    s.insert(p1);
    sol.push_back(p1);
    for (i = 1; i < n; i++) {
      s.insert(p1 + pref[i]);
      sol.push_back(p1 + pref[i]);
    }
    if (s.size() == n) {
      count = 1;
      for (auto i : s) {
        if (i != count) {
          ans = 0;
          break;
        }
        count++;
      }
    } else {
      ans = 0;
    }
    if (ans) {
      for (i = 0; i < n; i++) {
        cout << sol[i] << " ";
      }
    } else {
      cout << -1;
    }
  }
  return 0;
}

```