我们定义两个三元组 $a = (x_a, y_a, z_a)$ 和 $b = (x_b, y_b, z_b)$ 之间的偏序关系 $\prec$ 如下： $$a \prec b \iff x_a < x_b \text{ 且 } y_a < y_b \text{ 且 } z_a < z_b$$ 你的任务是在给定的三元组集合中，找到最长的上升序列 $a_1 \prec a_2 \prec \dots \prec a_k$。

输入格式

输入包含一系列数据集，每个数据集描述了一组三元组，格式如下：

$m \ n \ A \ B$ $x_1 \ y_1 \ z_1$ $x_2 \ y_2 \ z_2$ $\vdots$ $x_m \ y_m \ z_m$

其中第一行的 $m, n, A, B$ 以及后续行中的所有 $x_i, y_i, z_i$ ($i = 1, \dots, m$) 均为非负整数。

每个数据集指定了 $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;
}

重复调用上述定义的 r() 函数 $3n$ 次，依次产生 $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}$ 的值。

你可以假设 $1 \le m + n \le 3 \times 10^5$，$1 \le A, B \le 2^{16}$，且对于 $1 \le k \le m + n$，满足 $0 \le x_k, y_k, z_k < 10^6$。

输入以一行包含四个零的数据结束。所有数据集的 $m + n$ 总和不超过 $2 \times 10^6$。

输出格式

对于每个数据集，输出指定集合中最长上升三元组序列的长度。如果 $p_{i_1} \prec p_{i_2} \prec \dots \prec p_{i_k}$ 是最长的，则答案应为 $k$。

样例

样例输入 1

6 0 1 1
0 0 0
0 2 2
1 1 1
2 0 2
2 2 0
2 2 2
5 0 1 1
0 0 0
1 1 1
2 2 2
3 3 3
4 4 4
10 0 1 1
3 0 0
2 1 0
2 0 1
1 2 0
1 1 1
1 0 2
0 3 0
0 2 1
0 1 2
0 0 3
0 10 1 1
0 0 0 0

样例输出 1

3
5
1
3