Segment and Rectangle

Does the line segment ((X_1, Y_1)) to ((X_2, Y_2)) intersect with the rectangle defined by its diagonal endpoints ((X_3, Y_3)) and ((X_4, Y_4)), where the rectangle's sides are parallel to the coordinate axes? The segment and the rectangle intersect if they share at least one point.

Input

The first line contains four integers: (X_1, Y_1, X_2, Y_2), representing the coordinates of the segment's endpoints, separated by spaces. The second line contains four integers: (X_3, Y_3, X_4, Y_4), representing the coordinates of one of the rectangle's diagonals, separated by spaces. All coordinates are integers with an absolute value not exceeding 50.

Output

Output the number (1) if the rectangle and the segment intersect, or (0) if they do not.

Examples