Problem: Let us compare two triples a = (xa, ya, za) and b = (xb, yb, zb) by a partial order ∠ defined as follows.
a ∠ b ⇔ xa < xb and ya < yb and za < zb



Your mission is to find, in the given set of triples, the longest ascending series a1 ∠ a2 ∠ ... ∠ ak.



Input

The input is a sequence of datasets, each specifying a set of triples formatted as follows.


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


Here, m, n, A and B in the first line, and all of xi, yi and zi (i = 1, . . . , m) in the following lines are non-negative integers.

Each dataset specifies a set of m + n triples. The triples p1 through pm are explicitly specified in the dataset, the i-th triple pi being (xi, yi, zi). The remaining n triples are specified by parameters A and B given to the following generator routine.


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;
}


Repeated 3n calls of r() defined as above yield values of xm+1, ym+1, zm+1, xm+2, ym+2, zm+2, ..., xm+n, ym+n, and zm+n, in this order.

You can assume that 1 ≤ m + n ≤ 3 × 105, 1 ≤ A,B ≤ 216, and 0 ≤ xk, yk, zk < 106 for 1 ≤ k ≤ m + n.

The input ends with a line containing four zeros. The total of m + n for all the datasets does not exceed 2 × 106.

Output

For each dataset, output the length of the longest ascending series of triples in the specified set. If pi1 ∠ pi2 ∠ ... ∠ pik is the longest, the answer should be k.

Example

Input

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


Output

3
5
1
3

Solution (in CPP):

Solution:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define lowbit(x) ((x)&-(x))
using namespace std;

const int maxn = 300010, maxe = 1000010;
const int C = ~(1 << 31), M = (1 << 16) - 1;
struct node {int x, y, z;};
struct qry {int id, t, x, y, val;} q[maxe];
int f[maxe], g[maxn], ct[maxe];
node d[maxn];
int n, m, A, B, clk;

bool cmp(const node &a, const node &b)
{
    if (a.x != b.x) return a.x < b.x;
    if (a.y != b.y) return a.y > b.y;
    return a.z > b.z;
}

bool cmp1(const qry &a, const qry &b)
{
    if (a.x == b.x) return a.t > b.t;
    else return a.x < b.x;
}

void update(int u, int x)
{
    for (int i = u; i < maxe; i += lowbit(i))
        if (ct[i] != clk)
        {
            ct[i] = clk;
            f[i] = x;
        }
        else
            f[i] = max(x, f[i]);
}

int query(int u)
{
    int ans = 0;
    for (int i = u; i; i -= lowbit(i))
        if (ct[i] == clk)
            ans = max(ans, f[i]);
    return ans;
}

int r()
{
    A = 36969 * (A & M) + (A >> 16);
    B = 18000 * (B & M) + (B >> 16);
    return (C & ((A << 16) + B)) % 1000000;
}

void solve(int l, int r)
{
    if (l == r)
    {
        g[l] = max(1, g[l]);
        return;
    }
    int mid = (l + r) >> 1, cnt = 0;
    solve(l, mid);
    for (int i = l; i <= mid; ++i)
        q[cnt++] = (qry) {i, 0, d[i].y, d[i].z, g[i]};
    for (int i = mid + 1; i <= r; ++i)
        q[cnt++] = (qry) {i, 1, d[i].y, d[i].z, 0};
    sort(q, q + cnt, cmp1);
    ++clk;
    for (int i = 0; i < cnt; ++i)
    {
        if (!q[i].t) update(q[i].y, q[i].val);
        else g[q[i].id] = max(g[q[i].id], query(q[i].y - 1) + 1);
    }
    solve(mid + 1, r);
}

int main()
{
    ios::sync_with_stdio(false);
    while (cin >> n >> m >> A >> B && n + m)
    {
        for (int i = 1; i <= n; ++i)
            cin >> d[i].x >> d[i].y >> d[i].z;
        for (int i = n + 1; i <= n + m; ++i)
            d[i].x = r(), d[i].y = r(), d[i].z = r();
        for (int i = 1; i <= n + m; ++i)
            ++d[i].x, ++d[i].y, ++d[i].z;
        sort(d + 1, d + n + m + 1, cmp);
        memset(f, 0, sizeof(f));
        memset(g, 0, sizeof(g));
        memset(ct, 0, sizeof(ct));
        clk = 0;
        solve(1, n + m);
        cout << *max_element(g + 1, g + 1 + n + m) << endl;
    }
}