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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.BufferedWriter;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author BSRK Aditya
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        OutputWriter out = new OutputWriter(outputStream);
        ERestoreArray solver = new ERestoreArray();
        solver.solve(1, in, out);
        out.close();
    }

    static class ERestoreArray {
        int n;

        public void solve(int testNumber, InputReader in, OutputWriter out) {
            n = in.readInt();
            int[] b = new int[n + 1];
            for (int i = 1; i <= n; ++i)
                b[i] = in.readInt();

            long[] a = new long[n + 1];
            boolean entered = false;
            for (int i = 1; !entered && i <= n; ++i)
                if (b[i] > b[less(i)]) {
                    entered = true;
                    a[i] = b[i];
                    //out.printLine("computed", i);
                    long offset = 100000L;
                    int ci = i;
                    for (int j = n - 1; j > 0; --j) {
                        a[less(ci)] = a[ci] + b[less(ci)];
                        //out.printLine("computed", less(ci));
                        if (j == n - 1)
                            a[less(ci)] += offset * a[ci];
                        ci = less(ci);
                    }
                /*for (int j = 1; j <= n; ++j) {
                    if (a[more(j)] == 0 || a[j]%a[more(j)] != b[j]) {
                        out.printLine("did not work!");
                    }
                }*/
                    out.printLine("YES");
                    for (int j = 1; j <= n; ++j)
                        out.print(a[j], j == n ? '\n' : ' ');
                }
            if (!entered) {
                if (b[1] == 0) {
                    out.printLine("YES");
                    for (int i = 1; i <= n; ++i)
                        out.print(1, i == n ? '\n' : ' ');
                } else
                    out.printLine("NO");
            }
        }

        int less(int x) {
            return x == 1 ? n : (x - 1);
        }

    }

    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private InputReader.SpaceCharFilter filter;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {
            if (numChars == -1)
                throw new InputMismatchException();
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }

        public int readInt() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public boolean isSpaceChar(int c) {
            if (filter != null)
                return filter.isSpaceChar(c);
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);

        }

    }

    static class OutputWriter {
        private final PrintWriter writer;

        public OutputWriter(OutputStream outputStream) {
            writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
        }

        public OutputWriter(Writer writer) {
            this.writer = new PrintWriter(writer);
        }

        public void print(Object... objects) {
            for (int i = 0; i < objects.length; i++) {
                if (i != 0)
                    writer.print(' ');
                writer.print(objects[i]);
            }
        }

        public void printLine(Object... objects) {
            print(objects);
            writer.println();
        }

        public void close() {
            writer.close();
        }

    }
}