soj924

http://120.27.222.204:12243/problem/924

可恶，又赛后过题。

以下全部规定$a_{i,l_i+1}=\infin$。

先来讲一个easy的$O(nqlog^2{(l+q)})$的做法（其实也想了不少时间吧）。

$1.$二分最大的$x$，找到$a_{i,j}=x$；

$2.$设$y=\min\limits_{k=1}^ja_{i,k}$；

$3.$设$z_e,e \not= i$表示第$e$个数组比$y$大的最小位置，并令$z_i=0$；

$4.$判断$i+\sum\limits_{e=1}^n{(z_e - 1)}$是否小于等于$k$。

其中外层需要二分，并且对于每个$x$都要在线段树上二分求$z_x$，所以总复杂度为$O(nqlog^2(l+q))$。

现在我们希望能直接找到$y$，也就是希望最初二分的数组是个单调递增的，是该数组前缀最大值形成的，可惜我不会维护单调递增序列。

不过事物的发展是前进性和曲折性的统一，我们有了个别的想法：直接线段树二分！

考虑转化上述easy的步骤，使得其更适合直接线段树二分。

$1.$二分最大的$x$，找到$a_{i,j}=x$；

$2.$设$z_e$表示第$e$个数组大于等于$x$的最小位置；

$3.$判断$\sum\limits_{e=1}^n(z_e-1)+1$是否小于等于$k$。

我们不再设$y$，也不再令$z_i=0$。我们会惊奇的发现，这时二分出来的$x$一定是$i$数组的某个前缀最大值，因为如果不是，$x$一定能二分到那个前缀最大值。那么，我们相当于找到了easy步骤中的$y$。

反推正确答案，答案就是$a_{i,j+k-(\sum\limits_{e=1}^n(z_e-1)+1)}$。（这个下标虽然看起来有点繁琐，但是自己写还是很显然的）。

但是上述方法还是要$n$次线段树二分。我们可以只维护一棵权值线段树，这棵线段树的每个节点维护一个长度为$n$的数组，表示权值在$[L,R)$区间内的在每一个数组内的最小位置。只要找到一个最右的点，满足上述条件即可，具体可以看代码。

复杂度$O(nqlog{(l+q)})$。

#include <bits/stdc++.h>
#define ld double
#define ull unsigned long long
#define ll long long
#define pii pair <int, int>
#define iiii pair <int, pii >
#define mp make_pair
#define INF 1000000000
#define rep(i, x) for(int (i) = 0; (i) < (x); (i)++)
inline int getint() {
  int x = 0, p = 1; char c = getchar();
  while (c <= 32) c = getchar();
  if (c == 45) p = -p, c = getchar();
  while (c > 32) x = x * 10 + c - 48, c = getchar();
  return x * p;
}
using namespace std;
const int mod = 1e9 + 7;
inline void reduce(int &x) { x += x >> 31 & mod; }
inline int mul(int x, int y) { return 1ll * x * y % mod; }
//ruogu_alter
const int N = 7e5 + 5;
const int M = 5e5 + 5;
const int Q = 2e5 + 5;
int dat[N << 2][10], n, len[N], q, a[10][M];
pii pos[N];
int qx[Q], qy[Q], qz[Q], op[Q], tmp[10];
vector<int> id;
//
void up(int k) {
  rep(i, n) {
    dat[k][i] = min(dat[2 * k + 1][i], dat[2 * k + 2][i]);
  }
}
void build(int l, int r, int k) {
  if (r - l == 1) {
    rep(i, n) dat[k][i] = len[i];
    return;
  }
  int mid = (l + r) >> 1;
  build(l, mid, 2 * k + 1);
  build(mid, r, 2 * k + 2);
  up(k);
}
void modify(int l, int r, int p, int k, int x, int v) {
  if (r - l == 1) {
    dat[k][x] = v;
    return;
  }
  int mid = (l + r) >> 1;
  if (p < mid) modify(l, mid, p, 2 * k + 1, x, v);
  else modify(mid, r, p, 2 * k + 2, x, v);
  dat[k][x] = min(dat[2 * k + 1][x], dat[2 * k + 2][x]);
}
int qry(int l, int r, int k, int p) {
  if (r - l == 1) {
    rep(i, n) tmp[i] = min(tmp[i], dat[k][i]);
    return l;
  }
  int mid = (l + r) >> 1, sum = 0;
  rep(i, n) sum += min(tmp[i], dat[2 * k + 2][i]);
  if (sum > p) {
    rep(i, n) tmp[i] = min(tmp[i], dat[2 * k + 2][i]);
    return qry(l, mid, 2 * k + 1, p); 
  } 
  else return qry(mid, r, 2 * k + 2, p);
}
int main() {
  n = getint(); q = getint();
  rep(i, n) {
    len[i] = getint();
    rep(j, len[i]) {
      a[i][j] = getint();
      id.emplace_back(a[i][j]);
    }
  }
  rep(i, q) {
    op[i] = getint(); qx[i] = getint() - 1;
    if (op[i] == 1) {
      qy[i] = getint() - 1; qz[i] = getint();
      id.emplace_back(qz[i]);
    }
  }
  sort(id.begin(), id.end());
  id.resize(unique(id.begin(), id.end()) - id.begin());
  rep(i, q) if (op[i] == 1) {
    qz[i] = lower_bound(id.begin(), id.end(), qz[i]) - id.begin();
  }
  int m = id.size();
  build(0, m, 0);
  rep(i, m) pos[i] = mp(-1, -1);
  rep(i, n) rep(j, len[i]) {
    a[i][j] = lower_bound(id.begin(), id.end(), a[i][j]) - id.begin();
    assert(pos[a[i][j]] == mp(-1, -1));
    pos[a[i][j]] = mp(i, j);
    modify(0, m, a[i][j], 0, i, j); 
  }
  rep(i, q) {
    if (op[i] == 1) {
      modify(0, m, a[qx[i]][qy[i]], 0, qx[i], len[qx[i]]);
      pos[a[qx[i]][qy[i]]] = mp(-1, -1);
      assert(pos[qz[i]] == mp(-1, -1));
      a[qx[i]][qy[i]] = qz[i]; pos[qz[i]] = mp(qx[i], qy[i]);
      modify(0, m, a[qx[i]][qy[i]], 0, qx[i], qy[i]);
    }
    else {
      rep(i, n) tmp[i] = len[i]; int k = qx[i], sum = 0, h;
      pii res = pos[h = qry(0, m, 0, k)]; 
      rep(i, n) sum += tmp[i];
      assert(sum <= k);
      printf("%d\n", id[a[res.first][k - sum + res.second]]); 
    }
  }
  return 0;
}