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.math.*;
import java.util.*;
import java.util.stream.*;

public class E {

	void submit() {
		int n = nextInt();
		long[] b = new long[n];
		for (int i = 0; i < n; i++) {
			b[i] = nextLong();
		}
		long[] a = solve(b);
		if (a == null) {
			out.println("NO");
		} else {
			out.println("YES");
			for (long x : a) {
				out.print(x + " ");
			}
			out.println();
		}
	}

	long[] solve(long[] b) {
		int n = b.length;

		boolean all0 = true;

		for (int i = 0; i < n; i++) {
			all0 &= b[i] == 0;
		}

		if (all0) {
			long[] a = new long[n];
			Arrays.fill(a, 1);
			return a;
		}

		for (int i = 0; i < n; i++) {
			if (b[i] >= b[(i + 1) % n]) {
				continue;
			}

			long[] a = new long[n];
			a[(i + 1) % n] = b[(i + 1) % n];

			for (int jj = i; jj > i - n + 1; jj--) {
				int j = jj < 0 ? jj + n : jj;
				int afterJ = (j + 1) % n;
				int befJ = (j + n - 1) % n;

				long mod = a[afterJ];
				long rem = b[j];

				if (!(rem < mod)) {
					throw new AssertionError();
				}

				long atLeast = b[befJ];

				// mod * x + rem > atLeast
				// x > (atLeast - rem) / mod

				long x = Math.floorDiv(atLeast - rem, mod) + 1;

				a[j] = mod * x + rem;
			}

			return a;
		}

		return null;
	}

	void test() {

	}

	void stress() {
		for (int tst = 0;; tst++) {
			int n = rand(2, C);
			long[] b = new long[n];
			for (int i = 0; i < n; i++) {
				b[i] = rand(0, C);
			}
			solve(b);
			if (false) {
				throw new AssertionError();
			}
			System.err.println(tst);
		}
	}

	E() throws IOException {
		is = System.in;
		out = new PrintWriter(System.out);
		submit();
		// stress();
		// test();
		out.close();
	}

	static final Random rng = new Random();
	static final int C = 5;

	static int rand(int l, int r) {
		return l + rng.nextInt(r - l + 1);
	}

	public static void main(String[] args) throws IOException {
		new E();
	}

	private InputStream is;
	PrintWriter out;

	private byte[] buf = new byte[1 << 14];
	private int bufSz = 0, bufPtr = 0;

	private int readByte() {
		if (bufSz == -1)
			throw new RuntimeException("Reading past EOF");
		if (bufPtr >= bufSz) {
			bufPtr = 0;
			try {
				bufSz = is.read(buf);
			} catch (IOException e) {
				throw new RuntimeException(e);
			}
			if (bufSz <= 0)
				return -1;
		}
		return buf[bufPtr++];
	}

	private boolean isTrash(int c) {
		return c < 33 || c > 126;
	}

	private int skip() {
		int b;
		while ((b = readByte()) != -1 && isTrash(b))
			;
		return b;
	}

	String nextToken() {
		int b = skip();
		StringBuilder sb = new StringBuilder();
		while (!isTrash(b)) {
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}

	String nextString() {
		int b = readByte();
		StringBuilder sb = new StringBuilder();
		while (!isTrash(b) || b == ' ') {
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}

	double nextDouble() {
		return Double.parseDouble(nextToken());
	}

	char nextChar() {
		return (char) skip();
	}

	int nextInt() {
		int ret = 0;
		int b = skip();
		if (b != '-' && (b < '0' || b > '9')) {
			throw new InputMismatchException();
		}
		boolean neg = false;
		if (b == '-') {
			neg = true;
			b = readByte();
		}
		while (true) {
			if (b >= '0' && b <= '9') {
				ret = ret * 10 + (b - '0');
			} else {
				if (b != -1 && !isTrash(b)) {
					throw new InputMismatchException();
				}
				return neg ? -ret : ret;
			}
			b = readByte();
		}
	}

	long nextLong() {
		long ret = 0;
		int b = skip();
		if (b != '-' && (b < '0' || b > '9')) {
			throw new InputMismatchException();
		}
		boolean neg = false;
		if (b == '-') {
			neg = true;
			b = readByte();
		}
		while (true) {
			if (b >= '0' && b <= '9') {
				ret = ret * 10 + (b - '0');
			} else {
				if (b != -1 && !isTrash(b)) {
					throw new InputMismatchException();
				}
				return neg ? -ret : ret;
			}
			b = readByte();
		}
	}
}