Arnie the Worm has finished eating an apple house yet again and decided to move. He made up his mind on the plan, the way the rooms are located and how they are joined by corridors. He numbered all the rooms from 1 to n. All the corridors are bidirectional.

Arnie wants the new house to look just like the previous one. That is, it should have exactly n rooms and, if a corridor from room i to room j existed in the old house, it should be built in the new one. 

We know that during the house constructing process Arnie starts to eat an apple starting from some room and only stops when he eats his way through all the corridors and returns to the starting room. It is also known that Arnie eats without stopping. That is, until Arnie finishes constructing the house, he is busy every moment of his time gnawing a new corridor. Arnie doesn't move along the already built corridors.

However, gnawing out corridors in one and the same order any time you change a house is a very difficult activity. That's why Arnie, knowing the order in which the corridors were located in the previous house, wants to gnaw corridors in another order. It is represented as a list of rooms in the order in which they should be visited. The new list should be lexicographically smallest, but it also should be strictly lexicographically greater than the previous one. Help the worm. 

Input

The first line contains two integers n and m (3 ≤ n ≤ 100, 3 ≤ m ≤ 2000). It is the number of rooms and corridors in Arnie's house correspondingly. The next line contains m + 1 positive integers that do not exceed n. They are the description of Arnie's old path represented as a list of rooms he visited during the gnawing. It is guaranteed that the last number in the list coincides with the first one.

The first room described in the list is the main entrance, that's why Arnie should begin gnawing from it.

You may assume that there is no room which is connected to itself and there is at most one corridor between any pair of rooms. However, it is possible to find some isolated rooms which are disconnected from others.

Output

Print m + 1 positive integers that do not exceed n. Those numbers are the description of the new path, according to which Arnie should gnaw out his new house. If it is impossible to find new path you should print out No solution. The first number in your answer should be equal to the last one. Also it should be equal to the main entrance.

Examples

Input

3 3
1 2 3 1


Output

1 3 2 1 

Input

3 3
1 3 2 1


Output

No solution
import java.util.NoSuchElementException;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Iterator;
import java.io.IOException;
import java.util.Arrays;
import java.util.TreeSet;
import java.io.InputStream;
import java.io.FilterInputStream;
import java.util.HashMap;
import java.io.BufferedInputStream;

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

class Task_D_Wormhole {

    public FlowGraph g;
    public boolean[] used;
    public int[] vertices;
    public IntDeque solution = new IntDeque();

    public void solve(int testNumber, InputUtil in, PrintWriter out) {
        g = new FlowGraph(in.nextInt());
        int edges = in.nextInt();

        vertices = in.nextIntArray(edges + 1);
        used = new boolean[edges << 3];
        IntArrayUtil.decrement(vertices);

        for (int i = 0; i < edges; i++) {
            g.addUndirectedCostFlowEdge(vertices[i], vertices[i + 1], 0, 0);
        }
        for (int i = 0; i < g.vertexCount; i++) {
            int e = g.edges[i].size();
            for (int j = e - 1; j > 0; j--) {
                for (int k = 1; k <= j; k++) {
                    if (g.to(g.edges[i].get(k - 1)) > g.to(g.edges[i].get(k))) {
                        int x = g.edges[i].get(k - 1);
                        int y = g.edges[i].get(k);
                        g.edges[i].set(k - 1, y);
                        g.edges[i].set(k, x);
                    }
                }
            }
            for (int j = 1; j < e; j++) {
                if (g.to(g.edges[i].get(j - 1)) > g.to(g.edges[i].get(j))) {
                    throw new RuntimeException("WHYYYYYYYYY");
                }
            }
//            System.out.print("Edges for " + i + ": ");
//            for (int j = 0; j < e; j++) {
//                System.out.print(g.to(g.edges[i].get(j)) + " ");
//            }
//            System.out.println();
        }

        if (!run(false, vertices[0], 0)) {
            out.println("No solution");
        } else {
            out.println(solution + " " + (vertices[0] + 1));
        }
    }

