Problem: 'In Boolean logic, a formula is in conjunctive normal form (CNF) or clausal normal form if it is a conjunction of clauses, where a clause is a disjunction of literals' (cited from https://en.wikipedia.org/wiki/Conjunctive_normal_form)

In the other words, CNF is a formula of type <image>, where & represents a logical "AND" (conjunction), <image> represents a logical "OR" (disjunction), and vij are some boolean variables or their negations. Each statement in brackets is called a clause, and vij are called literals.

You are given a CNF containing variables x1, ..., xm and their negations. We know that each variable occurs in at most two clauses (with negation and without negation in total). Your task is to determine whether this CNF is satisfiable, that is, whether there are such values of variables where the CNF value is true. If CNF is satisfiable, then you also need to determine the values of the variables at which the CNF is true. 

It is guaranteed that each variable occurs at most once in each clause.

Input

The first line contains integers n and m (1 ≤ n, m ≤ 2·105) — the number of clauses and the number variables, correspondingly.

Next n lines contain the descriptions of each clause. The i-th line first contains first number ki (ki ≥ 1) — the number of literals in the i-th clauses. Then follow space-separated literals vij (1 ≤ |vij| ≤ m). A literal that corresponds to vij is x|vij| either with negation, if vij is negative, or without negation otherwise.

Output

If CNF is not satisfiable, print a single line "NO" (without the quotes), otherwise print two strings: string "YES" (without the quotes), and then a string of m numbers zero or one — the values of variables in satisfying assignment in the order from x1 to xm.

Examples

Input

2 2
2 1 -2
2 2 -1


Output

YES
11


Input

4 3
1 1
1 2
3 -1 -2 3
1 -3


Output

NO


Input

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


Output

YES
100010

Note

In the first sample test formula is <image>. One of possible answer is x1 = TRUE, x2 = TRUE.

Solution (in JAVA):

Solution:
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.util.Arrays;
import java.util.HashMap;
import java.io.IOException;
import java.util.ArrayList;
import java.io.UncheckedIOException;
import java.util.List;
import java.util.Map;
import java.io.Closeable;
import java.util.Map.Entry;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) throws Exception {
        Thread thread = new Thread(null, new TaskAdapter(), "", 1 << 29);
        thread.start();
        thread.join();
    }

    static class TaskAdapter implements Runnable {
        @Override
        public void run() {
            InputStream inputStream = System.in;
            OutputStream outputStream = System.out;
            FastInput in = new FastInput(inputStream);
            FastOutput out = new FastOutput(outputStream);
            CCNF2 solver = new CCNF2();
            solver.solve(1, in, out);
            out.close();
        }
    }

    static class CCNF2 {
        public void dfsForSuccess(Node root) {
            assert root.ok;
            for (Edge e : root.adj) {
                dfs(e.other(root), e);
            }
        }

        public void dfs(Node root, Edge p) {
            if (root.ok) {
                return;
            }
            root.ok = true;
            p.prefer = root;
            for (Edge e : root.adj) {
                dfs(e.other(root), e);
            }
        }

        public void solve(int testNumber, FastInput in, FastOutput out) {
            int n = in.ri();
            int m = in.ri();
            DSUExt dsu = new DSUExt(n);
            dsu.init();
            int[] value = new int[m + 1];
            for (int i = 1; i <= m; i++) {
                value[i] = i;
            }
            Map<Integer, Integer> map = new HashMap<>(m);
            Node[] nodes = new Node[n];
            for (int i = 0; i < n; i++) {
                nodes[i] = new Node();
            }
            List<Edge> edges = new ArrayList<>(n);
            for (int i = 0; i < n; i++) {
                int k = in.ri();
                for (int j = 0; j < k; j++) {
                    int var = in.ri();
                    if (map.containsKey(var)) {
                        //cool
                        int other = map.remove(var);
                        nodes[other].ok = true;
                        nodes[i].ok = true;
                        dsu.containCircle[dsu.find(other)] = true;
                        dsu.containCircle[dsu.find(i)] = true;
                        value[Math.abs(var)] = var;
                    } else if (map.containsKey(-var)) {
                        //cool again
                        int other = map.remove(-var);
                        if (dsu.find(other) == dsu.find(i)) {
                            nodes[other].ok = true;
                            dsu.containCircle[dsu.find(other)] = true;
                            value[Math.abs(var)] = -var;
                        } else {
                            dsu.merge(other, i);
                            Edge edge = new Edge();
                            edge.a = var > 0 ? nodes[i] : nodes[other];
                            edge.b = var > 0 ? nodes[other] : nodes[i];
                            edge.prefer = edge.a;
                            edge.index = Math.abs(var);
                            nodes[i].adj.add(edge);
                            nodes[other].adj.add(edge);
                            edges.add(edge);
                        }
                    } else {
                        map.put(var, i);
                    }
                }
            }
            for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
                int k = entry.getKey();
                int v = entry.getValue();
                nodes[v].ok = true;
                value[Math.abs(k)] = k;
                dsu.containCircle[dsu.find(v)] = true;
            }

            for (int i = 0; i < n; i++) {
                if (dsu.find(i) == i && !dsu.containCircle[i]) {
                    out.println("NO");
                    return;
                }
            }

            for (Node node : nodes) {
                if (node.ok) {
                    dfsForSuccess(node);
                }
            }

            for (Edge e : edges) {
                value[e.index] = e.prefer == e.a ? e.index : -e.index;
            }
            out.println("YES");
            for (int i = 1; i <= m; i++) {
                out.append(value[i] == i ? 1 : 0);
            }
        }

    }

    static class FastOutput implements AutoCloseable, Closeable, Appendable {
        private static final int THRESHOLD = 1 << 13;
        private final Writer os;
        private StringBuilder cache = new StringBuilder(THRESHOLD * 2);

        public FastOutput append(CharSequence csq) {
            cache.append(csq);
            return this;
        }

        public FastOutput append(CharSequence csq, int start, int end) {
            cache.append(csq, start, end);
            return this;
        }

        private void afterWrite() {
            if (cache.length() < THRESHOLD) {
                return;
            }
            flush();
        }

        public FastOutput(Writer os) {
            this.os = os;
        }

        public FastOutput(OutputStream os) {
            this(new OutputStreamWriter(os));
        }

        public FastOutput append(char c) {
            cache.append(c);
            afterWrite();
            return this;
        }

        public FastOutput append(int c) {
            cache.append(c);
            afterWrite();
            return this;
        }

        public FastOutput append(String c) {
            cache.append(c);
            afterWrite();
            return this;
        }

        public FastOutput println(String c) {
            return append(c).println();
        }

        public FastOutput println() {
            return append(System.lineSeparator());
        }

        public FastOutput flush() {
            try {
                os.append(cache);
                os.flush();
                cache.setLength(0);
            } catch (IOException e) {
                throw new UncheckedIOException(e);
            }
            return this;
        }

        public void close() {
            flush();
            try {
                os.close();
            } catch (IOException e) {
                throw new UncheckedIOException(e);
            }
        }

        public String toString() {
            return cache.toString();
        }

    }

    static class DSU {
        protected int[] p;
        protected int[] rank;
        protected int n;

        public DSU(int n) {
            p = new int[n];
            rank = new int[n];
        }

        public void init() {
            init(p.length);
        }

        public void init(int n) {
            this.n = n;
            for (int i = 0; i < n; i++) {
                p[i] = i;
                rank[i] = 0;
            }
        }

        public final int find(int a) {
            if (p[a] == p[p[a]]) {
                return p[a];
            }
            find(p[a]);
            preAccess(a);
            return p[a] = p[p[a]];
        }

        protected void preAccess(int a) {

        }

        protected void preMerge(int a, int b) {

        }

        public final void merge(int a, int b) {
            a = find(a);
            b = find(b);
            if (a == b) {
                return;
            }
            if (rank[a] == rank[b]) {
                rank[a]++;
            }

            if (rank[a] < rank[b]) {
                int tmp = a;
                a = b;
                b = tmp;
            }

            preMerge(a, b);
            p[b] = a;
        }

        public String toString() {
            return Arrays.toString(Arrays.copyOf(p, n));
        }

    }

    static class DSUExt extends DSU {
        boolean[] containCircle;

        public DSUExt(int n) {
            super(n);
            containCircle = new boolean[n];
        }

        protected void preMerge(int a, int b) {
            super.preMerge(a, b);
            containCircle[a] = containCircle[a] || containCircle[b];
        }

    }

    static class FastInput {
        private final InputStream is;
        private byte[] buf = new byte[1 << 13];
        private int bufLen;
        private int bufOffset;
        private int next;

        public FastInput(InputStream is) {
            this.is = is;
        }

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

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

        public int ri() {
            return readInt();
        }

        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;
        }

    }

    static class Node {
        List<Edge> adj = new ArrayList<>();
        boolean ok;

    }

    static class Edge {
        int index;
        Node a;
        Node b;
        Node prefer;

        Node other(Node x) {
            return a == x ? b : a;
        }

    }
}