#include <bits/stdc++.h>
using namespace std;
template <class T>
inline void amin(T &x, const T &y) {
  if (y < x) x = y;
}
template <class T>
inline void amax(T &x, const T &y) {
  if (x < y) x = y;
}
template <class Iter>
void rprintf(const char *fmt, Iter begin, Iter end) {
  for (bool sp = 0; begin != end; ++begin) {
    if (sp)
      putchar(' ');
    else
      sp = true;
    printf(fmt, *begin);
  }
  putchar('\n');
}
template <class T>
struct Deque {
  vector<T> fr, bk;
  Deque() {}
  template <class Iter>
  Deque(Iter first, Iter last) : bk(first, last) {}
  size_t size() const { return fr.size() + bk.size(); }
  bool empty() const { return fr.empty() && bk.empty(); }
  T &operator[](size_t i) {
    if (i < fr.size()) return fr[fr.size() - 1 - i];
    return bk[i - fr.size()];
  }
  const T &operator[](size_t i) const {
    if (i < fr.size()) return fr[fr.size() - 1 - i];
    return bk[i - fr.size()];
  }
  T &back() {
    if (bk.empty()) return fr[0];
    return bk.back();
  }
  const T &back() const {
    if (bk.empty()) return fr[0];
    return bk.back();
  }
  void push_back(const T &t) { bk.push_back(t); }
  template <typename... Args>
  void emplace_back(Args &&...args) {
    bk.emplace_back(forward<Args>(args)...);
  }
  void pop_back() {
    if (bk.empty()) {
      pop_back_helper(fr, bk);
    } else {
      bk.pop_back();
    }
  }
  T &front() {
    if (fr.empty()) return bk[0];
    return fr.back();
  }
  const T &front() const {
    if (fr.empty()) return bk[0];
    return fr.back();
  }
  void push_front(const T &t) { fr.push_back(t); }
  template <typename... Args>
  void emplace_front(Args &&...args) {
    fr.emplace_back(forward<Args>(args)...);
  }
  void pop_front() {
    if (fr.empty()) {
      pop_back_helper(bk, fr);
    } else {
      fr.pop_back();
    }
  }
  void reverse() { swap(fr, bk); }
  static void pop_back_helper(vector<T> &fr, vector<T> &bk) {
    size_t s = fr.size();
    size_t t = (s - 1) / 2;
    bk.resize(t);
    for (size_t i = 1; i <= t; i++) bk[t - i] = fr[i];
    for (size_t i = t + 1; i < s; i++) fr[i - t - 1] = fr[i];
    fr.resize(s - 1 - t);
  }
  struct iterator {
    using difference_type = size_t;
    using value_type = T;
    using pointer = T *;
    using reference = T &;
    using iterator_category = typename vector<T>::iterator::iterator_category;
    using sup_iter = typename vector<T>::iterator;
    sup_iter fr_it, bk_it;
    sup_iter fr_begin, bk_begin;
    iterator(sup_iter fr_it_, sup_iter bk_it_, sup_iter fr_begin_,
             sup_iter bk_begin_) {
      fr_it = fr_it_;
      bk_it = bk_it_;
      fr_begin = fr_begin_;
      bk_begin = bk_begin_;
    }
    iterator &operator=(const iterator &y) {
      fr_it = y.fr_it;
      bk_it = y.bk_it;
      fr_begin = y.fr_begin;
      bk_begin = y.bk_begin;
      return *this;
    }
    iterator &operator++() {
      if (fr_it == fr_begin)
        ++bk_it;
      else
        --fr_it;
      return *this;
    }
    iterator operator++(int) {
      iterator tmp = *this;
      ++*this;
      return tmp;
    }
    iterator &operator--() {
      if (bk_it == bk_begin)
        ++fr_it;
      else
        --bk_it;
      return *this;
    }
    iterator operator--(int) {
      iterator tmp = *this;
      --*this;
      return tmp;
    }
    T &operator*() {
      if (fr_it == fr_begin)
        return *bk_it;
      else
        return *prev(fr_it);
    }
    T *operator->() {
      if (fr_it == fr_begin)
        return bk_it;
      else
        return prev(fr_it);
    }
    bool operator==(const iterator &y) const {
      return fr_it == y.fr_it && bk_it == y.bk_it;
    }
    bool operator!=(const iterator &y) const { return !(*this == y); }
    bool operator<(const iterator &y) const {
      return fr_it > y.fr_it || bk_it < y.bk_it;
    }
    bool operator>(const iterator &y) const { return y < *this; }
    bool operator<=(const iterator &y) const { return !(y < *this); }
    bool operator>=(const iterator &y) const { return !(*this < y); }
    size_t operator-(const iterator &y) const {
      return (bk_it - y.bk_it) + (y.fr_it - fr_it);
    }
    iterator &operator+=(size_t k) {
      size_t s = fr_it - fr_begin;
      if (s >= k) {
        fr_it -= k;
      } else {
        fr_it = fr_begin;
        bk_it += k - s;
      }
      return *this;
    }
    iterator operator+(size_t k) const {
      iterator it = *this;
      return it += k;
    }
    iterator &operator-=(size_t k) {
      size_t s = bk_it - bk_begin;
      if (s >= k) {
        bk_it -= k;
      } else {
        bk_it = bk_begin;
        fr_it += k - s;
      }
      return *this;
    }
    iterator operator-(size_t k) const {
      iterator it = *this;
      return it -= k;
    }
  };
  iterator begin() {
    return iterator(fr.end(), bk.begin(), fr.begin(), bk.begin());
  }
  iterator end() {
    return iterator(fr.begin(), bk.end(), fr.begin(), bk.begin());
  }
};
int N;
int W;
int A[1000011];
long long ans[1000011];
long long add[1000011];
void MAIN() {
  scanf("%d%d", &N, &W);
  for (int $ = 0, $_len = (N); $ < $_len; ++$) {
    int L;
    scanf("%d", &L);
    for (int i = 0, i_len = (L); i < i_len; ++i) scanf("%d", A + i);
    if (L * 2 >= W) {
      int x = 0, y = 0;
      Deque<int> dq;
      for (int i = 0, i_len = (W); i < i_len; ++i) {
        while (y < L && y <= i) {
          while (!dq.empty() && dq.back() < A[y]) dq.pop_back();
          dq.push_back(A[y]);
          y++;
        }
        while (x < i - W + L) {
          if (!dq.empty() && A[x] == dq.front()) dq.pop_front();
          x++;
        }
        assert(!dq.empty());
        int tmp = dq.front();
        if (i + L < W || L <= i) amax(tmp, 0);
        ans[i] += tmp;
      }
    } else {
      int tmp = 0;
      for (int i = 0, i_len = (L); i < i_len; ++i) {
        amax(tmp, A[i]);
        ans[i] += tmp;
      }
      tmp = 0;
      for (int i = 0, i_len = (L); i < i_len; ++i) {
        amax(tmp, A[L - 1 - i]);
        ans[W - 1 - i] += tmp;
      }
      add[L] += tmp;
      add[W - L] -= tmp;
    }
  }
  for (int i = 0, i_len = (W); i < i_len; ++i) {
    add[i + 1] += add[i];
    ans[i] += add[i];
  }
  rprintf("%lld", ans, ans + W);
}
int main() {
  int TC = 1;
  for (int tc = 0, tc_len = (TC); tc < tc_len; ++tc) MAIN();
  return 0;
}

