You are given three arrays \(a_{1 \dots n}, b_{1 \dots n}, c_{1 \dots n}\) and two numbers M and K. Find a lexicographically minimum \(\{x, y, z\}\) such that there are exactly K indices \(i(1 \le i \le n)\) where \(x*a_i+y*b_i-c_i*z = M*f\) for some integer \(f\). Also, you are given ranges of \(x\), \(y\), and \(z\)-- \(l_{1..3}, r_{1..3}\)(\((l_1 \le x \le r_1, l_2 \le y \le r_2, l_3 \le z \le r_3)\). Here, a triplet of integers \(\{x_1,y_1,z_1\}\) is considered to be lexicographically smaller than a triplet \(\{x_2,y_2,z_2\}\) if sequence \([x_1, y_1, z_1]\) is lexicographically smaller than sequence \([x_2, y_2, z_2]\). A sequence a is lexicographically smaller than a sequence b if in the first position where a and b differ, the sequence a has a smaller element than the corresponding element in b.

Input format

• The first line contains one three integers \(n, m, K (1 \le n \le 10000, 0 \le K \le n, 1 \le M \le 15)\).
• The next n lines contain three integers \(a_i, b_i, c_i (1 \le a_i, b_i, c_i \le 10^9)\).
• The next three lines contain two integers \(l_i, r_i (1 \le l_i \le r_i \le 10^9)\).

Output format

If an answer does not exist, print -1. Otherwise, print desirable \(\{x, y, z\}\).