Longest Chain

Define a partial order $\prec$ on triples of integers $a = (x_a, y_a, z_a)$ and $b = (x_b, y_b, z_b)$ as follows.

$a \prec b \quad\Longleftrightarrow\quad x_a < x_b,\ y_a < y_b,\ z_a < z_b$

All three coordinates have to grow for $a \prec b$ to hold.

You are given a set of triples. Find the longest ascending series $a_1 \prec a_2 \prec \cdots \prec a_k$ in it.

The input is a sequence of datasets. One dataset has this format.

m n A B
x1 y1 z1
x2 y2 z2
...
xm ym zm

The values $m$, $n$, $A$, $B$ on the first line and every $x_i$, $y_i$, $z_i$ on the following $m$ lines are non-negative integers.

One dataset specifies $m + n$ triples. The triples $p_1$ through $p_m$ are written out in the dataset, and the $i$-th triple $p_i$ is $(x_i, y_i, z_i)$. The remaining $n$ triples come from the generator below, started with the parameters $A$ and $B$.

int a = A, b = B, C = ~(1<<31), M = (1<<16)-1;
int r() {
  a = 36969 * (a & M) + (a >> 16);
  b = 18000 * (b & M) + (b >> 16);
  return (C & ((a << 16) + b)) % 1000000;
}

Every operation in this code runs on 32-bit signed integers. Multiplication and addition wrap around in two's complement once the result leaves that range, and >> is an arithmetic shift that keeps the sign.

Calling r() $3n$ times in a row yields $x_{m+1}$, $y_{m+1}$, $z_{m+1}$, $x_{m+2}$, $y_{m+2}$, $z_{m+2}$, $\ldots$, $x_{m+n}$, $y_{m+n}$, $z_{m+n}$, in this order.

You can assume that $1 \le m + n \le 3 \times 10^5$ and $1 \le A, B \le 2^{16}$, and that $0 \le x_k, y_k, z_k < 10^6$ for every $k$ with $1 \le k \le m + n$.

The input ends with a line containing four zeros. The total of $m + n$ over all datasets does not exceed $2 \times 10^6$.

For each dataset, print the length of the longest ascending series of triples, one length per line. If $p_{i_1} \prec p_{i_2} \prec \cdots \prec p_{i_k}$ is the longest, the answer is $k$.