Problem: In Byteland, there are two political parties fighting for seats in the Parliament in the upcoming elections: Wrong Answer Party and Time Limit Exceeded Party. As they want to convince as many citizens as possible to cast their votes on them, they keep promising lower and lower taxes.

There are n cities in Byteland, connected by m one-way roads. Interestingly enough, the road network has no cycles — it's impossible to start in any city, follow a number of roads, and return to that city. Last year, citizens of the i-th city had to pay h_i bourles of tax.

Parties will now alternately hold the election conventions in various cities. If a party holds a convention in city v, the party needs to decrease the taxes in this city to a non-negative integer amount of bourles. However, at the same time they can arbitrarily modify the taxes in each of the cities that can be reached from v using a single road. The only condition that must be fulfilled that the tax in each city has to remain a non-negative integer amount of bourles.

The first party to hold the convention is Wrong Answer Party. It's predicted that the party to hold the last convention will win the election. Can Wrong Answer Party win regardless of Time Limit Exceeded Party's moves?

Input

The first line of the input contains two integers n, m (1 ≤ n ≤ 200 000, 0 ≤ m ≤ 200 000) — the number of cities and roads in Byteland.

The next line contains n space-separated integers h_1, h_2, ..., h_n (0 ≤ h_i ≤ 10^9); h_i denotes the amount of taxes paid in the i-th city.

Each of the following m lines contains two integers (1 ≤ u, v ≤ n, u ≠ v), and describes a one-way road leading from the city u to the city v. There will be no cycles in the road network. No two roads will connect the same pair of cities.

We can show that the conventions cannot be held indefinitely for any correct test case.

Output

If Wrong Answer Party can win the election, output WIN in the first line of your output. In this case, you're additionally asked to produce any convention allowing the party to win regardless of the opponent's actions. The second line should contain n non-negative integers h'_1, h'_2, ..., h'_n (0 ≤ h'_i ≤ 2 ⋅ 10^{18}) describing the amount of taxes paid in consecutive cities after the convention. If there are multiple answers, output any. We guarantee that if the party has any winning move, there exists a move after which no city has to pay more than 2 ⋅ 10^{18} bourles.

If the party cannot assure their victory, output LOSE in the first and only line of the output.

Examples

Input


4 2
2 1 1 5
1 2
3 4


Output


WIN
1 5 1 5 


Input


4 2
1 5 1 5
1 2
3 4


Output


LOSE


Input


3 3
314 159 265
1 2
1 3
3 2


Output


WIN
0 0 0 


Input


6 4
2 2 5 5 6 6
1 3
2 4
3 5
4 6


Output


LOSE

Note

In the first example, Wrong Answer Party should hold the convention in the city 1. The party will decrease the taxes in this city to 1 bourle. As the city 2 is directly reachable from 1, we can arbitrarily modify the taxes in this city. The party should change the tax to 5 bourles. It can be easily proved that Time Limit Exceeded cannot win the election after this move if Wrong Answer Party plays optimally.

The second example test presents the situation we created after a single move in the previous test; as it's Wrong Answer Party's move now, the party cannot win.

In the third test, we should hold the convention in the first city. This allows us to change the taxes in any city to any desired value; we can for instance decide to set all the taxes to zero, which allows the Wrong Answer Party to win the election immediately.

Solution (in JAVA):

Solution:


