|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|2 초||256 MB||9||4||4||44.444%|
A mathematician goes to the shop every day and brings a bag from it. The bags are nice and practical, so mathematician wants to keep them for future usage. He also wants to keep his bags in order: big bags with big bags and small bags with small bags.
The bag brought on the $i$-th day (we'll just call it bag $i$) occupies volume $a_i$ in folded state and volume $b_i$ in unfolded state (naturally, $a_i < b_i$). The bag $i$ fits into the bag $j$ if $a_i < b_j$. Mathematician thinks that bags $i$ and $j$ are equal (and should be kept together) if the bag $i$ fits into the bag $j$ and vice versa.
Unfortunately, sometimes it happens that there are three bags $i, j, k$ such that bags $i$ and $j$ are equal, and bags $j$ and $k$ are equal, but bags $i$ and $k$ are not! It scares mathematician very much because it contradicts with what he knows about the equality relation. If adding a new bag to his collection gives rise to a contradictory triple as described above, he throws the new bag out instead, otherwise he keeps it (and never throws it away afterwards).
Your task is to determine for each bag whether it was kept or thrown away.
The first line contains an integer $n$ --- the number of bags ($1 \le n \le 3 \cdot 10^5$).
The next $n$ lines describe the bags. The $i$-th of these lines contains two integers $a_i$ and $b_i$ --- sizes of the bag $i$ in folded and unfolded states respectively ($1 \le a_i < b_i \le 10^9$).
Print $n$ lines. The $i$-th line should contain the word "
KEPT" if the mathematician keeps the bag $i$, and "
THROWN AWAY" otherwise.
10 1 4 3 5 6 8 7 9 1 2 6 7 4 7 5 7 5 8 9 10
KEPT KEPT KEPT KEPT THROWN AWAY THROWN AWAY THROWN AWAY THROWN AWAY KEPT KEPT