Problem D. Road Accident

Author:A. Klenin, T. Chistyakov   Time limit:1 sec
Input file:input.txt   Memory limit:2 Mb
Output file:output.txt  

Statement

Two cars crashed on the road, receiving some damage each, and raising the usual question: "Who to blame?". To answer this, it is essential to thoroughly reconstruct the sequence of events. By gathering witness testimonies and analyzing tire tracks, positions and speeds of cars just before the impact were determined. From these positions until the crash the cars moved straight forward.

Your program must, given the available data, calculate for each car what part of it first came into contact with the other car. Parts are numbered as shown on the picture.

Input file format

Input file contains twelve floating point numbers: x1 y1 u1 v1 w1 s1 x2 y2 u2 v2 w2 s2, where (x, y) and (u, v) — coordinates of back-left and forward-left corners of the car, w — width of the car, s — speed of the car.

Output file format

Output file must contain two integers: p1 p2, where p — number of part which first contacted the other one (if two parts came into contact simultaneously, output the lesser of the part numbers),

Constraints

1 ≤ xi, yi, ui, vi, wi ≤ 106, 0 ≤ si ≤ 106. Input data is such that a crash certainly happens. Initially cars don't have common points.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
1.0 2.0 10.0 2.0 1.0 10.0
50.0 1.0 40.0 1.0 1.0 20.0
2 2
2
1 1 10 1 1 20
40 1 50 1 1 10
2 1

0.090s 0.016s 15