import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.nio.charset.Charset;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class CF1149E {
    public static void main(String[] args) throws Exception {
        boolean local = System.getProperty("ONLINE_JUDGE") == null;
        boolean async = false;

        Charset charset = Charset.forName("ascii");

        FastIO io = local ? new FastIO(new FileInputStream("D:\\DATABASE\\TESTCASE\\Code.in"), System.out, charset) : new FastIO(System.in, System.out, charset);
        Task task = new Task(io, new Debug(local));

        if (async) {
            Thread t = new Thread(null, task, "dalt", 1 << 27);
            t.setPriority(Thread.MAX_PRIORITY);
            t.start();
            t.join();
        } else {
            task.run();
        }

        if (local) {
            io.cache.append("\n\n--memory -- \n" + ((Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory()) >> 20) + "M");
        }

        io.flush();
    }

    public static class Task implements Runnable {
        final FastIO io;
        final Debug debug;
        int inf = (int) 1e8;
        int mod = (int) 1e9 + 7;

        public int mod(int val) {
            val %= mod;
            if (val < 0) {
                val += mod;
            }
            return val;
        }

        public int mod(long val) {
            val %= mod;
            if (val < 0) {
                val += mod;
            }
            return (int) val;
        }

        public Task(FastIO io, Debug debug) {
            this.io = io;
            this.debug = debug;
        }

        @Override
        public void run() {
            solve();
        }

        public void solve() {
            int n = io.readInt();
            int m = io.readInt();
            Node[] nodes = new Node[n + 1];

            for (int i = 1; i <= n; i++) {
                nodes[i] = new Node();
            }

            for (int i = 1; i <= n; i++) {
                nodes[i].tax = io.readInt();
            }
            for (int i = 0; i < m; i++) {
                nodes[io.readInt()].next.add(nodes[io.readInt()]);
            }

            for (int i = 1; i <= n; i++) {
                dfs(nodes[i]);
            }

            int[] xor = new int[n];
            for (int i = 1; i <= n; i++) {
                xor[nodes[i].mex] ^= nodes[i].tax;
            }

            boolean allZero = true;
            int mex = n - 1;
            for (int i = 0; i < n; i++) {
                allZero = allZero && xor[i] == 0;
                if (xor[i] != 0) {
                    mex = i;
                }
            }

            if (allZero) {
                io.cache.append("LOSE");
                return;
            }


            Node heldOn = null;
            for (int i = 1; i <= n; i++) {
                if (nodes[i].mex == mex && (nodes[i].tax ^ xor[mex]) < nodes[i].tax) {
                    heldOn = nodes[i];
                    break;
                }
            }

            heldOn.tax = heldOn.tax ^ xor[mex];
            xor[mex] = 0;
            for (Node node : heldOn.next) {
                if (xor[node.mex] == 0) {
                    continue;
                }
                node.tax ^= xor[node.mex];
                xor[node.mex] = 0;
            }

            io.cache.append("WIN\n");
            for (int i = 1; i <= n; i++) {
                io.cache.append(nodes[i].tax).append(' ');
            }
        }

        public void dfs(Node root) {
            if (root.visited) {
                return;
            }
            root.visited = true;
            for (Node node : root.next) {
                dfs(node);
            }
            root.next.sort((a, b) -> a.mex - b.mex);
            root.mex = 0;
            for (Node node : root.next) {
                if (node.mex > root.mex) {
                    break;
                }
                if (node.mex == root.mex) {
                    root.mex++;
                }
            }
        }

    }

    public static class FastIO {
        public final StringBuilder cache = new StringBuilder();
        private final InputStream is;
        private final OutputStream os;
        private final Charset charset;
        private StringBuilder defaultStringBuf = new StringBuilder(1 << 8);
        private byte[] buf = new byte[1 << 13];
        private int bufLen;
        private int bufOffset;
        private int next;

        public FastIO(InputStream is, OutputStream os, Charset charset) {
            this.is = is;
            this.os = os;
            this.charset = charset;
        }

        public FastIO(InputStream is, OutputStream os) {
            this(is, os, Charset.forName("ascii"));
        }

        private int read() {
            while (bufLen == bufOffset) {
                bufOffset = 0;
                try {
                    bufLen = is.read(buf);
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
                if (bufLen == -1) {
                    return -1;
                }
            }
            return buf[bufOffset++];
        }

        public void skipBlank() {
            while (next >= 0 && next <= 32) {
                next = read();
            }
        }

        public int readInt() {
            int sign = 1;

            skipBlank();
            if (next == '+' || next == '-') {
                sign = next == '+' ? 1 : -1;
                next = read();
            }

            int val = 0;
            if (sign == 1) {
                while (next >= '0' && next <= '9') {
                    val = val * 10 + next - '0';
                    next = read();
                }
            } else {
                while (next >= '0' && next <= '9') {
                    val = val * 10 - next + '0';
                    next = read();
                }
            }

            return val;
        }

        public long readLong() {
            int sign = 1;

            skipBlank();
            if (next == '+' || next == '-') {
                sign = next == '+' ? 1 : -1;
                next = read();
            }

            long val = 0;
            if (sign == 1) {
                while (next >= '0' && next <= '9') {
                    val = val * 10 + next - '0';
                    next = read();
                }
            } else {
                while (next >= '0' && next <= '9') {
                    val = val * 10 - next + '0';
                    next = read();
                }
            }

            return val;
        }

        public double readDouble() {
            boolean sign = true;
            skipBlank();
            if (next == '+' || next == '-') {
                sign = next == '+';
                next = read();
            }

            long val = 0;
            while (next >= '0' && next <= '9') {
                val = val * 10 + next - '0';
                next = read();
            }
            if (next != '.') {
                return sign ? val : -val;
            }
            next = read();
            long radix = 1;
            long point = 0;
            while (next >= '0' && next <= '9') {
                point = point * 10 + next - '0';
                radix = radix * 10;
                next = read();
            }
            double result = val + (double) point / radix;
            return sign ? result : -result;
        }

        public String readString(StringBuilder builder) {
            skipBlank();

            while (next > 32) {
                builder.append((char) next);
                next = read();
            }

            return builder.toString();
        }

        public String readString() {
            defaultStringBuf.setLength(0);
            return readString(defaultStringBuf);
        }

        public int readLine(char[] data, int offset) {
            int originalOffset = offset;
            while (next != -1 && next != '\n') {
                data[offset++] = (char) next;
                next = read();
            }
            return offset - originalOffset;
        }

        public int readString(char[] data, int offset) {
            skipBlank();

            int originalOffset = offset;
            while (next > 32) {
                data[offset++] = (char) next;
                next = read();
            }

            return offset - originalOffset;
        }

        public int readString(byte[] data, int offset) {
            skipBlank();

            int originalOffset = offset;
            while (next > 32) {
                data[offset++] = (byte) next;
                next = read();
            }

            return offset - originalOffset;
        }

        public char readChar() {
            skipBlank();
            char c = (char) next;
            next = read();
            return c;
        }

        public void flush() {
            try {
                os.write(cache.toString().getBytes(charset));
                os.flush();
                cache.setLength(0);
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }

        public boolean hasMore() {
            skipBlank();
            return next != -1;
        }
    }

    public static class Debug {
        private boolean allowDebug;

        public Debug(boolean allowDebug) {
            this.allowDebug = allowDebug;
        }

        public void assertTrue(boolean flag) {
            if (!allowDebug) {
                return;
            }
            if (!flag) {
                fail();
            }
        }

        public void fail() {
            throw new RuntimeException();
        }

        public void assertFalse(boolean flag) {
            if (!allowDebug) {
                return;
            }
            if (flag) {
                fail();
            }
        }

        private void outputName(String name) {
            System.out.print(name + " = ");
        }

        public void debug(String name, int x) {
            if (!allowDebug) {
                return;
            }

            outputName(name);
            System.out.println("" + x);
        }

        public void debug(String name, long x) {
            if (!allowDebug) {
                return;
            }
            outputName(name);
            System.out.println("" + x);
        }

        public void debug(String name, double x) {
            if (!allowDebug) {
                return;
            }
            outputName(name);
            System.out.println("" + x);
        }

        public void debug(String name, int[] x) {
            if (!allowDebug) {
                return;
            }
            outputName(name);
            System.out.println(Arrays.toString(x));
        }

        public void debug(String name, long[] x) {
            if (!allowDebug) {
                return;
            }
            outputName(name);
            System.out.println(Arrays.toString(x));
        }

        public void debug(String name, double[] x) {
            if (!allowDebug) {
                return;
            }
            outputName(name);
            System.out.println(Arrays.toString(x));
        }

        public void debug(String name, Object x) {
            if (!allowDebug) {
                return;
            }
            outputName(name);
            System.out.println("" + x);
        }

        public void debug(String name, Object... x) {
            if (!allowDebug) {
                return;
            }
            outputName(name);
            System.out.println(Arrays.deepToString(x));
        }
    }

    public static class Node {
        boolean visited;
        int mex;
        int tax;
        List<Node> next = new ArrayList<>();
    }
}