Ba mảng số

Trong một ngày làm việc bình thường, FullHouse Dev được một người thợ mộc tìm đến nhờ giải quyết một bài toán thú vị. Người thợ mộc đang cần tính toán số liệu cho một dự án đồ gỗ và gặp khó khăn với ba dãy số. FullHouse Dev quyết định giúp đỡ người thợ mộc giải quyết bài toán này.

Bài toán

Cho ba mảng số và hai số \(M\) và \(K\). Hãy tìm một bộ ba số \(x, y, z\) có thứ tự từ điển nhỏ nhất sao cho có đúng \(K\) chỉ số \(i\) thỏa mãn \(x \cdot A[i] + y \cdot B[i] + z \cdot C[i] = M\) với một số nguyên nào đó. Các giá trị \(x\), \(y\), và \(z\) phải nằm trong các khoảng cho trước \([l_1, r_1]\), \([l_2, r_2]\), và \([l_3, r_3]\).

Một bộ ba số \((x_1, y_1, z_1)\) được coi là có thứ tự từ điển nhỏ hơn bộ ba số \((x_2, y_2, z_2)\) nếu tại vị trí đầu tiên mà hai bộ ba khác nhau, số trong bộ ba thứ nhất nhỏ hơn số tương ứng trong bộ ba thứ hai.

INPUT FORMAT:

• Dòng đầu tiên chứa ba số nguyên \(n\), \(M\), \(K\).
• \(n\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(A[i]\), \(B[i]\), \(C[i]\).
• Ba dòng cuối cùng, mỗi dòng chứa hai số nguyên \(l_i\), \(r_i\) thể hiện khoảng giá trị cho phép của \(x\), \(y\), \(z\).

OUTPUT FORMAT:

• Nếu không tồn tại đáp án, in ra -1.
• Ngược lại, in ra ba số \(x\), \(y\), \(z\) thỏa mãn yêu cầu.

Ví dụ

INPUT

4 3 4
5 6 1
2 6 9
11 5 6
1 1 1
1 10
1 10
1 10

OUTPUT

3 3 3

Giải thích

Với \(K = 4\), điều kiện phải thỏa mãn tại tất cả các chỉ số. Ta có thể kiểm tra rằng bộ ba số \((3, 3, 3)\) thỏa mãn yêu cầu của bài toán.