Ən böyük zəncir
İki üçlük a = (x_a, y_a, z_a) və b = (x_b, y_b, z_b) arasında qismən sıralamanı belə müəyyən edək:
a ≺ b əgər x_a < x_b, y_a < y_b və z_a < z_b olarsa.
Verilmiş üçlüklər dəstindən ən uzun artan ardıcıllığı tapmaq lazımdır: a_1 ≺ a_2 ≺ ... ≺ a_k.
Giriş verilənləri
Bir neçə testdən ibarətdir, hər biri aşağıdakı formatda üçlüklər dəstini ehtiva edir.
m n A B
x_1 y_1 z_1
x_2 y_2 z_2
...
x_m y_m z_m
Birinci sətir m, n, A və B dəyərlərini ehtiva edir. Bütün x_i, y_i və z_i (i = 1, ..., m) dəyərləri qeyri-mənfi tam ədədlərdir.
Hər bir test m + n üçlükdən ibarət çoxluq ehtiva edir. p_1 -dən p_m-ə qədər üçlüklər açıq şəkildə verilir, i-ci üçlük p_i (x_i, y_i, z_i) bərabərdir. Qalan n üçlüklər A və B parametrləri ilə verilir və aşağıdakı prosedur vasitəsilə yaradılır.
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;
}
3n dəfə r() çağırılır, hər biri x_{m+1}, y_{m+1}, z_{m+1}, x_{m+2}, y_{m+2}, z_{m+2}, ..., x_{m+n}, y_{m+n} və z_{m+n} ədədlərini göstərilən qaydada yaradır.
Qəbul edin ki, 1 ≤ m + n ≤ 3×10^5, 1 ≤ A, B ≤ 2^16 və 0 ≤ x_k, y_k, z_k < 10^6 üçün 1 ≤ k ≤ m + n.
Sonuncu sətir dörd sıfır ehtiva edir. Bütün testlər üçün ümumi m + n cəmi 2×10^6-dan çox deyil.
Çıxış verilənləri
Hər bir test üçün verilmiş çoxluqdan ən uzun artan ardıcıllığın uzunluğunu çıxarın. Əgər p_i1 ≺ p_i2 ≺ ... ≺ p_ik ən uzundursa, cavab k-ya bərabərdir.