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 <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;

#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcountll

#define INF 1e16
#define mod 1000000007

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

ll M,N;
ll x[300001],y[300001],z[300001];
ll ord[300001],Y[300001],Z[300001];

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);

  while(1){
    cin>>M>>N>>A>>B;
    if(M+N==0)break;
    rep(i,M){
      cin>>x[i]>>y[i]>>z[i];
      ord[i]=i;
    }
    rep(i,N){
      x[i+M]=r(); y[i+M]=r(); z[i+M]=r(); ord[i+M]=i+M;
    }
    N+=M;
    sort(ord,ord+N,[](const ll& a,const ll& b){
      if(x[a]==x[b]&&y[a]==y[b])return z[a] > z[b];
      else if(x[a]==x[b])return y[a] > y[b];
      else return x[a] < x[b];
    });
    rep(i,N){
      Y[i]=y[ord[i]];
      Z[i]=z[ord[i]];
    }

    vector<set<P> > st(N,set<P>());
    ll res=1;
    st[0].insert(P(Y[0],Z[0]));
    repl(i,1,N){
      ll lb=-1,ub=res;
      while(ub-lb>1){
        ll m=(lb+ub)/2;
        auto it=st[m].lower_bound(P(Y[i],-1));
        if(it!=st[m].begin()&&(--it)->se<Z[i])lb=m;
        else ub=m;
      }

      maxch(res,ub+1);

      auto it=st[ub].lower_bound(P(Y[i],-1));
      while(it!=st[ub].end()&&it->se>=Z[i])it=st[ub].erase(it);

      it=st[ub].lower_bound(P(Y[i],-1));
      if(st[ub].size()==0)st[ub].insert(P(Y[i],Z[i]));
      else if(it->fi!=Y[i]){
        st[ub].insert(P(Y[i],Z[i]));
      }
    }
    cout<<res<<endl;
  }

  return 0;
}