代码

#define PROF 1
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
#include <emmintrin.h>
#pragma GCC optimize("O3")
// ================= NOIP2017 列队 (noip17f) =================
// Model:
//   Row r holds m-1 elements (cols 1..m-1): initially (r-1)*m+1 .. (r-1)*m+(m-1).
//   The last column (col m) holds n elements: initially i*m (i=1..n).
//   Query (x,y):
//     cval = column.remove_kth(x)             // element at (x,m)
//     if y < m: aval = row[x].remove_kth(y); print aval; row[x].append(cval);
//     else:     aval = cval;                 print cval;
//     column.append(aval)
//   "k-th alive with deletions and append-at-end" for both structure kinds:
//     smallest p with (p - #deleted<=p) == k.  (unappended slots count as alive in
//     this formula but the fixpoint never lands there - see notes.)
//   Implemented: deleted bitset + per-word popcounts + Fenwick over 512-bit block
//   alive counts + in-word select.  Rows with few queries use a sorted deleted array.
typedef unsigned char u8;
typedef unsigned short u16;
typedef unsigned u32;
typedef unsigned long long u64;
typedef long long i64;

static const u8 *gip;
static u8 *gob;
static unsigned gSN;   // stdin size (set by the startup bypass)
#ifdef PROF
static unsigned long PT[16]; static int PTC;
static inline unsigned long rdt(){ unsigned a,d; __asm__ volatile("rdtsc":"=a"(a),"=d"(d)); return ((unsigned long)d<<32)|a; }
#define PTICK() PT[PTC++]=rdt()
#else
#define PTICK() ((void)0)
#endif

// ------------------------- fast input -------------------------
static const u64 MASKV[9] = {0ULL, 0xFFULL, 0xFFFFULL, 0xFFFFFFULL, 0xFFFFFFFFULL,
                             0xFFFFFFFFFFULL, 0xFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFULL,
                             0xFFFFFFFFFFFFFFFFULL};
static const u32 INV5[9] = {1u,        0xCCCCCCCDu, 0xC28F5C29u, 0x26E978D5u, 0x3AFB7E91u,
                            0x0BCBE61Du, 0x68C26139u, 0xAE8D46A5u, 0x22E90E21u};

static inline u32 rd() {
  // RIGHT-ALIGN the k digits by shifting t LEFT 8*(8-k) bits: the separator byte
  // (t's byte k) and everything after it shifts out of the 64-bit word, so the
  // three-level SWAR fusion then yields the value DIRECTLY -- no mask, no >>j,
  // no in-table magic multiply.
  for (;;) {
    u64 x;
    __builtin_memcpy(&x, gip, 8);
    u64 t = x ^ 0x3030303030303030ULL;
    u64 mm = ((t + 0x7676767676767676ULL) | t) & 0x8080808080808080ULL;
    u32 k = mm ? (u32)(__builtin_ctzll(mm) >> 3) : 8u;
    if (k == 0) { gip++; continue; }
    u64 d = t << ((8u - k) << 3);
    u64 c1 = (d * 10 + (d >> 8)) & 0x00FF00FF00FF00FFULL;
    u64 c2 = (c1 * 100 + (c1 >> 16)) & 0x0000FFFF0000FFFFULL;
    u64 c3 = (c2 * 10000 + (c2 >> 32));
    gip += k + 1;
    return (u32)c3;
  }
}

// ------------------------- fast output -------------------------
static const char D2[201] =
    "00010203040506070809101112131415161718192021222324252627282930313233343536373839"
    "40414243444546474849505152535455565758596061626364656667686970717273747576777879"
    "8081828384858687888990919293949596979899";

