You are given n sequences. Each sequence consists of positive integers, not exceeding m. All integers in one sequence are distinct, but the same integer may appear in multiple sequences. The length of the i-th sequence is ki.

Each second integers in each of the sequences are shifted by one to the left, i.e. integers at positions i > 1 go to positions i - 1, while the first integers becomes the last.

Each second we take the first integer of each sequence and write it down to a new array. Then, for each value x from 1 to m we compute the longest segment of the array consisting of element x only.

The above operation is performed for 10100 seconds. For each integer from 1 to m find out the longest segment found at this time.

Input

The first line of the input contains two integers n and m (1 ≤ n, m ≤ 100 000) — the number of sequences and the maximum integer that can appear in the sequences. 

Then follow n lines providing the sequences. Each of them starts with an integer ki (1 ≤ ki ≤ 40) — the number of integers in the sequence, proceeded by ki positive integers — elements of the sequence. It's guaranteed that all integers in each sequence are pairwise distinct and do not exceed m.

The total length of all sequences doesn't exceed 200 000.

Output

Print m integers, the i-th of them should be equal to the length of the longest segment of the array with all its values equal to i during the first 10100 seconds.

Examples

Input

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


Output

2
1
3
2


Input

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


Output

3
1
4
0
1


Input

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


Output

0
0
2
1
1
2
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.util.Arrays;
import java.util.Iterator;
import java.io.IOException;
import java.io.UncheckedIOException;
import java.io.Closeable;
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);
            FCyclicCipher solver = new FCyclicCipher();
            solver.solve(1, in, out);
            out.close();
        }
    }

    static class FCyclicCipher {
        public void solve(int testNumber, FastInput in, FastOutput out) {
            int n = in.ri();
            int m = in.ri();
            MultiWayStack<int[]> stack = new MultiWayStack<>(m, (int) 2e5);
            int[] len = new int[n];
            for (int i = 0; i < n; i++) {
                int k = in.ri();
                len[i] = k;
                for (int j = 0; j < k; j++) {
                    int x = in.ri() - 1;
                    stack.addLast(x, new int[]{i, j});
                }
            }
            Sum sum = new Sum();
            Segment seg = new Segment(0, n - 1);
            for (int i = 0; i < m; i++) {
                long max = 0;
                for (int[] pos : stack.getStack(i)) {
                    seg.update(pos[0], pos[0], 0, n - 1, len[pos[0]], pos[1]);
                }
                for (int[] pos : stack.getStack(i)) {
                    sum.clear();
                    seg.query(pos[0], n - 1, 0, n - 1, sum);
                    max = Math.max(max, sum.len);
                }
                for (int[] pos : stack.getStack(i)) {
                    seg.update(pos[0], pos[0], 0, n - 1, 0, 0);
                }
                out.println(max);
            }
        }

    }

    static class LongModularDanger implements ILongModular {
        final long m;

        public long getMod() {
            return m;
        }

        public LongModularDanger(long m) {
            this.m = m;
        }

        public long mul(long a, long b) {
            return DigitUtils.modmul(a, b, m);
        }

    }

    static class Segment implements Cloneable {
        private Segment left;
        private Segment right;
        static ExtCRT crt = new ExtCRT();
        long m;
        long r;
        boolean valid;

        private void modify(int m, int r) {
            this.m = m;
            this.r = r;
            this.valid = m > 0;
        }

        public void pushUp() {
            valid = left.valid && right.valid;
            if (valid) {
                crt.set(left.r, left.m);
                valid = crt.add(right.r, right.m);
                m = crt.m;
                r = crt.r;
            }
        }

        public void pushDown() {
        }

        public Segment(int l, int r) {
            if (l < r) {
                int m = DigitUtils.floorAverage(l, r);
                left = new Segment(l, m);
                right = new Segment(m + 1, r);
                pushUp();
            } else {
                valid = false;
            }
        }

        private boolean enter(int L, int R, int l, int r) {
            return L <= l && R >= r;
        }

        private boolean leave(int L, int R, int l, int r) {
            return L > r || R < l;
        }

        public void update(int L, int R, int l, int r, int mod, int rm) {
            if (leave(L, R, l, r)) {
                return;
            }
            if (enter(L, R, l, r)) {
                modify(mod, rm);
                return;
            }
            pushDown();
            int m = DigitUtils.floorAverage(l, r);
            left.update(L, R, l, m, mod, rm);
            right.update(L, R, m + 1, r, mod, rm);
            pushUp();
        }

        public boolean query(int L, int R, int l, int r, Sum sum) {
            if (leave(L, R, l, r)) {
                return true;
            }
            if (enter(L, R, l, r) && valid) {
                if (sum.add(this.r, this.m, r - l + 1)) {
                    return true;
                }
            }
            if (l == r) {
                return false;
            }
            pushDown();
            int m = DigitUtils.floorAverage(l, r);
            boolean ans = left.query(L, R, l, m, sum);
            ans = ans && right.query(L, R, m + 1, r, sum);
            return ans;
        }

        private Segment deepClone() {
            Segment seg = clone();
            if (seg.left != null) {
                seg.left = seg.left.deepClone();
            }
            if (seg.right != null) {
                seg.right = seg.right.deepClone();
            }
            return seg;
        }

        protected Segment clone() {
            try {
                return (Segment) super.clone();
            } catch (CloneNotSupportedException e) {
                throw new RuntimeException(e);
            }
        }

        private void toString(StringBuilder builder) {
            if (left == null && right == null) {
                builder.append("val").append(",");
                return;
            }
            pushDown();
            left.toString(builder);
            right.toString(builder);
        }

        public String toString() {
            StringBuilder builder = new StringBuilder();
            deepClone().toString(builder);
            if (builder.length() > 0) {
                builder.setLength(builder.length() - 1);
            }
            return builder.toString();
        }

    }

    static class Sum {
        ExtCRT crt = new ExtCRT();
        int len;

        public void clear() {
            crt.clear();
            len = 0;
        }

        public boolean add(long rm, long mod, int len) {
            if (crt.add(rm, mod)) {
                this.len += len;
                return true;
            }
            return false;
        }

    }

    static class LongModular2305843009213693951 implements ILongModular {
        private static long mod = 2305843009213693951L;
        private static final LongModular2305843009213693951 INSTANCE = new LongModular2305843009213693951();
        private static long mask = (1L << 32) - 1;

        private LongModular2305843009213693951() {
        }

        public static final LongModular2305843009213693951 getInstance() {
            return INSTANCE;
        }

        public long getMod() {
            return mod;
        }

        public long mul(long a, long b) {
            long l1 = a & mask;
            long h1 = (a >> 32) & mask;
            long l2 = b & mask;
            long h2 = (b >> 32) & mask;
            long l = l1 * l2;
            long m = l1 * h2 + l2 * h1;
            long h = h1 * h2;
            long ret = (l & mod) + (l >>> 61) + (h << 3) + (m >>> 29) + ((m << 35) >>> 3) + 1;
            ret = (ret & mod) + (ret >>> 61);
            ret = (ret & mod) + (ret >>> 61);
            return ret - 1;
        }

    }

    static class LongExtGCDObject {
        private long[] xy = new long[2];

        public long extgcd(long a, long b) {
            return ExtGCD.extGCD(a, b, xy);
        }

        public long getX() {
            return xy[0];
        }

    }

    static interface SimplifiedStack<T> extends Iterable<T> {
    }

    static class SequenceUtils {
        public static void swap(long[] data, int i, int j) {
            long tmp = data[i];
            data[i] = data[j];
            data[j] = tmp;
        }

    }

    static interface RevokeIterator<E> extends Iterator<E> {
    }

    static class ExtGCD {
        public static long extGCD(long a, long b, long[] xy) {
            if (a >= b) {
                return extGCD0(a, b, xy);
            }
            long ans = extGCD0(b, a, xy);
            SequenceUtils.swap(xy, 0, 1);
            return ans;
        }

        private static long extGCD0(long a, long b, long[] xy) {
            if (b == 0) {
                xy[0] = 1;
                xy[1] = 0;
                return a;
            }
            long ans = extGCD0(b, a % b, xy);
            long x = xy[0];
            long y = xy[1];
            xy[0] = y;
            xy[1] = x - a / b * y;
            return ans;
        }

    }

    static class LongModular implements ILongModular {
        final long m;

        public long getMod() {
            return m;
        }

        public LongModular(long m) {
            this.m = m;
        }

        public long mul(long a, long b) {
            if (b == 0) {
                return 0;
            }
            long ans = mul(a, b >> 1) << 1;
            if (ans >= m) {
                ans -= m;
            }
            ans += a * (b & 1);
            if (ans >= m) {
                ans -= m;
            }
            return ans;
        }

    }

    static class MultiWayStack<T> {
        private Object[] values;
        private int[] next;
        private int[] heads;
        private int alloc;
        private int stackNum;

        public RevokeIterator<T> iterator(final int queue) {
            return new RevokeIterator<T>() {
                int ele = heads[queue];
                int pre = 0;


                public boolean hasNext() {
                    return ele != 0;
                }


                public T next() {
                    T ans = (T) values[ele];
                    pre = ele;
                    ele = next[ele];
                    return ans;
                }


                public void revoke() {
                    ele = pre;
                    pre = 0;
                }
            };
        }

        public SimplifiedStack<T> getStack(int qId) {
            return new SimplifiedStack<T>() {

                public boolean isEmpty() {
                    return MultiWayStack.this.isEmpty(qId);
                }


                public T peekLast() {
                    return MultiWayStack.this.peekLast(qId);
                }


                public void addLast(T x) {
                    MultiWayStack.this.addLast(qId, x);
                }


                public T removeLast() {
                    return MultiWayStack.this.removeLast(qId);
                }


                public Iterator<T> iterator() {
                    return MultiWayStack.this.iterator(qId);
                }
            };
        }

        private void doubleCapacity() {
            int newSize = Math.max(next.length + 10, next.length * 2);
            next = Arrays.copyOf(next, newSize);
            values = Arrays.copyOf(values, newSize);
        }

        public void alloc() {
            alloc++;
            if (alloc >= next.length) {
                doubleCapacity();
            }
            next[alloc] = 0;
        }

        public boolean isEmpty(int qId) {
            return heads[qId] == 0;
        }

        public MultiWayStack(int qNum, int totalCapacity) {
            values = new Object[totalCapacity + 1];
            next = new int[totalCapacity + 1];
            heads = new int[qNum];
            stackNum = qNum;
        }

        public void addLast(int qId, T x) {
            alloc();
            values[alloc] = x;
            next[alloc] = heads[qId];
            heads[qId] = alloc;
        }

        public T peekLast(int qId) {
            return (T) values[heads[qId]];
        }

        public T removeLast(int qId) {
            T ans = (T) values[heads[qId]];
            heads[qId] = next[heads[qId]];
            return ans;
        }

        public String toString() {
            StringBuilder builder = new StringBuilder();
            for (int i = 0; i < stackNum; i++) {
                builder.append(i).append(": ");
                for (Iterator iterator = iterator(i); iterator.hasNext(); ) {
                    builder.append(iterator.next()).append(",");
                }
                if (builder.charAt(builder.length() - 1) == ',') {
                    builder.setLength(builder.length() - 1);
                }
                builder.append('\n');
            }
            return builder.toString();
        }

    }

    static class ExtCRT {
        public long r;
        public long m;
        static final LongExtGCDObject gcd = new LongExtGCDObject();

        public ExtCRT() {
            r = 0;
            m = 1;
        }

        public void set(long r, long m) {
            this.r = r;
            this.m = m;
        }

        public void clear() {
            set(0, 1);
        }

        public boolean add(long r, long m) {
            long m1 = this.m;
            long x1 = this.r;
            long m2 = m;
            long x2 = ((r % m) + m) % m;
            long g = gcd.extgcd(m1, m2);
            long a = gcd.getX();
            if ((x2 - x1) % g != 0) {
                return false;
            }
            this.m = m1 / g * m2;
            ILongModular modular = ILongModular.getInstance(this.m);
            this.r = modular.plus(modular.mul(modular.mul(modular.valueOf(a), modular.valueOf((x2 - x1) / g)), m1), x1);
//        this.r = BigInteger.valueOf(a).multiply(BigInteger.valueOf((x2 - x1) / g)).multiply(BigInteger.valueOf(m1))
//                .add(BigInteger.valueOf(x1)).mod(BigInteger.valueOf(this.m)).longValue();
            return true;
        }

        public String toString() {
            return String.format("%d mod %d", r, m);
        }

    }

    static interface ILongModular {
        long getMod();

        default long plus(long a, long b) {
            return DigitUtils.modplus(a, b, getMod());
        }

        default long valueOf(long x) {
            return DigitUtils.mod(x, getMod());
        }

        long mul(long a, long b);

        static ILongModular getInstance(long mod) {
            if (mod <= Integer.MAX_VALUE) {
                return new SmallLongModular(mod);
            }
            if (mod <= (1L << 50)) {
                return new LongModularDanger(mod);
            }
            if (mod == (1L << 61) - 1) {
                return LongModular2305843009213693951.getInstance();
            }
            return new LongModular(mod);//new BigLongModular(mod);//new LongModular(mod);
        }

    }

    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 SmallLongModular implements ILongModular {
        long mod;

        public SmallLongModular(long mod) {
            this.mod = mod;
        }

        public long getMod() {
            return mod;
        }

        public long mul(long a, long b) {
            return a * b % mod;
        }

    }

    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(long c) {
            cache.append(c);
            afterWrite();
            return this;
        }

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

        public FastOutput println(long 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 DigitUtils {
        private DigitUtils() {
        }

        public static long round(double x) {
            if (x >= 0) {
                return (long) (x + 0.5);
            } else {
                return (long) (x - 0.5);
            }
        }

        public static long modplus(long a, long b, long mod) {
            long ans = a + b;
            if (ans >= mod) {
                ans -= mod;
            }
            return ans;
        }

        public static long mod(long x, long mod) {
            if (x < -mod || x >= mod) {
                x %= mod;
            }
            if (x < 0) {
                x += mod;
            }
            return x;
        }

        public static long modmul(long a, long b, long mod) {
            long k = DigitUtils.round((double) a / mod * b);
            return DigitUtils.mod(a * b - k * mod, mod);
        }

        public static int floorAverage(int x, int y) {
            return (x & y) + ((x ^ y) >> 1);
        }

    }
}