### Prompt

Generate a CPP solution to the following problem:

You are given n arrays that can have different sizes. You also have a table with w columns and n rows. The i-th array is placed horizontally in the i-th row. You can slide each array within its row as long as it occupies several consecutive cells and lies completely inside the table.

You need to find the maximum sum of the integers in the j-th column for each j from 1 to w independently.

<image> Optimal placements for columns 1, 2 and 3 are shown on the pictures from left to right.

Note that you can exclude any array out of a column provided it remains in the window. In this case its value is considered to be zero.

Input

The first line contains two integers n (1 ≤ n ≤ 10^{6}) and w (1 ≤ w ≤ 10^{6}) — the number of arrays and the width of the table.

Each of the next n lines consists of an integer l_{i} (1 ≤ l_{i} ≤ w), the length of the i-th array, followed by l_{i} integers a_{i1}, a_{i2}, …, a_{il_i} (-10^{9} ≤ a_{ij} ≤ 10^{9}) — the elements of the array.

The total length of the arrays does no exceed 10^{6}.

Output

Print w integers, the i-th of them should be the maximum sum for column i.

Examples

Input


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


Output


10 15 16 


Input


2 2
2 7 8
1 -8


Output


7 8 

Note

Illustration for the first example is in the statement.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
template <class T>
inline void amin(T &x, const T &y) {
  if (y < x) x = y;
}
template <class T>
inline void amax(T &x, const T &y) {
  if (x < y) x = y;
}
template <class Iter>
void rprintf(const char *fmt, Iter begin, Iter end) {
  for (bool sp = 0; begin != end; ++begin) {
    if (sp)
      putchar(' ');
    else
      sp = true;
    printf(fmt, *begin);
  }
  putchar('\n');
}
template <class T>
struct Deque {
  vector<T> fr, bk;
  Deque() {}
  template <class Iter>
  Deque(Iter first, Iter last) : bk(first, last) {}
  size_t size() const { return fr.size() + bk.size(); }
  bool empty() const { return fr.empty() && bk.empty(); }
  T &operator[](size_t i) {
    if (i < fr.size()) return fr[fr.size() - 1 - i];
    return bk[i - fr.size()];
  }
  const T &operator[](size_t i) const {
    if (i < fr.size()) return fr[fr.size() - 1 - i];
    return bk[i - fr.size()];
  }
  T &back() {
    if (bk.empty()) return fr[0];
    return bk.back();
  }
  const T &back() const {
    if (bk.empty()) return fr[0];
    return bk.back();
  }
  void push_back(const T &t) { bk.push_back(t); }
  template <typename... Args>
  void emplace_back(Args &&...args) {
    bk.emplace_back(forward<Args>(args)...);
  }
  void pop_back() {
    if (bk.empty()) {
      pop_back_helper(fr, bk);
    } else {
      bk.pop_back();
    }
  }
  T &front() {
    if (fr.empty()) return bk[0];
    return fr.back();
  }
  const T &front() const {
    if (fr.empty()) return bk[0];
    return fr.back();
  }
  void push_front(const T &t) { fr.push_back(t); }
  template <typename... Args>
  void emplace_front(Args &&...args) {
    fr.emplace_back(forward<Args>(args)...);
  }
  void pop_front() {
    if (fr.empty()) {
      pop_back_helper(bk, fr);
    } else {
      fr.pop_back();
    }
  }
  void reverse() { swap(fr, bk); }
  static void pop_back_helper(vector<T> &fr, vector<T> &bk) {
    size_t s = fr.size();
    size_t t = (s - 1) / 2;
    bk.resize(t);
    for (size_t i = 1; i <= t; i++) bk[t - i] = fr[i];
    for (size_t i = t + 1; i < s; i++) fr[i - t - 1] = fr[i];
    fr.resize(s - 1 - t);
  }
  struct iterator {
    using difference_type = size_t;
    using value_type = T;
    using pointer = T *;
    using reference = T &;
    using iterator_category = typename vector<T>::iterator::iterator_category;
    using sup_iter = typename vector<T>::iterator;
    sup_iter fr_it, bk_it;
    sup_iter fr_begin, bk_begin;
    iterator(sup_iter fr_it_, sup_iter bk_it_, sup_iter fr_begin_,
             sup_iter bk_begin_) {
      fr_it = fr_it_;
      bk_it = bk_it_;
      fr_begin = fr_begin_;
      bk_begin = bk_begin_;
    }
    iterator &operator=(const iterator &y) {
      fr_it = y.fr_it;
      bk_it = y.bk_it;
      fr_begin = y.fr_begin;
      bk_begin = y.bk_begin;
      return *this;
    }
    iterator &operator++() {
      if (fr_it == fr_begin)
        ++bk_it;
      else
        --fr_it;
      return *this;
    }
    iterator operator++(int) {
      iterator tmp = *this;
      ++*this;
      return tmp;
    }
    iterator &operator--() {
      if (bk_it == bk_begin)
        ++fr_it;
      else
        --bk_it;
      return *this;
    }
    iterator operator--(int) {
      iterator tmp = *this;
      --*this;
      return tmp;
    }
    T &operator*() {
      if (fr_it == fr_begin)
        return *bk_it;
      else
        return *prev(fr_it);
    }
    T *operator->() {
      if (fr_it == fr_begin)
        return bk_it;
      else
        return prev(fr_it);
    }
    bool operator==(const iterator &y) const {
      return fr_it == y.fr_it && bk_it == y.bk_it;
    }
    bool operator!=(const iterator &y) const { return !(*this == y); }
    bool operator<(const iterator &y) const {
      return fr_it > y.fr_it || bk_it < y.bk_it;
    }
    bool operator>(const iterator &y) const { return y < *this; }
    bool operator<=(const iterator &y) const { return !(y < *this); }
    bool operator>=(const iterator &y) const { return !(*this < y); }
    size_t operator-(const iterator &y) const {
      return (bk_it - y.bk_it) + (y.fr_it - fr_it);
    }
    iterator &operator+=(size_t k) {
      size_t s = fr_it - fr_begin;
      if (s >= k) {
        fr_it -= k;
      } else {
        fr_it = fr_begin;
        bk_it += k - s;
      }
      return *this;
    }
    iterator operator+(size_t k) const {
      iterator it = *this;
      return it += k;
    }
    iterator &operator-=(size_t k) {
      size_t s = bk_it - bk_begin;
      if (s >= k) {
        bk_it -= k;
      } else {
        bk_it = bk_begin;
        fr_it += k - s;
      }
      return *this;
    }
    iterator operator-(size_t k) const {
      iterator it = *this;
      return it -= k;
    }
  };
  iterator begin() {
    return iterator(fr.end(), bk.begin(), fr.begin(), bk.begin());
  }
  iterator end() {
    return iterator(fr.begin(), bk.end(), fr.begin(), bk.begin());
  }
};
int N;
int W;
int A[1000011];
long long ans[1000011];
long long add[1000011];
void MAIN() {
  scanf("%d%d", &N, &W);
  for (int $ = 0, $_len = (N); $ < $_len; ++$) {
    int L;
    scanf("%d", &L);
    for (int i = 0, i_len = (L); i < i_len; ++i) scanf("%d", A + i);
    if (L * 2 >= W) {
      int x = 0, y = 0;
      Deque<int> dq;
      for (int i = 0, i_len = (W); i < i_len; ++i) {
        while (y < L && y <= i) {
          while (!dq.empty() && dq.back() < A[y]) dq.pop_back();
          dq.push_back(A[y]);
          y++;
        }
        while (x < i - W + L) {
          if (!dq.empty() && A[x] == dq.front()) dq.pop_front();
          x++;
        }
        assert(!dq.empty());
        int tmp = dq.front();
        if (i + L < W || L <= i) amax(tmp, 0);
        ans[i] += tmp;
      }
    } else {
      int tmp = 0;
      for (int i = 0, i_len = (L); i < i_len; ++i) {
        amax(tmp, A[i]);
        ans[i] += tmp;
      }
      tmp = 0;
      for (int i = 0, i_len = (L); i < i_len; ++i) {
        amax(tmp, A[L - 1 - i]);
        ans[W - 1 - i] += tmp;
      }
      add[L] += tmp;
      add[W - L] -= tmp;
    }
  }
  for (int i = 0, i_len = (W); i < i_len; ++i) {
    add[i + 1] += add[i];
    ans[i] += add[i];
  }
  rprintf("%lld", ans, ans + W);
}
int main() {
  int TC = 1;
  for (int tc = 0, tc_len = (TC); tc < tc_len; ++tc) MAIN();
  return 0;
}

```