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\}$.