Hide

Problem F
Urban Design

/problems/urbandesign/file/statement/en/img-0001.png

A new town is being planned, and the designers have some very specific ideas about how things should be laid out. First, they lay out the streets. Each street is perfectly straight and passes completely from one end of the town to the other. These streets divide the town into regions, and each region is to be designated either “residential” or “commercial.” The town planners require that any two regions directly across the street from one another must have different designations. On this one particular day, all of the streets have been planned, but none of the regions have been designated. One town planner wishes to purchase two properties, and it is important to him that the properties eventually have different designations. For this problem, the streets can be modeled by lines in the plane that extend forever in both directions and have no width, and properties may be modeled by points. Given the lines and two points, can you decide whether or not they must get different designations, “commercial” or “residential?”

Input

Input begins with an integer $S$ on a single line, giving the number of streets ($1 \le S \le 10\, 000$). The next $S$ lines of input each contain four integers $x_1$, $y_1$, $x_2$, and $y_2$, specifying the coordinates of two distinct points $(x_1, y_1)$ and $(x_2, y_2)$. The unique line through these two points gives one of the streets. Each coordinate is in the range $[0, 10\, 000]$, and no two lines will be identical. That is, the town will have $S$ distinct streets. The next line contains an integer $T$, the number of pairs of properties to test ($ 1 \le T \le 1\, 000$). This is followed by $T$ lines of input, each containing four integers $x_3$, $y_3$, $x_4$, and $y_4$, representing two distinct points $(x_3, y_3)$ and $(x_4, y_4)$, where each point lies within one of the two properties to test. None of these points will lie on any of the streets, nor will both points lie within the same property. Again, each coordinate is in the range $[0, 10\, 000]$.

Output

For each of the $T$ pairs of properties to be tested, output either “same” if the properties are guaranteed to receive the same designation or “different” if they are guaranteed to receive different designations.

Sample Input 1	Sample Output 1
2 1 1 2 1 1 1 1 2 3 2 0 2 2 2 0 0 3 0 0 2 2	different same same

Sample Input 2	Sample Output 2
4 1 3 2 4 1 3 2 5 1 3 3 4 7 9 8 8 2 14 7 10 13 1 4 2 3	same different

Problem FUrban Design

Input

Output

Problem F
Urban Design