    public boolean run(boolean over, int u, int idx) {
        if (idx == vertices.length - 1) {
            return over;
        }
        if (!over && u < vertices[idx]) {
            return false;
        }

        over |= u > vertices[idx];
        for (int e: g.edges[u]) {
            if (!used[e]) {
                used[e] = used[g.reverse(e)] = true;
                if (run(over, g.to(e), idx + 1)) {
                    solution.push(u + 1);
                    return true;
                }
                used[e] = used[g.reverse(e)] = false;
            }
        }
        return false;
    }

}

class FlowGraph extends CostGraph {

    public IntArrayList flow;
    public IntArrayList reverse;

    public FlowGraph(int vertexCount) {
        this(vertexCount, 16);
    }

    public FlowGraph(int vertexCount, int edgeCount) {
        super(vertexCount, edgeCount);
        this.flow = new IntArrayList(edgeCount);
        this.reverse = new IntArrayList(edgeCount);
    }

    public void addUndirectedCostFlowEdge(int u, int v, int capacity, int edgeCost) {
        addCostFlowEdge(u, v, capacity, edgeCost, edgeCount + 1);
        addCostFlowEdge(v, u, capacity, -edgeCost, edgeCount - 1);
    }

    private void addCostFlowEdge(int u, int v, int capacity, int edgeCost, int reverseEdge) {
        super.addDirectedEdge(u, v, edgeCost);
        flow.add(capacity);
        reverse.add(reverseEdge);
    }

    public int reverse(int edge) {
        return reverse.get(edge);
    }
}

class IntDeque implements Iterable<Integer> {

    private int capacity;
    private int size = 0;
    private int front = 0;
    private int back = 0;
    private int[] deque;
    public IntDeque() {
        this(16);
    }
    public IntDeque(int capacity) {
        this.capacity = capacity;
        deque = new int[capacity];
    }

    public void addFirst(int x) {
        ensureCapacity();
        size++;
        if (front == 0) {
            front = capacity;
        }
        deque[--front] = x;
    }

    public void ensureCapacity() {
        if (size < capacity) {
            return;
        }
        int[] newDeque = new int[capacity << 1];
        for (int i = 0, j = front; i < size; i++, j++) {
            if (j == capacity) {
                j = 0;
            }
            newDeque[i] = deque[j];
        }
        deque = newDeque;
        capacity <<= 1;
        front = 0;
        back = size;
    }

    public Iterator<Integer> iterator() {
        return new Iterator<Integer>() {
            int done = 0;
            int curr = front;
            public boolean hasNext() {
                return done < size;
            }
            public Integer next() {
                Integer res = deque[curr++];
                if (curr == capacity) {
                    curr = 0;
                }
                done++;
                return res;
            }
            public void remove() {
                throw new UnsupportedOperationException();
            }
        };
    }

    public void push(int x) {
        addFirst(x);
    }

    public String toString() {
        if (size == 0) {
            return "";
        }
        StringBuilder res = new StringBuilder();
        for (int i: this) {
            res.append(i);
            res.append(" ");
        }
        res.setLength(res.length() - 1);
        return res.toString();
    }
}

class InputUtil {

    JoltyScanner in;

    public InputUtil(InputStream istream) {
        in = new JoltyScanner(istream);
    }

    public String next() {
        return in.nextOrNull();
    }

    public int nextInt() {
        String s = next();
        if (s == null) {
            throw new NoSuchElementException("Attempted to read integer that is not there.");
        }
        return Integer.parseInt(s);
    }

    public int[] nextIntArray (int size) {
        int[] arr = new int[size];
        for (int i = 0; i < size; i++) {
            arr[i] = in.nextInt();
        }
        return arr;
    }

}

class IntArrayUtil {

    public static void decrement(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            arr[i]--;
        }
    }

}

class IntArrayList implements Iterable<Integer> {
    int size = 0;
    int[] array;

    public IntArrayList() {
        this(16);
    }

    public IntArrayList(int length) {
        array = new int[length];
    }

    public void add(int element) {
        ensureCapacity();
        array[size] = element;
        size++;
    }

