AMR12J  Escape from the Mines
It was after nightfall when they had entered the Mines. They had been going for several hours with only brief halts, when Gandalf came to his first serious check. Before him stood a wide dark arch opening into three passages: all led in the same general direction, eastwards; but the lefthand passage plunged down, while the righthand climbed up, and the middle way seemed to run on, smooth and level but very narrow.  The Fellowship of the Ring are lost in the Mines.
The Mines of Moria are a true testament of Dwarvish genius. And the Fellowship of the Ring are lost in the maze of rooms, halls and caverns. You have managed to acquire a copy of the blueprints, and if only you were part of the Fellowship, Gandalf need not have had to face the Balrog!
In this problem, we consider the Mines as consisting of rectangular rooms with their sides aligned parallel to the X (WestEast) and Y (SouthNorth) axes. Some rooms are situated within other rooms. The boundaries of any two rooms have no point in common. The rooms are numbered 0 to N1. Your task is to determine for each room i, which room would you enter if you exit room i. If you exit into the open, output 1.
For example, if the blueprints of the Mines looked like:

 
 
3

  
   
  []  
  2  
 1 
 
0
Then, you should determine that:
Room 0 exits into the open (1)
Room 1 exits into Room 0
Room 2 exits into Room 1
Room 3 exits into the open (1)
Input (STDIN):
The first line contains an integer N followed by N lines. The i'th line defines the coordinates of the i'th room in the mines: x1_i, y1_i, x2_i, y2_i, where (x1_i, y1_i) are the coordinates of the southwest corner and (x2_i, y2_i) are the coordinates of the northeast corner of the i'th room.
Output (STDOUT):
Output N lines, the i'th line containing the number of the room into which the i'th room exits. Output 1 if the i'th room exits into the open.
Constraints:
1 <= N <= 100,000
0 <= x1_i < x2_i <= 1,000,000,000
0 <= y1_i < y2_i <= 1,000,000,000
The borders of no two rooms have any point in common.
Sample Input:
4
0 0 10 10
2 3 7 8
3 4 5 6
12 10 13 15
Sample Output:
1
0
1
1
Notes/Explanation of Sample Input:
Given in the diagram.
hide comments
Varun Jalan:
20121222 12:00:02
I see. None of the problem setters were aware of this. 

[Rampage] Blue.Mary:
20121222 09:34:54
The same as SGU 319. 
Added by:  Varun Jalan 
Date:  20121222 
Time limit:  4s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Varun Jalan  ICPC Asia regionals, Amritapuri 2012 