Store
Contest: Codeforces Round 499 (Div. 1)
Difficulty rating: 2700
Tags: data structures

Natasha was already going to fly back to Earth when she remembered that she needs to go to the Martian store to buy Martian souvenirs for her friends.

It is known, that the Martian year lasts $$$x_{max}$$$ months, month lasts $$$y_{max}$$$ days, day lasts $$$z_{max}$$$ seconds. Natasha also knows that this store works according to the following schedule: 2 months in a year were selected: $$$x_l$$$ and $$$x_r$$$ ($$$1\le x_l\le x_r\le x_{max}$$$), 2 days in a month: $$$y_l$$$ and $$$y_r$$$ ($$$1\le y_l\le y_r\le y_{max}$$$) and 2 seconds in a day: $$$z_l$$$ and $$$z_r$$$ ($$$1\le z_l\le z_r\le z_{max}$$$). The store works at all such moments (month $$$x$$$, day $$$y$$$, second $$$z$$$), when simultaneously $$$x_l\le x\le x_r$$$, $$$y_l\le y\le y_r$$$ and $$$z_l\le z\le z_r$$$.

Unfortunately, Natasha does not know the numbers $$$x_l,x_r,y_l,y_r,z_l,z_r$$$.

One Martian told Natasha: "I went to this store $$$(n+m)$$$ times. $$$n$$$ times of them it was opened, and $$$m$$$ times — closed." He also described his every trip to the store: the month, day, second of the trip and whether the store was open or closed at that moment.

Natasha can go to the store $$$k$$$ times. For each of them, determine whether the store at the time of the trip is open, closed, or this information is unknown.

Input format:
The first line contains $$$6$$$ integers $$$x_{max}$$$, $$$y_{max}$$$, $$$z_{max}$$$, $$$n$$$, $$$m$$$, $$$k$$$ ($$$1\le x_{max},y_{max},z_{max}\le 10^5$$$, $$$1\le n\le 10^5$$$, $$$0\le m\le 10^5$$$, $$$1\le k\le 10^5$$$) — number of months in a year, days in a month, seconds in a day, times when the store (according to a Martian) was opened, when it was closed and Natasha's queries.

The $$$i$$$-th of the next $$$n$$$ lines contains $$$3$$$ integers $$$x_i$$$, $$$y_i$$$, $$$z_i$$$ ($$$1\le x_i\le x_{max}$$$, $$$1\le y_i\le y_{max}$$$, $$$1\le z_i\le z_{max}$$$) — month, day and second of $$$i$$$-th time, when the store, according to the Martian, was opened.

The $$$i$$$-th of the next $$$m$$$ lines contains $$$3$$$ integers $$$x_i$$$, $$$y_i$$$, $$$z_i$$$ ($$$1\le x_i\le x_{max}$$$, $$$1\le y_i\le y_{max}$$$, $$$1\le z_i\le z_{max}$$$) — month, day and second of $$$i$$$-th time, when the store, according to the Martian, was closed.

The $$$i$$$-th of the next $$$k$$$ lines contains $$$3$$$ integers $$$x_i$$$, $$$y_i$$$, $$$z_i$$$ ($$$1\le x_i\le x_{max}$$$, $$$1\le y_i\le y_{max}$$$, $$$1\le z_i\le z_{max}$$$) — month, day and second of $$$i$$$-th Natasha's query.

Output format:
If the Martian was mistaken and his information about when the store is open and when it is closed is inconsistent, print a single line "INCORRECT" (without quotes).

Otherwise, print the first line "CORRECT" (without quotes). Next output $$$k$$$ lines: in $$$i$$$-th of them, output an answer to $$$i$$$-th Natasha's query: "OPEN" (without quotes), if the store was opened at the moment of this query, "CLOSED" (without quotes), if it was closed, or "UNKNOWN" (without quotes), if this information can not be determined on the basis of available data.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
Consider the first test case.

There are $$$10$$$ months in a year, $$$10$$$ days in a month, and $$$10$$$ seconds in a day.

The store was opened in $$$3$$$ moments:

- month $$$2$$$, day $$$6$$$, second $$$2$$$;
- month $$$4$$$, day $$$2$$$, second $$$4$$$;
- month $$$6$$$, day $$$4$$$, second $$$6$$$.

The store was closed at the time: month $$$9$$$, day $$$9$$$, second $$$9$$$.

Queries:

