406802: GYM102562 C Chicken Invasion

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 \leq N \leq 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 \leq a \leq b \leq 10^4$$$) which means the chicken will survive if the food provided has a value $$$k$$$ of the said component, with $$$a \leq k \leq b$$$.

Besides this, the owner of the farm also gives you $$$1 \leq K \leq 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 \leq P \leq 10^9$$$, $$$1 \leq V \leq 10^9$$$ and $$$1 \leq S \leq 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.

4
2 5
2 5
2 5
5 10
5 10
5 10
5 5
5 5
5 5
5 5
5 5
5 5
4
2 1 2
4 1 2
1 3 4
3 3 4

5 5 5 
1
2

2
2 2
2 2
2 2
3 3
3 3
3 3
2
1 1 2
3 1 2

-1