// ------------------------- windowed query-line parse -------------------------
// The scalar reader's chain is  load -> xor -> add -> or -> and -> tzcnt -> (>>3) -> gip += k+1
// and it runs TWICE per query because x's length determines y's start address.  Here ONE
// 16-byte load yields the newline offset (the only loop-carried quantity: gip += nl+1) and the
// two delimiter positions from a digit mask -- so the address chain is one tzcnt per QUERY, and
// both VALUES come off the same register, off the chain.
// Safety: only called when 16 bytes are readable at gip.  sep1 <= 7 and sep2 <= sep1+8 keep the
// second 8-byte read inside those 16 bytes.  Returns 0 (gip untouched) unless the line is
// exactly "<digits> <digits>\n", so any other whitespace layout falls back to rd().
static inline u32 winparse(u32 *px, u32 *py) {
  __m128i v = _mm_loadu_si128((const __m128i *)gip);
  u32 nlm = (u32)_mm_movemask_epi8(_mm_cmpeq_epi8(v, _mm_set1_epi8('\n')));
  if (!nlm) return 0;
  __m128i dg = _mm_and_si128(_mm_cmpgt_epi8(v, _mm_set1_epi8(0x2F)),
                             _mm_cmpgt_epi8(_mm_set1_epi8(0x3A), v));
  u32 nd = (~(u32)_mm_movemask_epi8(dg)) & 0xFFFFu;
  u32 sep1 = (u32)__builtin_ctz(nd);
  if (sep1 == 0 || sep1 > 7) return 0;
  u32 nd2 = nd >> (sep1 + 1);
  if (!nd2) return 0;
  u32 sep2 = sep1 + 1 + (u32)__builtin_ctz(nd2);
  u32 nl = (u32)__builtin_ctz(nlm);
  if (sep2 != nl || sep2 > sep1 + 8) return 0;
  u64 w0; __builtin_memcpy(&w0, gip, 8);
  u64 t0 = (w0 ^ 0x3030303030303030ULL) << ((8u - sep1) << 3);
  u64 a1 = (t0 * 10 + (t0 >> 8)) & 0x00FF00FF00FF00FFULL;
  u64 a2 = (a1 * 100 + (a1 >> 16)) & 0x0000FFFF0000FFFFULL;
  *px = (u32)(a2 * 10000 + (a2 >> 32));
  u32 ky = sep2 - sep1 - 1;
  u64 w1; __builtin_memcpy(&w1, gip + sep1 + 1, 8);
  u64 t1 = (w1 ^ 0x3030303030303030ULL) << ((8u - ky) << 3);
  u64 b1 = (t1 * 10 + (t1 >> 8)) & 0x00FF00FF00FF00FFULL;
  u64 b2 = (b1 * 100 + (b1 >> 16)) & 0x0000FFFF0000FFFFULL;
  *py = (u32)(b2 * 10000 + (b2 >> 32));
  gip += nl + 1;
  return 1;
}
static u32 T4[10000];            // 40 KB: T4[i] = the 4 zero-padded ASCII digits of i
static u64 POW10[20];
static u8  LB[65];               // LB[bl] = digits(2^(bl-1))  (a LOWER bound on digits for bitlen bl)
static inline void writer_init() {
  for (u32 i = 0; i < 10000; i++) {
    u32 h = i / 100, l = i - h * 100;
    u8 *p = (u8 *)&T4[i];
    p[0] = (u8)D2[2*h]; p[1] = (u8)D2[2*h+1]; p[2] = (u8)D2[2*l]; p[3] = (u8)D2[2*l+1];
  }
  u64 p = 1; for (int i = 0; i < 20; i++) { POW10[i] = p; p *= 10; }
  for (int bl = 1; bl <= 64; bl++) {
    u64 lo = (bl == 1) ? 1ULL : (1ULL << (bl - 1));
    u32 d = 1; u64 t = 1; while (t * 10 <= lo) { t *= 10; d++; }
    LB[bl] = (u8)d;
  }
}
// v <= n*m <= 9e10 (11 digits); guard covers v < 1e12.  Writes up to 16 bytes.
static inline u8 *wr(u8 *o, u64 v) {  // len 1..11, writes 16 bytes (over-write ok)
  if (v < 10) { o[0] = (u8)('0' + v); o[1] = '\n'; return o + 2; }
  u32 bl = 64u - (u32)__builtin_clzll(v);
  u32 d0 = LB[bl];
  u32 len = d0 + (v >= POW10[d0] ? 1u : 0u);
  u64 hv = v / 100000000ULL;                 // <= 999 for v < 1e11
  u32 lo8 = (u32)(v - hv * 100000000ULL);
  u32 hi = (u32)hv;
  u32 a = lo8 / 10000, b = lo8 - a * 10000;
  u32 c = hi / 10000,  d = hi  - c * 10000;
  u8 tmp[32];
  __builtin_memcpy(tmp +  0, &T4[c], 4);
  __builtin_memcpy(tmp +  4, &T4[d], 4);
  __builtin_memcpy(tmp +  8, &T4[a], 4);
  __builtin_memcpy(tmp + 12, &T4[b], 4);
  __builtin_memcpy(o, tmp + 16 - len, 8);
  __builtin_memcpy(o + 8, tmp + 16 - len + 8, 8);
  o[len] = '\n';
  return o + len + 1;
}
static inline u8 *wr_old(u8 *o, u64 v) {  // exact-length version (kept for the tail)
  u8 tmp[24];
  u32 i = 24;
  if (v < 10) { o[0] = (u8)('0' + v); o[1] = '\n'; return o + 2; }
  while (v >= 100) {
    u32 r = (u32)(v % 100);
    v /= 100;
    i -= 2;
    tmp[i] = D2[2 * r];
    tmp[i + 1] = D2[2 * r + 1];
  }
  if (v < 10) {
    tmp[--i] = (u8)('0' + v);
  } else {
    i -= 2;
    tmp[i] = D2[2 * v];
    tmp[i + 1] = D2[2 * v + 1];
  }
  u32 len = 24 - i;
  for (u32 w = 0; w < len; w++) o[w] = tmp[i + w];
  o[len] = '\n';
  return o + len + 1;
}

