Forklift Removal Order

Farmer John is training to become forklift certified! He must remove \(N\) boxes from an old warehouse. Each box \(i\) is given as an axis-aligned rectangle with its southwest corner at \((x_{i1}, y_{i1})\) and its northeast corner at \((x_{i2}, y_{i2})\). The coordinates satisfy \(1 \le x_{i1} < x_{i2} \le 2N\) and \(1 \le y_{i1} < y_{i2} \le 2N\). Moreover, no two boxes intersect and no two corners from different boxes share the same \(x\) or \(y\) coordinate.

Farmer John can only remove a box \(i\) if there is no other remaining box whose southwest corner \((x_{j1}, y_{j1})\) satisfies \[ x_{j1} < x_{i2}\quad\text{and}\quad y_{j1} < y_{i2}, \] that is, no part of any other box lies both south and west of box \(i\)'s northeast corner.

Your program should work in one of two modes determined by an integer flag \(M\):

• Mode 1 (\(M = 1\)): Output any valid permutation of \(1, \dots, N\) representing a valid order in which the boxes may be removed.
• Mode 2 (\(M = 2\)): For each \(k = 1, \dots, N\), output \(1\) if box \(k\) can be removed immediately (when boxes \(1, \dots, k-1\) have already been removed) and \(0\) otherwise.

inputFormat

The first line contains two integers \(M\) and \(N\) (with \(1 \le N \le 10^5\)). Each of the following \(N\) lines contains four integers: \(x_{i1}\), \(y_{i1}\), \(x_{i2}\), \(y_{i2}\), describing the southwest and northeast corners of box \(i\). It is guaranteed that \(1 \le x_{i1} < x_{i2} \le 2N\) and \(1 \le y_{i1} < y_{i2} \le 2N\), the boxes have positive area, no two boxes intersect, and no two boxes share the same \(x\) or \(y\) coordinate among their corners.

outputFormat

If \(M = 1\), output a permutation of \(1, \dots, N\) (separated by spaces or newlines) representing a valid removal order of the boxes. If \(M = 2\), output \(N\) numbers (each either \(1\) or \(0\), separated by spaces or newlines): for each \(k = 1, \dots, N\), output \(1\) if box \(k\) can be removed immediately after boxes \(1, \dots, k-1\) have been removed, and \(0\) otherwise.

sample

1 4
1 1 3 3
4 1 6 3
1 4 3 6
4 4 6 6

1 2 3 4