가장 긴 사슬

정수 세 개로 이루어진 삼중항 $a = (x_a, y_a, z_a)$와 $b = (x_b, y_b, z_b)$ 사이에 부분 순서 $\prec$를 다음과 같이 정한다.

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

세 좌표가 모두 커져야 $a \prec b$가 성립한다.

삼중항 집합이 주어진다. 그 안에서 $a_1 \prec a_2 \prec \cdots \prec a_k$를 만족하는 가장 긴 사슬을 찾아라.

입력은 데이터 집합 여러 개로 이루어진다. 데이터 집합 하나의 형식은 다음과 같다.

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

첫 줄의 $m$, $n$, $A$, $B$와 그 뒤 $m$개 줄에 적힌 $x_i$, $y_i$, $z_i$는 모두 음이 아닌 정수다.

데이터 집합 하나는 삼중항 $m + n$개를 정한다. 그중 $p_1$부터 $p_m$까지는 입력에 직접 적혀 있고, $i$번째 삼중항 $p_i$는 $(x_i, y_i, z_i)$다. 남은 $n$개는 아래 생성기에 $A$와 $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;
}

이 코드의 연산은 모두 32비트 부호 있는 정수로 이루어진다. 곱셈이나 덧셈 결과가 32비트 범위를 넘으면 2의 보수로 순환하고, >>는 부호를 유지하는 산술 시프트다.

r()을 $3n$번 연달아 호출하면 반환값이 순서대로 $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}$이 된다.

$1 \le m + n \le 3 \times 10^5$이고 $1 \le A, B \le 2^{16}$이다. $1 \le k \le m + n$인 모든 $k$에 대해 $0 \le x_k, y_k, z_k < 10^6$이다.

입력의 마지막 줄에는 0이 네 개 있다. 모든 데이터 집합의 $m + n$을 더한 값은 $2 \times 10^6$을 넘지 않는다.

데이터 집합마다 가장 긴 사슬의 길이를 한 줄에 하나씩 출력한다. $p_{i_1} \prec p_{i_2} \prec \cdots \prec p_{i_k}$가 가장 길면 답은 $k$다.