static inline u8 *wr_safe(u8 *o, u64 v) {  // exact-length version (for the tail)
  u8 tmp[24];
  u32 i = 24;
  if (v < 10) { o[0] = (u8)('0' + v); o[1] = '\n'; return o + 2; }
  while (v >= 100) {
    u32 r = (u32)(v % 100);
    v /= 100;
    i -= 2;
    tmp[i] = D2[2 * r];
    tmp[i + 1] = D2[2 * r + 1];
  }
  if (v < 10) {
    tmp[--i] = (u8)('0' + v);
  } else {
    i -= 2;
    tmp[i] = D2[2 * v];
    tmp[i + 1] = D2[2 * v + 1];
  }
  u32 len = 24 - i;
  for (u32 w = 0; w < len; w++) o[w] = tmp[i + w];
  o[len] = '\n';
  return o + len + 1;
}

// ------------------------- k-th alive: FLAT 3-LEVEL, O(1) UPDATE -------------------------
// Geometry: word=64b, block=8 words=512b, group=8 blocks=4096b, super=8 groups=32768b.
// The 11-level binary Fenwick is replaced by three flat u16 count arrays scanned with SSE2
// prefix-sum + movemask; the update is FIVE independent stores instead of an 11-entry walk.
// Every level array is zero-padded to a multiple of 8 so every scan is a full 8-lane vector.
static inline __m128i pf16(__m128i v) {
  v = _mm_add_epi16(v, _mm_slli_si128(v, 2));
  v = _mm_add_epi16(v, _mm_slli_si128(v, 4));
  v = _mm_add_epi16(v, _mm_slli_si128(v, 8));
  return v;
}
// UNSIGNED u16 compare a>b.  A full super sums to exactly 32768, which _mm_cmpgt_epi16 (SIGNED)
// reads as negative -- the XOR the sign bit trick is required, not cosmetic.
static inline __m128i gt16u(__m128i a, __m128i b) {
  const __m128i sg_ = _mm_set1_epi16((short)0x8000);
  return _mm_cmpgt_epi16(_mm_xor_si128(a, sg_), _mm_xor_si128(b, sg_));
}
// first lane whose INCLUSIVE prefix reaches rem; also yields the EXCLUSIVE prefix at that lane
static inline u32 sel8(const u16 *p, u32 rem, u32 *sub) {
  __m128i inc = pf16(_mm_loadu_si128((const __m128i *)p));
  u32 msk = (u32)_mm_movemask_epi8(gt16u(inc, _mm_set1_epi16((short)(rem - 1))));
  u32 j = (u32)__builtin_ctz(msk) >> 1;
  u16 buf[8];
  // EXCLUSIVE prefix: lane j must hold inc[j-1], i.e. a shift LEFT in byte position.
  // (_mm_srli_si128 shifts the lane index DOWN -- it gives inc[j+1], which is INVERTED.)
  _mm_storeu_si128((__m128i *)buf, _mm_slli_si128(inc, 2));
  *sub = (u32)buf[j];
  return j;
}
static inline u32 sel8w(const u8 *pw, u32 rem, u32 *sub) {
  __m128i b8 = _mm_loadl_epi64((const __m128i *)pw);
  __m128i a = _mm_sub_epi16(_mm_set1_epi16(64), _mm_unpacklo_epi8(b8, _mm_setzero_si128()));
  __m128i inc = pf16(a);
  u32 msk = (u32)_mm_movemask_epi8(gt16u(inc, _mm_set1_epi16((short)(rem - 1))));
  u32 j = (u32)__builtin_ctz(msk) >> 1;
  u16 buf[8];
  _mm_storeu_si128((__m128i *)buf, _mm_slli_si128(inc, 2));
  *sub = (u32)buf[j];
  return j;
}
// kth_alive + the deletion in ONE function: the deletion's (word, block, group, super)
// indices are EXACTLY the ones the select already produced, so big_del's four SERIAL shifts
// (w=p>>6, b=w>>3, g=b>>3, s=g>>3) are re-derivations of values already in registers -- and
// they sat on the critical path of a chain that runs once per query.  Every call site deleted
// the element immediately after selecting it, so the two are fused here.
static inline u32 kth_alive_del(u64 *del, u8 *wc, u16 *bc, u16 *gs, u16 *sg, u32 k) {
  u32 rem = k, s = 0;
  while (rem > (u32)sg[s]) { rem -= sg[s]; s++; }
  u32 sub;
  u32 jg = sel8(gs + (s << 3), rem, &sub); rem -= sub;
  u32 g = (s << 3) + jg;
  u32 jb = sel8(bc + (g << 3), rem, &sub); rem -= sub;
  u32 b = (g << 3) + jb;
  u32 sub2;
  u32 wi = sel8w(wc + (b << 3), rem, &sub2); rem -= sub2;
  u32 w = (b << 3) + wi;
  u64 m = ~del[w];
  u64 r; __asm__("pdep %2, %1, %0" : "=r"(r) : "r"(1ULL << (rem - 1)), "r"(m));
  u32 bit = (u32)__builtin_ctzll(r);
  del[w] |= 1ULL << bit;
  wc[w]++; bc[b]--; gs[g]--; sg[s]--;
  return ((b << 9) + (wi << 6)) + bit + 1;
}
static inline u32 kth_alive(const u64 *del, const u8 *wc, const u16 *bc, const u16 *gs, const u16 *sg, u32 k) {
  u32 rem = k, s = 0;
  while (rem > (u32)sg[s]) { rem -= sg[s]; s++; }
  u32 sub;
  u32 jg = sel8(gs + (s << 3), rem, &sub); rem -= sub;
  u32 g = (s << 3) + jg;
  u32 jb = sel8(bc + (g << 3), rem, &sub); rem -= sub;
  u32 b = (g << 3) + jb;
  u32 sub2;
  u32 wi = sel8w(wc + (b << 3), rem, &sub2); rem -= sub2;
  u32 base = (b << 9) + (wi << 6);
  u64 m = ~del[(b << 3) + wi];
  u64 r; __asm__("pdep %2, %1, %0" : "=r"(r) : "r"(1ULL << (rem - 1)), "r"(m));
  return base + (u32)__builtin_ctzll(r) + 1;
}
static inline void big_del(u64 *del, u8 *wc, u16 *bc, u16 *gs, u16 *sg, u32 p) {  // p 0-based
  u32 w = p >> 6;
  u32 b = w >> 3, g = b >> 3, s = g >> 3;
  del[w] |= 1ULL << (p & 63);
  wc[w]++; bc[b]--; gs[g]--; sg[s]--;
}
#define KA_OFF(NW, NBP, NGP, NSUP)                                       \
  ( ( (((NW)+1) & ~1UL)                                                 \
    + ((((NW)<<3)+7) & ~7UL) )                                           \
    + (((NBP)<<1)+1 & ~1UL) + (((NGP)<<1)+1 & ~1UL) + (((NSUP)<<1)+7 & ~7UL) )