- month $$$3$$$, day $$$3$$$, second $$$3$$$ — open ("OPEN") (since the store opens no later than month $$$2$$$, day $$$2$$$, second $$$2$$$ and closes no earlier than in month $$$6$$$, day $$$6$$$, second $$$6$$$);
- month $$$10$$$, day $$$10$$$, second $$$10$$$ — closed ("CLOSED") (since it is closed even in the month $$$9$$$, day $$$9$$$, second $$$9$$$);
- month $$$8$$$, day $$$8$$$, second $$$8$$$ — unknown ("UNKNOWN") (because the schedule in which the store is open at this moment exists, and the schedule in which the store is closed at this moment exists as well).

In the second test case, the store was closed and opened at the same time — contradiction ("INCORRECT").

Example input:
10 10 10 3 1 3
2 6 2
4 2 4
6 4 6
9 9 9
3 3 3
10 10 10
8 8 8

Example output:
CORRECT
OPEN
CLOSED
UNKNOWN

Example input:
10 10 10 1 1 1
2 5 7
2 5 7
8 9 10

Example output:
INCORRECT

Editorial:
Consider $$$2$$$ options:
• $$$m=0$$$. This means that Natasha does not know about any moment when the store was closed. Let's find the numbers $$$x_l=min(x_i)$$$, $$$x_r=max(x_i)$$$, $$$y_l=min(y_i)$$$, $$$y_r=max(y_i)$$$, $$$z_l=min(z_i)$$$, $$$z_r=max(z_i)$$$, where $$$(x_i,y_i,z_i)$$$ are moments when store is open. For each query $$$(x_t,y_t,z_t)$$$ answer "OPEN", if $$$x_l\le x_t\le x_r$$$, $$$y_l\le y_t\le y_r$$$, and $$$z_l\le z_t\le z_r$$$. Answer "UNKNOWN" otherwise.
• $$$m\ne0$$$. Let's find the numbers $$$x_l=min(x_i)$$$, $$$x_r=max(x_i)$$$, $$$y_l=min(y_i)$$$, $$$y_r=max(y_i)$$$, $$$z_l=min(z_i)$$$, $$$z_r=max(z_i)$$$, where $$$(x_i,y_i,z_i)$$$ are moments when store is open. If there is at least one moment $$$(x_j,y_j,z_j)$$$, when the store is closed, and $$$x_l\le x_j\le x_r$$$, $$$y_l\le y_j\le y_r$$$ and $$$z_l\le z_j\le z_r$$$, then the answer is "INCORRECT". Otherwise, let's create a compressed two-dimensional segment tree. The first coordinate is number of the month in the year, the second coordinate is number of the day in a month. At each vertex of the tree of segments we store a pair of numbers — the greatest such number of a second $$$z$$$, when the store was closed, in this day of this month, that $$$z\le z_r$$$, and the smallest such number of a second $$$z$$$, when the store was closed, in this day of this month, that $$$z\ge z_l$$$. Now every query $$$(x_t,y_t,z_t)$$$ we will handle like this. If $$$x_l\le x_t\le x_r$$$, $$$y_l\le y_t\le y_r$$$ and $$$z_l\le z_t\le z_r$$$, answer "OPEN". Otherwise, consider the parallelepiped given by the coordinates of opposite vertices $$$(x_l,y_l,z_l)$$$ and $$$(x_r,y_r,z_r)$$$ and consider each vertex in turn $$$(x_p,y_p,z_p)$$$ the parallelepiped under consideration. Let's make the query in the segment tree $$$(x_p,x_t)$$$, $$$(y_p,y_t)$$$. Let the received answer is $$$(z_{first},z_{second})$$$. If the number $$$z_{first}$$$ or number $$$z_{second}$$$ is between numbers $$$z_p$$$ and $$$z_t$$$, this means that there is such a time point $$$(x_j,y_j,z_j)$$$, when the store is closed, that $$$x_j$$$ is between $$$x_p$$$ and $$$x_t$$$ (the month of the year when the store is closed, is between the month in the year when the store is open, and the month in the year in the query), $$$y_j$$$ is between $$$y_p$$$ and $$$y_t$$$ (the day in the month when the store is closed is between the day in the month when the store is open and the day in the month in the query), $$$z_j$$$ is between $$$z_p$$$ and $$$z_t$$$ (second in a day, when the store is closed, is between a second in a day, when the store is open and a second in a day in the query), hence the answer to the query is "CLOSED". If the condition is not satisfied for any vertex of the parallelepiped, the answer is "UNKNOWN".
Complexity: $$$O(n+m\log m+k\log^2m)$$$.