Permutation and Set Symmetric Difference

You are given n distinct points \((x_i,y_i)\) for \(1 \le i \le n\) and m sets defined by:

\[ S_j = \{ (x_i,y_i) \mid A_j x_i + B_j y_i + C_j > 0 \}, \quad 1 \le j \le m. \]

Your task is to find a permutation \(p_1, p_2, \dots, p_m\) of \(\{1,2,\dots,m\}\) such that

\[ |S_{p_1}| + \sum_{i=2}^m \left| S_{p_i}\oplus S_{p_{i-1}} \right| \le M, \]

where \(M\) is a given constant, and for any two sets \(A\) and \(B\), the notation \(A\oplus B\) denotes their symmetric difference defined by

\[ A \oplus B = (A \cup B) \setminus (A \cap B). \]

If such a permutation exists, output any one of them (using 1-indexed positions). Otherwise, output -1.

inputFormat

The input begins with three integers n m M where

• n is the number of points.
• m is the number of sets.
• M is the given constant.

The next n lines each contain two integers xi yi representing the coordinates of each point.

Then, the next m lines each contain three integers Aj Bj Cj for \(1 \le j \le m\), which define the set \(S_j\) by the inequality \(A_j x_i + B_j y_i + C_j > 0\).

outputFormat

If a valid permutation exists, output a single line containing the permutation \(p_1, p_2, \dots, p_m\) (1-indexed) separated by spaces. If no valid permutation exists, output -1.

sample

3 2 10
0 0
1 1
2 2
1 1 -1
-1 1 0

1 2