    private void checkIndex(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("" + index);
        }
    }

    public void ensureCapacity() {
        if (size == array.length) {
            int[] newArray = new int[size << 1];
            System.arraycopy(array, 0, newArray, 0, size);
            array = newArray;
        }
    }

    public int get(int index) {
        checkIndex(index);
        return array[index];
    }

    public Iterator<Integer> iterator() {
        return new Iterator<Integer>() {
            int index = 0;
            public boolean hasNext() {
                return index < size;
            }
            public Integer next() {
                return array[index++];
            }
            //FIXME - Never tested
            public void remove() {
                if (index == 0) {
                    throw new IndexOutOfBoundsException();
                }
                index--;
                System.arraycopy(array, index + 1, array, index, size - index);
                size--;
            }
        };
    }

    public void set(int index, int value) {
        checkIndex(index);
        array[index] = value;
    }
    public int size() {
        return size;
    }

    public String toString() {
        if (size == 0) {
            return "";
        }
        StringBuilder res = new StringBuilder();
        for (int i: this) {
            res.append(i);
            res.append(" ");
        }
        res.setLength(res.length() - 1);
        return res.toString();
    }

}

class SimpleGraph {

    public IntArrayList to;
    public IntArrayList edges[];
    public int vertexCount;
    public int edgeCount;

    public SimpleGraph(int vertexCount, int edgeCount) {
        this.to = new IntArrayList(edgeCount);
        this.edges = new IntArrayList[vertexCount];
        this.vertexCount = vertexCount;
        this.edgeCount = 0;
        for (int i = 0; i < vertexCount; i++) {
            edges[i] = new IntArrayList();
        }
    }

    public void addDirectedEdge(int u, int v) {
        to.add(v);
        edges[u].add(edgeCount);
        edgeCount++;
    }

    public int to(int edge) {
        return to.get(edge);
    }

}

class CostGraph extends SimpleGraph {

    public IntArrayList cost;

    public CostGraph(int vertexCount, int edgeCount) {
        super(vertexCount, edgeCount);
        this.cost = new IntArrayList(edgeCount);
    }

    public void addDirectedEdge(int u, int v, int edgeCost) {
        super.addDirectedEdge(u, v);
        cost.add(edgeCost);
    }

}

class JoltyScanner {
    public static final int BUFFER_SIZE = 1 << 16;
	public static final char NULL_CHAR = (char) -1;

    BufferedInputStream in;
	StringBuilder str = new StringBuilder();
	byte[] buffer = new byte[BUFFER_SIZE];
	boolean EOF_FLAG = false;

    char c = NULL_CHAR;
	int bufferIdx = 0;
    int size = 0;

	public JoltyScanner(InputStream in) {
		this.in = new BufferedInputStream(in, BUFFER_SIZE);
	}

	public int nextInt() {
		long x = nextLong();
		if (x > Integer.MAX_VALUE || x < Integer.MIN_VALUE) {
			throw new ArithmeticException("Scanned value overflows integer");
		}
		return (int) x;
	}

	public long nextLong() {
		boolean negative = false;
		if (c == NULL_CHAR) {
			c = nextChar();
		}
		for (; !EOF_FLAG && (c < '0' || c > '9'); c = nextChar()) {
			if (c == '-') {
				negative = true;
			}				
		}
		checkEOF();
		long res = 0;
		for (; c >= '0' && c <= '9'; c = nextChar()) {
			res = (res << 3) + (res << 1) + c - '0';
		}
		return negative ? -res : res;
	}

    public String next() {
		checkEOF();
		for (c = c == NULL_CHAR ? nextChar() : c; Character.isWhitespace(c); checkEOF()) {
			c = nextChar();
		}
		str.setLength(0);
		for (; !EOF_FLAG && !Character.isWhitespace(c); c = nextChar()) {
			str.append(c);
		}
		return str.toString();
	}

	public String nextOrNull() {
		try {
			return next();
		} catch (EndOfFileException e) {
			return null;
		}
	}

    public char nextChar() {
		if (EOF_FLAG) {
			return NULL_CHAR;
		}
		while (bufferIdx == size) {
			try {
				size = in.read(buffer);
				if (size == -1) {
					throw new Exception();
				}
			} catch (Exception e) {
				EOF_FLAG = true;
				return NULL_CHAR;
			}
			if (size == -1) {
				size = BUFFER_SIZE;
			}
			bufferIdx = 0;
		}
		return (char) buffer[bufferIdx++];
	}

    public void checkEOF() {
		if (EOF_FLAG) {
			throw new EndOfFileException();
		}
	}

	public class EndOfFileException extends RuntimeException {
	}
}

