Problem: While discussing a proper problem A for a Codeforces Round, Kostya created a cyclic array of positive integers a_1, a_2, …, a_n. Since the talk was long and not promising, Kostya created a new cyclic array b_1, b_2, …, b_{n} so that b_i = (a_i mod a_{i + 1}), where we take a_{n+1} = a_1. Here mod is the [modulo operation](https://en.wikipedia.org/wiki/Modulo_operation). When the talk became interesting, Kostya completely forgot how array a had looked like. Suddenly, he thought that restoring array a from array b would be an interesting problem (unfortunately, not A).

Input

The first line contains a single integer n (2 ≤ n ≤ 140582) — the length of the array a.

The second line contains n integers b_1, b_2, …, b_{n} (0 ≤ b_i ≤ 187126).

Output

If it is possible to restore some array a of length n so that b_i = a_i mod a_{(i mod n) + 1} holds for all i = 1, 2, …, n, print «YES» in the first line and the integers a_1, a_2, …, a_n in the second line. All a_i should satisfy 1 ≤ a_i ≤ 10^{18}. We can show that if an answer exists, then an answer with such constraint exists as well.

It it impossible to restore any valid a, print «NO» in one line.

You can print each letter in any case (upper or lower).

Examples

Input

4
1 3 1 0


Output

YES
1 3 5 2


Input

2
4 4


Output

NO

Note

In the first example:

  * 1 mod 3 = 1 
  * 3 mod 5 = 3 
  * 5 mod 2 = 1 
  * 2 mod 1 = 0 

Solution (in JAVA):

Solution:
import java.io.*;
import java.util.*;

@SuppressWarnings("WeakerAccess")
public class Main {

    final boolean ONLINE_JUDGE = System.getProperty("ONLINE_JUDGE") != null;
    BufferedReader in;
    PrintWriter out;
    StringTokenizer tok = new StringTokenizer("");

    public static void main(String[] args) {
        new Main().run();
        // Sworn to fight and die
    }

    void init() throws FileNotFoundException {
        if (ONLINE_JUDGE) {
            in = new BufferedReader(new InputStreamReader(System.in));
            out = new PrintWriter(System.out);
        } else {
            in = new BufferedReader(new FileReader("input.txt"));
            out = new PrintWriter("output.txt");
        }
    }

    String readString() throws IOException {
        while (!tok.hasMoreTokens()) {
            tok = new StringTokenizer(in.readLine());
        }
        return tok.nextToken();
    }

    int readInt() throws IOException {
        return Integer.parseInt(readString());
    }

    long readLong() throws IOException {
        return Long.parseLong(readString());
    }

    double readDouble() throws IOException {
        return Double.parseDouble(readString());
    }

    public void run() {
        try {
            long t1 = System.currentTimeMillis();
            init();
            solve();
            out.close();
            long t2 = System.currentTimeMillis();
            System.err.println("Time = " + (t2 - t1));
        } catch (Exception e) {
            e.printStackTrace(System.err);
            System.exit(-1);
        }
    }

    class Point {
        double [] a;

        public Point(int n) {
            this.a = new double[n];
        }

        double scalar(Point b) {
            double result = 0;
            for (int i = 0; i < a.length; i++) {
                result += a[i] * b.a[i];
            }

            return result;
        }

        double len() {
            double res = 0;

            for (int i = 0; i < a.length; i++) {
                res += (a[i] * a[i]);
            }

            return Math.sqrt(res);
        }

        double dist(Point b) {
            double res = 0;

            for (int i = 0; i < a.length; i++) {
                res += ((a[i] - b.a[i]) * (a[i] - b.a[i]));
            }

            return Math.sqrt(res);
        }

        void alphaScalar(double alpha) {
            for (int i = 0; i < a.length; i++) {
                a[i] *= alpha;
            }
        }

    }

    public class LOL implements Comparable<LOL> {
        int a;
        int b;
        public LOL(int a, int b) {
            this.a = a;
            this.b = b;
        }
        public int compareTo(LOL o) {

            int xCompare = Integer.compare(o.a, a);

            if (xCompare != 0) {
                return xCompare;
            }

            return Integer.compare(o.b, b);
        }
    }

    public LOL getIntersection(int a1, int b1, int a2, int b2) {
        int start = Math.max(a1, a2);
        int end = Math.min(b1, b2);
        if (start <= end) {
            return new LOL(start, end);
        }
        return null;
    }

    public void solve() throws IOException {
        int n = readInt();

        int[] a = new int[n];

        int max = 0;

        for (int i = 0; i < n; i++) {
            a[i] = readInt();
            max = Math.max(a[i], max);
        }

        int pos = -1;

        for (int i = 0; i < n; i++) {
            if (a[i] == max && a[(i - 1 + n) % n] < max) {
                pos = i;
            }
        }

        if (pos == -1) {
            if (a[0] == 0) {
                out.println("YES");
                for (int i = 0; i < n; i++) {
                    out.print(1 + " ");
                }
                return;
            } else {
                out.print("NO");
                return;
            }
        }

        int delta = n - pos - 1;

        long[] b = new long[n];

        for (int i = 0; i < n; i++) {
            b[(i + delta) % n] = a[i];
        }

        long[] res = new long[n];
        long sum = 0;
        for (int i = n - 2; i >= 0; i--) {
            sum += b[i];
            res[i] = sum + b[n - 1] * 2;
        }
        res[n - 1] = b[n - 1];

        long[] ans = new long[n];
        for (int i = 0; i < n; i++) {
            ans[(i - delta + n) % n] = res[i];
        }

        res[n - 1] = b[n - 1];
        out.println("YES");
        for (int i = 0; i < n; i++) {
            out.print(ans[i] + " ");
        }

    }

}