Moriarty has trapped n people in n distinct rooms in a hotel. Some rooms are locked, others are unlocked. But, there is a condition that the people in the hotel can only escape when all the doors are unlocked at the same time. There are m switches. Each switch control doors of some rooms, but each door is controlled by exactly two switches.

You are given the initial configuration of the doors. Toggling any switch, that is, turning it ON when it is OFF, or turning it OFF when it is ON, toggles the condition of the doors that this switch controls. Say, we toggled switch 1, which was connected to room 1, 2 and 3 which were respectively locked, unlocked and unlocked. Then, after toggling the switch, they become unlocked, locked and locked.

You need to tell Sherlock, if there exists a way to unlock all doors at the same time.

Input

First line of input contains two integers n and m (2 ≤ n ≤ 105, 2 ≤ m ≤ 105) — the number of rooms and the number of switches.

Next line contains n space-separated integers r1, r2, ..., rn (0 ≤ ri ≤ 1) which tell the status of room doors. The i-th room is locked if ri = 0, otherwise it is unlocked.

The i-th of next m lines contains an integer xi (0 ≤ xi ≤ n) followed by xi distinct integers separated by space, denoting the number of rooms controlled by the i-th switch followed by the room numbers that this switch controls. It is guaranteed that the room numbers are in the range from 1 to n. It is guaranteed that each door is controlled by exactly two switches.

Output

Output "YES" without quotes, if it is possible to open all doors at the same time, otherwise output "NO" without quotes.

Examples

Input

3 3
1 0 1
2 1 3
2 1 2
2 2 3


Output

NO

Input

3 3
1 0 1
3 1 2 3
1 2
2 1 3


Output

YES

Input

3 3
1 0 1
3 1 2 3
2 1 2
1 3


Output

NO

Note

In the second example input, the initial statuses of the doors are [1, 0, 1] (0 means locked, 1 — unlocked).

After toggling switch 3, we get [0, 0, 0] that means all doors are locked.

Then, after toggling switch 1, we get [1, 1, 1] that means all doors are unlocked.

It can be seen that for the first and for the third example inputs it is not possible to make all doors unlocked.
// package codeforces.cf4xx.cf400;

import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.List;

public class D {
    public static void main(String[] args) {
        InputReader in = new InputReader(System.in);
        PrintWriter out = new PrintWriter(System.out);

        int n = in.nextInt();
        int m = in.nextInt();
        int[] doors = in.nextInts(n);

        int[] di = new int[n];
        int[][] pair = new int[n][2];
        for (int i = 0; i < m ; i++) {
            int nu = in.nextInt();
            for (int j = 0; j < nu; j++) {
                int idx = in.nextInt()-1;
                pair[idx][di[idx]++] = i;
            }
        }

        SAT2 sat2 = new SAT2(m);
        for (int i = 0; i < n ; i++) {
            if (doors[i] == 0) {
                sat2.add(pair[i][0], pair[i][1]);
                sat2.add(pair[i][0]+m, pair[i][1]+m);
            } else {
                sat2.add(pair[i][0]+m, pair[i][1]);
                sat2.add(pair[i][0], pair[i][1]+m);
            }
        }

        if (sat2.doit() == null) {
            out.println("NO");
        } else {
            out.println("YES");
        }
        out.flush();
    }

    public static class SAT2 {
        boolean[] visited;
        int[] nodeId;
        List<Integer> rev;

        int n;
        int vn;
        List<Integer>[] graph;
        List<Integer>[] revGraph;

        public SAT2(int maxN) {
            n = maxN;
            vn = n * 2;
            graph = new List[vn];
            revGraph = new List[vn];
            for (int i = 0; i < vn; i++) {
                graph[i] = new ArrayList<>();
                revGraph[i] = new ArrayList<>();
            }
        }

        public int not(int v) {
            return v >= n ? v - n : v + n;
        }

        public void add(int a, int b) {
            // a or b => [(not a) then b] and [(not b) then a]
            graph[not(a)].add(b);
            graph[not(b)].add(a);
            revGraph[b].add(not(a));
            revGraph[a].add(not(b));
        }

        public boolean[] doit() {
            visited = new boolean[vn];
            rev = new ArrayList<>();
            for (int i = 0; i< vn ; i++) {
                if (!visited[i]) {
                    dfs(i);
                }
            }
            int id = 0;
            nodeId = new int[vn];
            visited = new boolean[vn];
            for (int i = rev.size()-1; i>=0; i--) {
                if (!visited[rev.get(i)]) {
                    rdfs(rev.get(i), id);
                    id++;
                }
            }

            boolean[] ret = new boolean[n];
            for (int i = 0; i < n ; i++) {
                if (nodeId[i] == nodeId[i+n]) {
                    return null;
                }
                ret[i] = nodeId[i] > nodeId[i+n];
            }
            return ret;
        }

        private void dfs(int i) {
            visited[i] = true;
            for (int next : graph[i]) {
                if (!visited[next]) {
                    dfs(next);
                }
            }
            rev.add(i);
        }

        private void rdfs(int i, int id) {
            visited[i] = true;
            nodeId[i] = id;
            for (int next : revGraph[i]) {
                if (!visited[next]) {
                    rdfs(next, id);
                }
            }
        }
    }


    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        private int[] nextInts(int n) {
            int[] ret = new int[n];
            for (int i = 0; i < n; i++) {
                ret[i] = nextInt();
            }
            return ret;
        }

        private int[][] nextIntTable(int n, int m) {
            int[][] ret = new int[n][m];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    ret[i][j] = nextInt();
                }
            }
            return ret;
        }

        private long[] nextLongs(int n) {
            long[] ret = new long[n];
            for (int i = 0; i < n; i++) {
                ret[i] = nextLong();
            }
            return ret;
        }

        private long[][] nextLongTable(int n, int m) {
            long[][] ret = new long[n][m];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    ret[i][j] = nextLong();
                }
            }
            return ret;
        }

        private double[] nextDoubles(int n) {
            double[] ret = new double[n];
            for (int i = 0; i < n; i++) {
                ret[i] = nextDouble();
            }
            return ret;
        }

        private int next() {
            if (numChars == -1)
                throw new InputMismatchException();
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }

        public char nextChar() {
            int c = next();
            while (isSpaceChar(c))
                c = next();
            if ('a' <= c && c <= 'z') {
                return (char) c;
            }
            if ('A' <= c && c <= 'Z') {
                return (char) c;
            }
            throw new InputMismatchException();
        }

        public String nextToken() {
            int c = next();
            while (isSpaceChar(c))
                c = next();
            StringBuilder res = new StringBuilder();
            do {
                res.append((char) c);
                c = next();
            } while (!isSpaceChar(c));
            return res.toString();
        }

        public int nextInt() {
            int c = next();
            while (isSpaceChar(c))
                c = next();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = next();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c-'0';
                c = next();
            } while (!isSpaceChar(c));
            return res*sgn;
        }

        public long nextLong() {
            int c = next();
            while (isSpaceChar(c))
                c = next();
            long sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = next();
            }
            long res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c-'0';
                c = next();
            } while (!isSpaceChar(c));
            return res*sgn;
        }

        public double nextDouble() {
            return Double.valueOf(nextToken());
        }

        public boolean isSpaceChar(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);
        }
    }

    static void debug(Object... o) {
        System.err.println(Arrays.deepToString(o));
    }
}
