Problem:


Problem G: Longest Chain

Let us compare two triples a = (xa, ya, za) and b = (xb, yb, zb) by a partial order &ang; defined as follows.

a &ang; b &hArr; xa < xb and ya < yb and za < zb

Your mission is to find, in the given set of triples, the longest ascending series a1 &ang; a2 &ang; ...  &ang; 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> 16);
  b = 18000 * (b & M) + (b >> 16);
  return (C & ((a n 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 &times; 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 &times; 106.

Output

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

Sample 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 for the Sample Input

3
5
1
3



Sample 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


Sample output:
3
5
1
3

Submission status: Runtime Error

Solution code:
#Longest Chain: O(n^2)

def R(A, B):
    a, b = A, B
    C, M = ~(1 << 31), (1 << 16) - 1
    while True:
        a = 3696 * (a & M) + (a >> 16)
        b = 1800 * (b & M) + (b >> 16)
        yield (C & ((a << 16) + b)) % 1000000

def check(p1, p2):
    return all(map(lambda (x, y): x <= y, zip(p1, p2)))

def solve():
    dp = [1] * (m + n)
    for i in xrange(m + n):
        for j in xrange(i + 1,m + n):
            if check(L[i], L[j]):
                dp[j] = max(dp[j], dp[i] + 1)
    return max(dp)

while True:
    m, n, A, B = map(int, raw_input().split())
    if m | n | A | B == 0:
        break
    L = [map(int, raw_input().split()) for _ in xrange(m)]
    r = R(A, B)
    L += [(r.next(), r.next(), r.next()) for _ in xrange(n)]
    L.sort()
    print solve()

Submission status: Runtime Error

Solution code:
#Longest Chain: O(NlogN + ??)

def R(A, B):
    a, b = A, B
    C, M = ~(1 << 31), (1 << 16) - 1
    while True:
        a = 3696 * (a & M) + (a >> 16)
        b = 1800 * (b & M) + (b >> 16)
        yield (C & ((a << 16) + b)) % 1000000

def compare(a, b):
    return all(aa < bb for aa, bb in zip(a, b))

def upper_bound(data, a, comp):
    left, right = 0, len(data)
    while True:
        mid = (right + left) / 2        
        if not left < mid < right:
            return right
        if comp(data[mid], a):
            left = mid
        else:
            right = mid

def solve(L):
    A = [(0,0,0)]
    val = {A[0]: 0}
    count = 0
    for n in L:
        idx = upper_bound(A, n, compare)
        A.insert(idx, n)
        val[n] = val[A[idx - 1]] + 1
    return max(val.values())

while True:
    m, n, A, B = map(int, raw_input().split())
    if m | n | A | B == 0:
        break
    L = [tuple(map(int, raw_input().split())) for _ in xrange(m)]
    r = R(A, B)
    L += [(r.next(), r.next(), r.next()) for _ in xrange(n)]
    L.sort()
    print solve(L)