Laser Mirror Trap Pairing

King Byteasar’s palace contains a special mirror‐trap room. The room is an orthogonal polygon – its consecutive sides are perpendicular and have integral lengths – with its entire interior walls covered in mirrors. In every corner one may install either a laser gun or a laser detector (but not both at the same corner). When a laser gun is installed at a corner, it fires a beam along the bisector of the angle formed by the two incident walls. Owing to the room’s architecture the bisector makes a 45° angle with the walls, so its direction is one of the four diagonal directions ( (1,1), (1,-1), (-1,1), (-1,-1) ). The beam travels in a straight line (since reflection off a mirror leaves the direction unchanged) until it reaches a corner. If it enters a corner where a detector is installed the beam is absorbed. However, if the beam reaches a corner that does not have a detector (even if a gun is there) it is reflected back (i.e. its direction reverses by 180°) and continues its journey. In a correct setup every laser gun’s beam must eventually be absorbed by a unique detector, and every detector must absorb exactly one beam. The task is to choose a placement of guns and detectors (one per chosen corner, with no corner hosting both) so that the maximum possible number of pairs ( (\text{gun},,\text{detector}) ) is achieved.

A useful observation – once one fixes the polygon’s vertex coordinates ( (x_i,y_i) ) in order (with ( i=1,2,\dots,n )) – is that the beam fired at a given vertex ( i ) travels in a fixed diagonal direction determined solely by the configuration of the two incident edges. In fact, if the two incident edge vectors at vertex ( i ) are ( \vec{v}) and ( \vec{w} ), then the beam direction is ( \big(\operatorname{sgn}(v_x+w_x),,\operatorname{sgn}(v_y+w_y)\big) ) (here, ( \operatorname{sgn}() ) denotes the sign function). Moreover, since all vertex coordinates are integral the first vertex (different from ( i )) hit by the ray fired from vertex ( i ) is exactly the vertex ( j ) for which

[ x_j=x_i+t,\operatorname{sgn}(v_x+w_x),\quad y_j=y_i+t,\operatorname{sgn}(v_y+w_y)\quad (t>0,; t\in\mathbb{Z}) ]

(with the smallest possible ( t )). It turns out that in many mirror traps the pairing defined by assigning each vertex ( i ) the vertex ( f(i) ) hit by its beam is an involution ( (f(f(i))=i) ). Thus one may choose the pair ( (i,f(i)) ) (with ( i ) acting as gun and ( f(i) ) as detector) whenever ( f(i)=j ) and ( f(j)=i ).

Your task is to read the polygon description, compute for every vertex ( i ) the first vertex ( f(i) ) hit by a beam fired from ( i ) (according to the rule above) and then output all pairs ( (i,j) ) (with ( i<j )) for which ( f(i)=j ) and ( f(j)=i ). The indices are 1–based. If no such pair exists, output 0.

inputFormat

The first line of input contains a single even integer \( n \) (with \( n\ge 4 \)) – the number of vertices of the polygon. The following \( n \) lines each contain two integers \( x_i \) and \( y_i \) (\( -10^4\le x_i,y_i\le 10^4 \)), the coordinates of the vertices given in order (either clockwise or counter‐clockwise). It is guaranteed that consecutive sides are perpendicular.

outputFormat

The first line should contain a single integer \( m \), the number of gun–detector pairs in your solution. Each of the following \( m \) lines should contain two integers \( i \) and \( j \) (with \( i<j \)), representing that a laser gun is to be installed at vertex \( i \) and a detector at vertex \( j \) such that the beam fired from \( i \) will be absorbed at \( j \). If no pair exists, simply output 0.

sample

4
0 0
1 0
1 1
0 1

0