26405번 - Decent Sequence 스페셜 저지다국어

문제

The array $a$ is decent if it can be split into two consecutive parts (possibly empty), such that the first one (the prefix) is non-decreasing, and the second (the suffix) is non-increasing. For example, $[1, 2, 3],ドル $[1, 2, 2, 1]$ and $[3]$ are decent, while $[3, 2, 2, 8]$ is not.

There is an array $a$ consisting of $n$ integers, which is not given to you. You are, however, given $n$ integers $l_i$ and $n$ integers $r_i$. It is known that for all indices $i$ from 1ドル$ to $n$ we have $l_i \leq a_i \leq r_i$. Is $a$ decent?

You have to give one of the three answers:

1. $a$ is definitely decent.
2. $a$ is definitely not decent.
3. Neither of the above is the case.

입력

The first line contains a single integer $n$ (1ドル \leq n \leq 10^6$), the length of $a$.

Each of the following $n$ lines contains two integers $l_i$ and $r_i$ (1ドル \leq l_i \leq r_i \leq 10^9$) describing the range containing the element $a_i$.

출력

Output "TAK" (without quotes) if $a$ is definitely decent.

Output "NEIN" (without quotes) if $a$ is definitely not decent.

Output an arbitary string consisting of at least five but not more than 100 lowercase or capital english letters otherwise. If you output something really inappropriate you might get Presentation Error. Both of the possible answers in the samples are not considered inappropriate.

제한

힌트