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:
//package com.company;

import java.io.*;
import java.util.*;

public class Main {
    static long TIME_START, TIME_END;

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
//        Scanner sc = new Scanner(new FileInputStream("Test.in"));
        PrintWriter pw = new PrintWriter(System.out);
//        PrintWriter pw = new PrintWriter(new FileOutputStream("Test.out"));

        Runtime runtime = Runtime.getRuntime();
        long usedMemoryBefore = runtime.totalMemory() - runtime.freeMemory();
        TIME_START = System.currentTimeMillis();
        Task t = new Task();
        t.solve(sc, pw);
        TIME_END = System.currentTimeMillis();
        long usedMemoryAfter = runtime.totalMemory() - runtime.freeMemory();
        pw.close();
        System.out.println("Memory increased:" + (usedMemoryAfter - usedMemoryBefore) / 1000000);
        System.out.println("Time used: " + (TIME_END - TIME_START) + ".");
    }

    public static class Task {

        public void solve(Scanner sc, PrintWriter pw) throws IOException {
            int n = sc.nextInt();
            int[] b = new int[n];
            int ct = 0;
            Set<Integer> s = new HashSet<>();
            for (int i = 0; i < n; i++) {
                b[i] = sc.nextInt();
                if (b[i] == 0) ct++;
                if (s.size() < 2) s.add(b[i]);
            }
            if (ct == n) {
                pw.println("YES");
                for (int i = 0; i < n; i++) {
                    pw.print(1 + " ");
                }
                pw.println();
                return;
            }
            if (s.size() == 1) {
                pw.println("NO");
                return;
            }
            long[] ret = solve(b);
            pw.println("YES");
            for (int i = 0; i < n; i++) {
                pw.print(ret[i] + " ");
            }

        }

        public long[] solve(int[] b) {
            int maxIdx = 0;
            int n = b.length;
            for (int i = 0; i < n; i++) {
                if (b[i] > b[maxIdx]) {
                    maxIdx = i;
                }
            }
            for (int i = 0; i < n; i++) {
                int prev = (i - 1 + n) % n;
                if (b[prev] != b[maxIdx] && b[i] == b[maxIdx]) {
                    maxIdx = i;
                    break;
                }
            }
            long[] a = new long[n];
            a[maxIdx] = b[maxIdx];
            for (int i = 0; i < n - 1; i++) {
                int tv = (maxIdx - i - 1 + n) % n;
                int vv = (maxIdx - i + n) % n;
                a[tv] = a[vv] + b[tv];
                int cv = (maxIdx - i - 2 + n) % n;
                if (a[tv] <= b[cv]) {
                    a[tv] += a[vv];
                }
            }
            for (int i = 0; i < n; i++) {
                if (a[i] % a[(i + 1) % n] != b[i]) return new long[]{};
            }
            return a;
        }


    }

    static class Scanner {
        StringTokenizer st;
        BufferedReader br;

        public Scanner(InputStream s) {
            br = new BufferedReader(new InputStreamReader(s));
        }

        public Scanner(FileReader s) throws FileNotFoundException {
            br = new BufferedReader(s);
        }

        public String next() throws IOException {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }

        public int nextInt() throws IOException {
            return Integer.parseInt(next());
        }

        public long nextLong() throws IOException {
            return Long.parseLong(next());
        }

        public String nextLine() throws IOException {
            return br.readLine();
        }

        public double nextDouble() throws IOException {
            return Double.parseDouble(next());
        }

        public boolean ready() throws IOException {
            return br.ready();
        }
    }
}