static inline unsigned long ka_need(u32 V) {
  u32 nwords = (V + 63) >> 6;
  u32 nblk = (nwords + 7) >> 3;
  u32 ngrp = (nblk + 7) >> 3;
  u32 nsup = (ngrp + 7) >> 3;
  u32 nbp = ngrp << 3, ngp = nsup << 3;
  unsigned long need = ((unsigned long)nwords << 3) + nwords + 1;
  need = (need + 1) & ~1UL; need += (((unsigned long)nbp) << 1) + 2;
  need = (need + 1) & ~1UL; need += (((unsigned long)ngp) << 1) + 2;
  need = (need + 1) & ~1UL; need += (((unsigned long)nsup) << 1) + 2;
  return (need + 63) & ~(unsigned long)63;
}
static inline unsigned long big_init(u8 *mem, u32 V, u64 **pdel, u8 **pwc,
                                     u16 **pbc, u16 **pgs, u16 **psg) {
  u32 nwords = (V + 63) >> 6;
  u32 nblk = (nwords + 7) >> 3;
  u32 ngrp = (nblk + 7) >> 3;
  u32 nsup = (ngrp + 7) >> 3;
  u32 nbp = ngrp << 3, ngp = nsup << 3;
  unsigned long o1 = (((unsigned long)nwords << 3) + 1) & ~1UL;
  unsigned long o2 = (o1 + nwords + 1) & ~1UL;
  unsigned long o3 = (o2 + (((unsigned long)nbp) << 1) + 1) & ~1UL;
  unsigned long o4 = (o3 + (((unsigned long)ngp) << 1) + 1) & ~1UL;
  u64 *del = (u64 *)mem;
  u8  *wc  = (u8 *)(mem + o1);
  u16 *bc  = (u16 *)(mem + o2);
  u16 *gs  = (u16 *)(mem + o3);
  u16 *sg  = (u16 *)(mem + o4);
  for (u32 i = 0; i < nwords; i++) { del[i] = 0; wc[i] = 0; }
  u32 hi = V & 63;
  if (hi) { del[nwords - 1] = ~0ULL << hi; wc[nwords - 1] = (u8)(64 - hi); }
  for (u32 i = 0; i < nbp; i++) bc[i] = 0;
  for (u32 i = 0; i < ngp; i++) gs[i] = 0;
  for (u32 i = 0; i < nsup; i++) sg[i] = 0;
  for (u32 i = 0; i < nwords; i++) bc[i >> 3] += (u16)(64u - (u32)wc[i]);
  for (u32 i = 0; i < nblk; i++)  gs[i >> 3] += bc[i];
  for (u32 i = 0; i < ngrp; i++)  sg[i >> 3] += gs[i];
  *pdel = del; *pwc = wc; *pbc = bc; *pgs = gs; *psg = sg;
  return ka_need(V);
}

