Problem: Polycarp loves not only to take pictures, but also to show his photos to friends. On his personal website he has recently installed a widget that can display n photos with the scroll option. At each moment of time the widget displays exactly one photograph with the option showing the previous/next one. From the first photo, you can switch to the second one or to the n-th one, from the second photo you can switch to the third one or to the first one, etc. Thus, navigation is performed in a cycle.

Polycarp's collection consists of m photo albums, the i-th album contains ai photos. Polycarp wants to choose n photos and put them on a new widget. To make watching the photos interesting to the visitors, he is going to post pictures so that no two photos from one album were neighboring (each photo will have exactly two neighbors, the first photo's neighbors are the second and the n-th one).

Help Polycarp compile a photo gallery. Select n photos from his collection and put them in such order that no two photos from one album went one after the other.

Input

The first line contains two integers n and m (3 ≤ n ≤ 1000, 1 ≤ m ≤ 40), where n is the number of photos on the widget, and m is the number of albums. The second line contains m integers a1, a2, ..., am (1 ≤ ai ≤ 1000), where ai is the number of photos in the i-th album.

Output

Print the single number -1 if there is no solution. Otherwise, print n numbers t1, t2, ..., tn, where ti represents the number of the album of the i-th picture in the widget. The albums are numbered from 1 in the order of their appearance in the input. If there are several solutions, print any of them.

Examples

Input

4 3
1 3 5


Output

3 1 3 2


Input

10 2
5 5


Output

2 1 2 1 2 1 2 1 2 1


Input

10 3
1 10 3


Output

-1

Solution (in JAVA):

Solution:
/**
 * @author derrick20
 */

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

public class PolycarpGallery3DO implements Runnable {
    public static void main(String[] args) throws Exception {
        new Thread(null, new PolycarpGallery3DO(), ": )", 1 << 28).start();
    }

    public void run() {
        FastScanner sc = new FastScanner();
        PrintWriter out = new PrintWriter(System.out);

//        generate();
        int N = sc.nextInt();
        int M = sc.nextInt();
        /*
        Two ideas don't work:
        1. Splitting two by two
        This leads to a problem case where you are trying to alternate
        two groups by interlacing A and B: a b a b a b
        But at the end, there may be something unpaired:
        2 2 2 -> a b a b [c c]

        2. Sprinkling evenly across
        This leads to the issue where you are giving everyone equal precedence
        so you may end up with something high not being grouped with the others
        1 2 3 1 2 3 1 2 3 [3333]

        Correct way:
        For each id, we want to fill the maximum number of spots possible.
        For the first number, we can just go down, every other slot:
        1 _ 1 _ 1 _ ...
        If it doesn't reach the end, we can pick up with the next:
        1 _ 1 _ 2 _ 2 _ ...
        _ _ _
        If that wraps around, we can still go up to floor[n / 2] spots, (the
        maximum allowed). This means that any other numbers which have the
        the maximum possible number of potential frequencies will still be
        capable of filling their slots. So, the wrap around idea works out (somehow!)
        This proves that this is optimal since for each number we have the opportunity
        to fill up the maximum amount valid.

        The other ideas are faulty because we can find examples counter cases where
        a number does not have the ability to be placed to it's full maximum.
        Not sure how to formalize why though?
         */
        Pair[] a = new Pair[M];
        int sum = 0;
        for (int i = 0; i < M; i++) {
            a[i] = new Pair(i + 1, Math.min(N / 2, sc.nextInt()));
            sum += a[i].val;
        }
        if (sum < N) {
            out.println(-1);
        } else {
            Arrays.sort(a, Comparator.comparingInt(p -> -p.val));
            int[] positions = new int[N];
            int ptr = 0;
            for (int i = 0; i < N; i += 2) {
                positions[ptr++] = i;
            }
            for (int i = 1; i < N; i += 2) {
                positions[ptr++] = i;
            }
            int curr = 0;
            ptr = 0;
            int[] ans = new int[N];
            while (ptr < N) {
                int pos = positions[ptr++];
                if (a[curr].val > 0) {
                    ans[pos] = a[curr].id;
                    a[curr].val--;
                    if (a[curr].val == 0) {
                        curr++;
                        if (curr == M) {
                            break;
                        }
                    }
                }
            }
            if (ptr != N) {
                out.println(-1);
            } else {
                StringJoiner sj = new StringJoiner( " ");
                for (int x : ans) {
                    sj.add(Integer.toString(x));
                }
                out.println(sj);
            }
        }
        out.close();
    }

    static class Pair {
        int id, val;

        public Pair(int ii, int vv) {
            id = ii;
            val = vv;
        }

        public String toString() {
            return "(" + id + ", " + val + ")";
        }
    }

    static void generate() {
        int N = 20;
        int M = 10;
        System.out.println(N + " " + M);
        for (int i = 0; i < M; i++) {
            System.out.print(new Random().nextInt(7) + " ");
        }
        System.out.println();
    }

    static class FastScanner {
        private int BS = 1 << 16;
        private char NC = (char) 0;
        private byte[] buf = new byte[BS];
        private int bId = 0, size = 0;
        private char c = NC;
        private double cnt = 1;
        private BufferedInputStream in;

        public FastScanner() {
            in = new BufferedInputStream(System.in, BS);
        }

        public FastScanner(String s) {
            try {
                in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
            } catch (Exception e) {
                in = new BufferedInputStream(System.in, BS);
            }
        }

        private char getChar() {
            while (bId == size) {
                try {
                    size = in.read(buf);
                } catch (Exception e) {
                    return NC;
                }
                if (size == -1) return NC;
                bId = 0;
            }
            return (char) buf[bId++];
        }

        public int nextInt() {
            return (int) nextLong();
        }

        public int[] nextInts(int N) {
            int[] res = new int[N];
            for (int i = 0; i < N; i++) {
                res[i] = (int) nextLong();
            }
            return res;
        }

        public long[] nextLongs(int N) {
            long[] res = new long[N];
            for (int i = 0; i < N; i++) {
                res[i] = nextLong();
            }
            return res;
        }

        public long nextLong() {
            cnt = 1;
            boolean neg = false;
            if (c == NC) c = getChar();
            for (; (c < '0' || c > '9'); c = getChar()) {
                if (c == '-') neg = true;
            }
            long res = 0;
            for (; c >= '0' && c <= '9'; c = getChar()) {
                res = (res << 3) + (res << 1) + c - '0';
                cnt *= 10;
            }
            return neg ? -res : res;
        }

        public double nextDouble() {
            double cur = nextLong();
            return c != '.' ? cur : cur + nextLong() / cnt;
        }

        public double[] nextDoubles(int N) {
            double[] res = new double[N];
            for (int i = 0; i < N; i++) {
                res[i] = nextDouble();
            }
            return res;
        }

        public String next() {
            StringBuilder res = new StringBuilder();
            while (c <= 32) c = getChar();
            while (c > 32) {
                res.append(c);
                c = getChar();
            }
            return res.toString();
        }

        public String nextLine() {
            StringBuilder res = new StringBuilder();
            while (c <= 32) c = getChar();
            while (c != '\n') {
                res.append(c);
                c = getChar();
            }
            return res.toString();
        }

        public boolean hasNext() {
            if (c > 32) return true;
            while (true) {
                c = getChar();
                if (c == NC) return false;
                else if (c > 32) return true;
            }
        }
    }

    static void ASSERT(boolean assertion, String message) {
        if (!assertion) throw new AssertionError(message);
    }

    static void ASSERT(boolean assertion) {
        if (!assertion) throw new AssertionError();
    }
}