The chicken population at a local farm has spiralled out of control, and you are in charge of taking care of it. You may produce one type of food that is characterised by the number of proteins, vitamins and sugars.
For each of the $1 <= N <= 10^5$ chicken, you know one relation for each of the components of the food such that the chicken survives. For each one of the $3$, you receive an information of type $[ a, b ]$ ($2 <= a <= b <= 10^4$) which means the chicken will survive if the food provided has a value $k$ of the said component, with $a <= k <= b$.
Besides this, the owner of the farm also gives you $1 <= K <= 10^5$ constraints. These can be of $4$ types:
- $1$ $a$ $b$ means at least one of the chickens $a$ and $b$ should survive.
- $2$ $a$ $b$ means at least one of the chickens $a$ and $b$ should not survive.
- $3$ $a$ $b$ means chicken $a$ and $b$ are entangled, so they should both either survive or not.
- $4$ $a$ $b$ means chicken $a$ and $b$ are opposite, meaning one should survive and one shouldn't.
After feeding them the food, you may also pick some chicken to eat for dinner if they survived.
You should find a type of food and a configuration for the dinner that satisfy all of the constraints, or tell that it is impossible to do so.
The first line contains then number $N$ of chicken. The following $3 * N$ lines contain the description of the chicken.
For each chicken, the $3$ lines will contain two integers which correspond to the relation of that chicken to proteins, vitamins and sugars respectively.
The next line will contain the number $K$ of constraints. Each of the next $K$ lines will contain 3 integers, describing one of constraints.
In case there is no solution, you should output one line containing the integer $-1$.
Otherwise, the first line of the output file should contain $3$ integers $1 <= P <= 10^9$, $1 <= V <= 10^9$ and $1 <= S <= 10^9$, the characteristics of the food.
The second line should contain the integer $D$. Following that there should be a line with $D$ integers, the chicken you will use for dinner.
In case there are multiple correct solutions, you may output any of them.
## Input
The first line contains then number $N$ of chicken. The following $3 * N$ lines contain the description of the chicken.For each chicken, the $3$ lines will contain two integers which correspond to the relation of that chicken to proteins, vitamins and sugars respectively.The next line will contain the number $K$ of constraints. Each of the next $K$ lines will contain 3 integers, describing one of constraints.
## Output
In case there is no solution, you should output one line containing the integer $-1$.Otherwise, the first line of the output file should contain $3$ integers $1 <= P <= 10^9$, $1 <= V <= 10^9$ and $1 <= S <= 10^9$, the characteristics of the food.The second line should contain the integer $D$. Following that there should be a line with $D$ integers, the chicken you will use for dinner.In case there are multiple correct solutions, you may output any of them.
[samples]
**Definitions**
Let $ n \in \mathbb{Z} $ be the number of points, $ k \in \mathbb{Z} $ the target rank.
Let $ P = \{ (x_i, y_i) \mid i \in \{1, \dots, n\} \} $ be a set of $ n $ distinct points in $ \mathbb{R}^2 $.
**Constraints**
1. $ 2 \leq n \leq 100000 $
2. $ 1 \leq k \leq \binom{n}{2} $
3. $ -10^8 \leq x_i, y_i \leq 10^8 $ for all $ i \in \{1, \dots, n\} $
4. All points in $ P $ are pairwise distinct.
**Objective**
Let $ D = \left\{ |x_i - x_j| + |y_i - y_j| \mid 1 \leq i < j \leq n \right\} $ be the multiset of Manhattan distances between all unordered pairs of points.
Output the $ k $-th smallest element in $ D $, when sorted in non-decreasing order.