// small-row: sorted deleted array R[0..d); returns the position p, inserts it
static inline u32 small_remove(u32 *R, u32 d, u32 k) {
  u32 lo = 0, hi = d;
  while (lo < hi) {
    u32 mid = (lo + hi + 1) >> 1;
    if (R[mid - 1] - mid < k) lo = mid; else hi = mid - 1;
  }
  u32 p = k + lo;
  if (lo < d) {
    u32 *s = R + d, *e = R + lo;
    while (s > e) { *s = s[-1]; s--; }
  }
  R[lo] = p;
  return p;
}

// ------------------------- globals -------------------------
#define PN 300005
static u32 QX[PN], QY[PN];
// RCNT as u16 (0.6 MB instead of 1.2 MB): it is the only array written RANDOMLY by every
// query, so its dirty write-back volume and footprint are paid on the critical path.
// Counts >= 0xFFFF (<= ceil(q/65535) <= 5 rows for q <= 3e5) move to a tiny side list.
static u16 RCNT16[PN];
static u32 OVL[16], OVC[16], NOVF;
static inline void ovbump(u32 x) {
  for (u32 i = 0; i < NOVF; i++) if (OVL[i] == x) { OVC[i]++; return; }
  if (NOVF < 16u) { OVL[NOVF] = x; OVC[NOVF] = 0x10000u; NOVF++; }
}
static inline u32 ovget(u32 x) {
  for (u32 i = 0; i < NOVF; i++) if (OVL[i] == x) return OVC[i];
  return 0xFFFFu;
}
// RC[r] = off | (cnt << 20): the row's arena offset and its deletion count in ONE u32.
// Small-path cnt is <= ~392 (the cb<cs test needs (V/64+1)*2+55c >= c*(c/8)+30c with
// V=m-1+c, i.e. c^2/8 <= V/32+25c+2), so 12 bits is ample; big rows keep off/cnt in
// their BRec.  off <= q <= 3e5 fits in 20 bits.
#define RC_MASK 0xFFFFFu
static u32 RC[PN];
#define PB 65536
// ONE 2-bit-per-row classification instead of TWO separate 37.5 KB bitmaps.
// Phase 3 tests SIMPLE1 then BIGBMP, i.e. it performs TWO random bitmap loads per
// row-path query (the second on the ~63 % that are not SIMPLE1) to choose among
// three classes.  Encoding the class in 2 bits of the SAME word makes it ONE load.
//   0 = no row state  1 = SIMPLE1 (exactly one query)  2 = small path  3 = big path
// Same total bytes (300005*2 bits = 75 KB); fewer distinct lines touched per query.
#define SMBW ((PN + 31) / 32)
static u64 SM2[SMBW];
#define SM2SET(r, v) (SM2[(r) >> 5] |= (u64)(v) << (((r) & 31) << 1))
#define SM2GET(r)    ((u32)((SM2[(r) >> 5] >> (((r) & 31) << 1)) & 3ULL))
static u16 BIGID[PN];
struct BRec { u64 *del; u8 *wc; u16 *bc; u16 *gs; u16 *sg; u32 off; u32 cnt; u64 pad[2]; } __attribute__((aligned(64)));
static BRec BT[PB];
// SIMPLE1: rows with exactly ONE query (that one query is then provably p=y, no state).

