Description
Elfnt and his family (a total of elephants) are claiming their own territories. We can represent the land as a 1D coordinate line. Each elephant chooses a continuous segment as its territory, starting from position to (inclusive interval ).
An elephant A's territory completely contains elephant B's territory if and .
Your task is to analyze the overlapping territories. For each elephant, determine if its territory contains at least one other elephant's territory, and if its territory is contained by at least one other elephant's territory.
Input
The first line contains a single integer — the number of elephants.
The following lines each contain two integers and , representing the starting and ending points of an elephant's territory.
(Note: The elephants are numbered from to in the order they appear in the input).
Constraints
- All given territories are guaranteed to be distinct.
Output
The first line should contain integers. The -th integer should be 1 if the -th elephant's territory completely contains at least one other territory, and 0 otherwise.
The second line should contain integers. The -th integer should be 1 if the -th elephant's territory is completely contained by at least one other territory, and 0 otherwise.
For both lines, consecutive integers must be separated by a space. There must be no space after the last integer of each line, and each line must end with a newline.