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>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

typedef pair<int,int> ii;

const int IINF = INT_MAX;

struct Point3d {
  int x,y,z;
  bool operator < ( const Point3d &p ) const {
    if( z != p.z ) return z < p.z;
    if( y != p.y ) return y > p.y;
    return x > p.x;
  }
};


int a, 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;
}


const int MAX = 300010;
int m,n,A,B;
Point3d ps[MAX];


set<ii> dp[MAX];

bool check(int index,ii v){
  set<ii>::iterator it = dp[index].lower_bound(v);
  while( (*it).second < v.second ){
    if( (*it).first < v.first ) return true;
    --it;
  }
  return false;
}

void update(int index,ii v){
  set<ii>::iterator it = dp[index].lower_bound(v);
  --it;
  if( (*it).second <= v.second ) return;
  ++it;
  while( (*it).second >= v.second ) dp[index].erase(it++);
  dp[index].insert(v);
}

int LIS2D(vector<ii> &vec) {
  rep(i,(int)vec.size()+1) {
    dp[i].clear();
    dp[i].insert(ii(-1,IINF));
    dp[i].insert(ii(IINF,-1));
  }
  dp[0].insert(ii(-1,-1));
  int maxi = 0;
  rep(i,(int)vec.size()){
    int low = 0, hig = i+1;
    while( hig - low ) {
      int mid = ( low + hig ) / 2;
      if( check(mid,vec[i]) ) low = mid + 1;
      else                    hig = mid;
    }
    maxi = max(maxi,low);
    update(low,vec[i]);
  }
  return maxi + 1;
}


void compute(){
  sort(ps,ps+n+m);
  vector<ii> vec;
  rep(i,n+m) vec.push_back(ii(ps[i].y,ps[i].x));
  cout << LIS2D(vec) << endl;
}

int main(){
  while( scanf("%d %d %d %d",&m,&n,&A,&B), m|n|A|B ){
    a = A, b = B;
    rep(i,m) scanf("%d %d %d",&ps[i].x,&ps[i].y,&ps[i].z);
    rep(i,n) {
      ps[m+i].x = r();
      ps[m+i].y = r();
      ps[m+i].z = r();
    }
    compute();
  }
  return 0;
}