There are two different parallel lines L1 and L2 and there are N segments connecting them. Each segment connects two points (xi,yi) and (x′i,y′i) from these lines. You can assume that all the points (xi,yi) belong to L1 and all the points (x′i,y′i) belong to L2.
Your task is to find a subset of these segments such that there won’t be any two segments crossing each other. It is guaranteed that all the given points have distinct coordinates.
Input Format
The first line contains an integer N, the number of segments (1≤N≤105).
Each of the next N lines contain 4 space-separated integers xi,yi,x′i,y′i - each describing the endpoints of a segment (−109≤xi,yi,x′i,y′i≤109).
Output Format
Print the maximum number of segments such that there won’t be any two of them crossing each other.
All these three segments intersect each other, so we cannot choose any pair from them.