static u32 NBIG;
static u64 RAPP[PN];
static u32 SMALLD[PN];
static u64 CAPP[PN];                 // fallback: only TOUCHED when n*m >= 2^40
static u8  CAPP5[PN * 5 + 8];         // 40-bit packed storage: 1.5 MB instead of 2.4 MB
static int CAPP5on;

#define ARENASZ (144u << 20)
static u8 ARENA[ARENASZ];

static u64 *CDEL; static u8 *CWC; static u16 *CBC; static u16 *CGS; static u16 *CSG;

static void solve() {
  PTICK();
  writer_init();
  u32 n = rd(), m = rd(), q = rd();
  u32 mm1 = m - 1;
  CAPP5on = ((u64)n * (u64)m < (1ULL << 40));
  // ---- phase 1 ----
  const u8 *gLim = gip + gSN;
  for (u32 i = 0; i < q; i++) {
    u32 x, y;
    if (gip + 16 <= gLim && winparse(&x, &y)) {
      /* windowed: one 16-byte load gives BOTH values and the line length */
    } else { x = rd(); y = rd(); }
    QX[i] = x; QY[i] = y;
    if (y < m) { u32 v = RCNT16[x]; if (v != 0xFFFFu) RCNT16[x] = (u16)(v + 1); else ovbump(x); }
  }
  PTICK();
  // ---- phase 2 ----
  NBIG = 0;
  u32 off = 0;
  u32 RR_off = 0;
  unsigned long asz = 0;
  for (u32 r = 1; r <= n; r++) {
    u32 c = RCNT16[r]; if (c == 0xFFFFu) c = ovget(r);
    if (!c) continue;
    if (c == 1) { SM2SET(r, 1u); continue; }
    SM2SET(r, 2u);
    RC[r] = off;
    RR_off = off;
    off += c;
    u64 V = (u64)mm1 + c;
    i64 cs = (i64)c * ((i64)(c >> 3) + 30);
    i64 cb = (i64)((V >> 6) + 1) * 2 + (i64)c * 55;
    if (cb < cs) {
      u32 nw = (u32)((V + 63) >> 6);
      u32 nb = (nw + 7) >> 3;
      unsigned long need = ka_need((u32)V); (void)nw; (void)nb;
      if (asz + need <= ARENASZ - (1u << 20)) {
        u64 *pdel; u8 *pwc; u16 *pbc; u16 *pgs; u16 *psg;
        big_init(ARENA + asz, (u32)V, &pdel, &pwc, &pbc, &pgs, &psg);
        u32 bi = NBIG++;
        if (bi < PB) { BT[bi].del=pdel; BT[bi].wc=pwc; BT[bi].bc=pbc; BT[bi].gs=pgs; BT[bi].sg=psg; BT[bi].off=RR_off; BT[bi].cnt=0; BIGID[r]=(u16)bi; }
        SM2SET(r, 1u);              // 2 | 1 = 3 : big row
        asz += need;
        continue;
      }
    }
  }
  PTICK();
  // ---- column ----
  {
    u64 *pdel; u8 *pwc; u16 *pbc; u16 *pgs; u16 *psg;
    unsigned long need = big_init(ARENA + asz, n + q, &pdel, &pwc, &pbc, &pgs, &psg);
    asz += need;
    CDEL = pdel; CWC = pwc; CBC = pbc; CGS = pgs; CSG = psg;
  }
  PTICK();
  // ---- phase 3 ----
  u32 cappn = 0;
  u8 *o = gob;
  for (u32 i = 0; i < q; i++) {
    u32 x = QX[i], y = QY[i];
    if (y < m) { __builtin_prefetch(&RC[x], 0, 3); __builtin_prefetch(&SM2[x >> 5], 0, 3); }
    u32 pc = kth_alive_del(CDEL, CWC, CBC, CGS, CSG, x);
    u64 cval;
    if (pc <= n) cval = (u64)pc * m;
    else {
      u32 jj = pc - n - 1;
      if (CAPP5on) { u32 lo_; __builtin_memcpy(&lo_, CAPP5 + (size_t)jj * 5, 4);
                     cval = (u64)lo_ | ((u64)CAPP5[(size_t)jj * 5 + 4] << 32); }
      else cval = CAPP[jj];
    }
    /* deletion fused into kth_alive_del */
    u64 val;
    if (y < m) {
      u32 r = x;
      u32 rcls = SM2GET(r);
      if (rcls == 1u) {
        val = (u64)(r - 1) * m + y;          // exact: the row's first and only query
      } else if (rcls == 3u) {
        BRec *bp = &BT[BIGID[r]];
        u64 *pdel = bp->del; u8 *pwc = bp->wc; u16 *pbc = bp->bc; u16 *pgs = bp->gs; u16 *psg = bp->sg;
        u32 bof = bp->off, bcn = bp->cnt;
        u32 pp = kth_alive_del(pdel, pwc, pbc, pgs, psg, y);
        val = (pp <= mm1) ? ((u64)(r - 1) * m + pp) : RAPP[bof + (pp - m)];
        /* deletion fused into kth_alive_del */
        RAPP[bof + bcn] = cval;
        bp->cnt = bcn + 1;
      } else {
        u32 rc = RC[r];
        u32 of = rc & RC_MASK;
        u32 cn = rc >> 20;
        u32 *R = SMALLD + of;
        u32 pp = small_remove(R, cn, y);
        val = (pp <= mm1) ? ((u64)(r - 1) * m + pp) : RAPP[of + (pp - m)];
        RAPP[of + cn] = cval;
        RC[r] = rc + (1u << 20);
      }
      { size_t o_ = (size_t)cappn * 5;
        if (CAPP5on) { u32 lo_ = (u32)val; __builtin_memcpy(CAPP5 + o_, &lo_, 4); CAPP5[o_ + 4] = (u8)(val >> 32); }
        else CAPP[cappn] = val; }
      cappn++;
    } else {
      val = cval;
      { size_t o_ = (size_t)cappn * 5;
        if (CAPP5on) { u32 lo_ = (u32)val; __builtin_memcpy(CAPP5 + o_, &lo_, 4); CAPP5[o_ + 4] = (u8)(val >> 32); }
        else CAPP[cappn] = val; }
      cappn++;
    }
    o = (i + 1 == q) ? wr_safe(o, val) : wr(o, val);
  }
  PTICK();
  gob = o;
  PTICK();
}

struct DUCKDI{unsigned long abi;const char*sp;unsigned long sn;char*op;unsigned long ol,os;char*ep;unsigned long el,es;const char*IB;unsigned long IBl;char*OB;unsigned long OBl;unsigned long tsc;}__attribute__((packed));
extern "C" void __libc_start_main(void*m,int argc,char**argv){
 unsigned long*p=(unsigned long*)(argv+argc+1);while(*p)p++;p++;
 DUCKDI*d=0;for(;p[0];p+=2)if(p[0]==0x6b637564UL){d=(DUCKDI*)p[1];break;}
 gip=(const u8*)d->sp; gob=(u8*)d->op; gSN=(unsigned)d->sn;
 solve();
 d->os=(unsigned long)(gob-(u8*)d->op);
 __asm__ volatile("syscall"::"a"(60),"D"(0):"rcx","r11","memory");
 for(;;);
}
int main(){return 0;}

评测结果