Longest Chain#6784

Longest Chain

60 seconds

256 megabytes

Very easy

Let us define a partial order $≺$ on triples $a = (x_{a}, y_{a}, z_{a})$ \mathbf{a} = (x_a, y_a, z_a) and $b = (x_{b}, y_{b}, z_{b})$ \mathbf{b} = (x_b, y_b, z_b) as follows:

$a ≺ b$ \mathbf{a} \prec \mathbf{b} if $x_{a} < x_{b}$ x_a < x_b, $y_{a} < y_{b}$ y_a < y_b, and $z_{a} < z_{b}$ z_a < z_b.

Given a set of triples, find the length of the longest strictly increasing sequence of triples $a_{1} ≺ a_{2} ≺ \dots ≺ a_{k}$ \mathbf{a}_1 \prec \mathbf{a}_2 \prec \dotsb \prec \mathbf{a}_k.

Input

The input consists of several datasets. Each dataset describes a set of triples in the following format:

$m n A B$ m~n~A~B
$x_{1} y_{1} z_{1}$ x_1~y_1~z_1
$x_{2} y_{2} z_{2}$ x_2~y_2~z_2
$⋮$
$x_{m} y_{m} z_{m}$ x_m~y_m~z_m

The first line contains four integers: $m$ , $n$ , $A$ , $B$ . All values $x_{i}$ x_i, $y_{i}$ y_i, $z_{i}$ z_i ( $1 \leq i \leq m$ 1 \le i \le m) are non-negative integers.

Each dataset contains $m + n$ m + n triples. The first $m$ triples, $p_{1}$ \mathbf{p}_1 through $p_{m}$ \mathbf{p}_m, are given explicitly ( $p_{i} = (x_{i}, y_{i}, z_{i})$ \mathbf{p}_i = (x_i, y_i, z_i)). The remaining $n$ triples are generated as follows, using 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;
}

Call $r ()$ a total of $3 n$ times to generate, in order:

x_{m + 1}, y_{m + 1}, z_{m + 1}, x_{m + 2}, y_{m + 2}, z_{m + 2}, \dots, x_{m + n}, y_{m + n}, z_{m + n} .

x_{m+1},~y_{m+1},~z_{m+1},~x_{m+2},~y_{m+2},~z_{m+2},~\dotsc,~x_{m+n},~y_{m+n},~z_{m+n}.

You may assume:

1 \leq m + n \leq 3 \times 1 0^{5}, 1 \leq A, B \leq 2^{16}, 0 \leq x_{k}, y_{k}, z_{k} < 1 0^{6} for 1 \leq k \leq m + n .

1 \le m+n \le 3 \times 10^5,\\ 1 \le A,~B \le 2^{16},\\ 0 \le x_k,~y_k,~z_k < 10^6\quad \text{for}\ 1 \le k \le m+n.

The input ends with a line containing four zeros.

The total sum of $m + n$ m+n over all datasets does not exceed $2 \times 1 0^{6}$ 2 \times 10^6.

Output

For each dataset, output the length $k$ of the longest strictly increasing sequence of triples in the given set—that is, the largest $k$ such that $p_{i_{1}} ≺ p_{i_{2}} ≺ \dots ≺ p_{i_{k}}$ \mathbf{p}_{i_1} \prec \mathbf{p}_{i_2} \prec \dotsb \prec \mathbf{p}_{i_k}.

Examples

Example 1