#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:256000000")
using namespace std;
mt19937 ggen;
inline long long add(long long a, long long b, long long m) {
  return (a + b) % m;
}
inline long long sub(long long a, long long b, long long m) {
  return ((a - b) % m + m) % m;
}
inline long long mul(long long a, long long b, long long m) {
  long long d = (long double)a * b / m;
  long long res = a * b - m * d;
  while (res >= m) res -= m;
  while (res < 0) res += m;
  return res;
}
inline long long binpow(long long a, long long p, long long m) {
  if (m == 1) return 0;
  long long res = 1;
  while (p) {
    if (p & 1) res = mul(res, a, m);
    a = mul(a, a, m);
    p >>= 1;
  }
  return res;
}
int lp[41];
int dv[41];
vector<int> pr;
const int ps = 12;
void sieve() {
  lp[1] = 1;
  for (int i = 2; i <= 40; i++) {
    if (lp[i] == 0) {
      lp[i] = i;
      dv[i] = 1;
      pr.push_back(i);
    }
    for (int j = 0;
         j < (int)pr.size() && pr[j] <= lp[i] && (long long)(i)*pr[j] <= 40;
         j++) {
      lp[i * pr[j]] = pr[j];
      dv[i * pr[j]] = i;
    }
  }
}
long long gcd(long long a, long long b) {
  while (b) {
    a %= b;
    swap(a, b);
  }
  return a;
}
long long phi(long long a) {
  long long res = a;
  while (a != 1) {
    for (int i = 0; i < ps; i++) {
      if (a % pr[i] == 0) {
        res -= res / pr[i];
        while (a % pr[i] == 0) a /= pr[i];
      }
    }
  }
  return res;
}
inline long long obr(long long a, long long m) {
  return binpow(a, phi(m) - 1, m);
}
struct eq {
  long long p;
  long long m;
  eq() {}
  eq(long long p, long long m) : p(p), m(m) {}
};
eq merge(eq a, eq b) {
  if (a.p == -1 || b.p == -1) {
    return eq(-1, -1);
  }
  if (a.m == 1) return b;
  if (b.m == 1) return a;
  long long ta = a.m;
  long long tb = b.m;
  long long g = gcd(a.m, b.m);
  if (a.p % g != b.p % g) {
    return eq(-1, -1);
  }
  for (int i = 0; i < ps; i++) {
    int ca = 0, cb = 0;
    long long p_a = 1, p_b = 1;
    while (ta % pr[i] == 0) {
      ca++;
      p_a *= pr[i];
      ta /= pr[i];
    }
    while (tb % pr[i] == 0) {
      cb++;
      p_b *= pr[i];
      tb /= pr[i];
    }
    if (ca <= cb)
      a.m /= p_a;
    else
      b.m /= p_b;
  }
  a.p %= a.m;
  b.p %= b.m;
  if (a.m == 1) return b;
  if (b.m == 1) return a;
  long long x1 = a.p;
  long long r12 = obr(a.m, b.m);
  long long x2 = mul(sub(b.p, x1, b.m), r12, b.m);
  eq res;
  res.m = a.m * b.m;
  res.p = x1 + x2 * a.m;
  return res;
}
int n, m;
int sz[100010];
vector<vector<pair<int, int> > > pos;
eq seg[100010];
eq pc[100010][20];
int ss;
void precalc() {
  for (int i = 0; i < ss; i++) pc[i][0] = seg[i];
  for (int pw = 1; (1 << pw) <= ss; pw++) {
    for (int j = 0; j + (1 << pw) <= ss; j++) {
      pc[j][pw] = merge(pc[j][pw - 1], pc[j + (1 << (pw - 1))][pw - 1]);
    }
  }
}
eq get(int l, int r) {
  int dt = r - l + 1;
  int pi = 0;
  int pw = 1;
  while ((pw << 1) <= dt) {
    pw <<= 1;
    pi++;
  }
  return merge(pc[l][pi], pc[r - pw + 1][pi]);
}
int calc() {
  int res = 0;
  int l = 0;
  for (int i = 0; i < ss; i++) {
    while (l <= i && get(l, i).p == -1) l++;
    res = max(res, i - l + 1);
  }
  return res;
}
void solve() {
  sieve();
  cin >> n >> m;
  pos.resize(m + 1);
  for (int i = 0; i < n; i++) {
    cin >> sz[i];
    for (int j = 0; j < sz[i]; j++) {
      int a;
      cin >> a;
      pos[a].push_back(pair<int, int>(i, j));
    }
  }
  for (int i = 1; i <= m; i++) {
    int ctr = 0;
    int ans = 0;
    for (int j = 0; j <= (int)pos[i].size(); j++) {
      if (j != 0 && ((j == (int)pos[i].size()) ||
                     (pos[i][j].first != pos[i][j - 1].first + 1))) {
        ss = ctr;
        precalc();
        ans = max(ans, calc());
        ctr = 0;
      }
      if (j < (int)pos[i].size()) {
        seg[ctr].p = pos[i][j].second;
        seg[ctr].m = sz[pos[i][j].first];
        ctr++;
      }
    }
    cout << ans << '\n';
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  ggen = mt19937(13);
  solve();
  return 0;
}

### Prompt

Develop a solution in Cpp to the problem described below:

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

### Response

```cpp
#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:256000000")
using namespace std;
mt19937 ggen;
inline long long add(long long a, long long b, long long m) {
  return (a + b) % m;
}
inline long long sub(long long a, long long b, long long m) {
  return ((a - b) % m + m) % m;
}
inline long long mul(long long a, long long b, long long m) {
  long long d = (long double)a * b / m;
  long long res = a * b - m * d;
  while (res >= m) res -= m;
  while (res < 0) res += m;
  return res;
}
inline long long binpow(long long a, long long p, long long m) {
  if (m == 1) return 0;
  long long res = 1;
  while (p) {
    if (p & 1) res = mul(res, a, m);
    a = mul(a, a, m);
    p >>= 1;
  }
  return res;
}
int lp[41];
int dv[41];
vector<int> pr;
const int ps = 12;
void sieve() {
  lp[1] = 1;
  for (int i = 2; i <= 40; i++) {
    if (lp[i] == 0) {
      lp[i] = i;
      dv[i] = 1;
      pr.push_back(i);
    }
    for (int j = 0;
         j < (int)pr.size() && pr[j] <= lp[i] && (long long)(i)*pr[j] <= 40;
         j++) {
      lp[i * pr[j]] = pr[j];
      dv[i * pr[j]] = i;
    }
  }
}
long long gcd(long long a, long long b) {
  while (b) {
    a %= b;
    swap(a, b);
  }
  return a;
}
long long phi(long long a) {
  long long res = a;
  while (a != 1) {
    for (int i = 0; i < ps; i++) {
      if (a % pr[i] == 0) {
        res -= res / pr[i];
        while (a % pr[i] == 0) a /= pr[i];
      }
    }
  }
  return res;
}
inline long long obr(long long a, long long m) {
  return binpow(a, phi(m) - 1, m);
}
struct eq {
  long long p;
  long long m;
  eq() {}
  eq(long long p, long long m) : p(p), m(m) {}
};
eq merge(eq a, eq b) {
  if (a.p == -1 || b.p == -1) {
    return eq(-1, -1);
  }
  if (a.m == 1) return b;
  if (b.m == 1) return a;
  long long ta = a.m;
  long long tb = b.m;
  long long g = gcd(a.m, b.m);
  if (a.p % g != b.p % g) {
    return eq(-1, -1);
  }
  for (int i = 0; i < ps; i++) {
    int ca = 0, cb = 0;
    long long p_a = 1, p_b = 1;
    while (ta % pr[i] == 0) {
      ca++;
      p_a *= pr[i];
      ta /= pr[i];
    }
    while (tb % pr[i] == 0) {
      cb++;
      p_b *= pr[i];
      tb /= pr[i];
    }
    if (ca <= cb)
      a.m /= p_a;
    else
      b.m /= p_b;
  }
  a.p %= a.m;
  b.p %= b.m;
  if (a.m == 1) return b;
  if (b.m == 1) return a;
  long long x1 = a.p;
  long long r12 = obr(a.m, b.m);
  long long x2 = mul(sub(b.p, x1, b.m), r12, b.m);
  eq res;
  res.m = a.m * b.m;
  res.p = x1 + x2 * a.m;
  return res;
}
int n, m;
int sz[100010];
vector<vector<pair<int, int> > > pos;
eq seg[100010];
eq pc[100010][20];
int ss;
void precalc() {
  for (int i = 0; i < ss; i++) pc[i][0] = seg[i];
  for (int pw = 1; (1 << pw) <= ss; pw++) {
    for (int j = 0; j + (1 << pw) <= ss; j++) {
      pc[j][pw] = merge(pc[j][pw - 1], pc[j + (1 << (pw - 1))][pw - 1]);
    }
  }
}
eq get(int l, int r) {
  int dt = r - l + 1;
  int pi = 0;
  int pw = 1;
  while ((pw << 1) <= dt) {
    pw <<= 1;
    pi++;
  }
  return merge(pc[l][pi], pc[r - pw + 1][pi]);
}
int calc() {
  int res = 0;
  int l = 0;
  for (int i = 0; i < ss; i++) {
    while (l <= i && get(l, i).p == -1) l++;
    res = max(res, i - l + 1);
  }
  return res;
}
void solve() {
  sieve();
  cin >> n >> m;
  pos.resize(m + 1);
  for (int i = 0; i < n; i++) {
    cin >> sz[i];
    for (int j = 0; j < sz[i]; j++) {
      int a;
      cin >> a;
      pos[a].push_back(pair<int, int>(i, j));
    }
  }
  for (int i = 1; i <= m; i++) {
    int ctr = 0;
    int ans = 0;
    for (int j = 0; j <= (int)pos[i].size(); j++) {
      if (j != 0 && ((j == (int)pos[i].size()) ||
                     (pos[i][j].first != pos[i][j - 1].first + 1))) {
        ss = ctr;
        precalc();
        ans = max(ans, calc());
        ctr = 0;
      }
      if (j < (int)pos[i].size()) {
        seg[ctr].p = pos[i][j].second;
        seg[ctr].m = sz[pos[i][j].first];
        ctr++;
      }
    }
    cout << ans << '\n';
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  ggen = mt19937(13);
  solve();
  return 0;
}

```