Problem Description

Takahashi-kun sends integer sequences to Aoki-kun every year as his birthday present. But this year, Takahashi-kun plans to send sequences of points on a two-dimensional plane to Aoki-kun.

First, he makes 3 point sequences: $(a_0,\ a_1,\ ...,\ a_{N-1})$, $(b_0,\ b_1,\ ...,\ b_{N-1})$, and $(c_0,\ c_1,\ ...,\ c_{N-1})$, and makes a point $ d_0 $. Then he makes the points $d_1,\ d_2,\ ...,\ d_N$ in this order as follows:

• For each $i\ =\ 0,\ 1,\ ...,\ {N-1}$, $ d_{i+1} $ is defined as the intersection point of two lines: the line that passes through $ a_i $ and $ b_i $, and the line that passes through $ c_i $ and $ d_i $.

It can happen that a point $ d_{i+1} $ cannot be defined for some $ i $. For example, when two lines are the same, there are an infinite number of intersection points.

Takahashi-kun wants to know the smallest $ i $ such that $ d_{i+1} $ cannot be defined. To be precise, $ d_{i+1} $ cannot be defined if either of the following conditions is met.

• $c_i\ =\ d_i$
• Two lines given by $ a_i $, $ b_i $, $ c_i $, and $ d_i $ are the same, or parallel.

It is guaranteed that $a_i\ \neq\ b_i$ for all $ i $.

Note that, in the following sections, $ x $- and $ y $-coordinates of a point $ p $ are denoted as $ p.x $ and $ p.y $, respectively.

Input Format

Input is given from Standard Input in the following format:

$ N $ $ d_0.x $ $ d_0.y $ $ a_0.x $ $ a_0.y $ $ b_0.x $ $ b_0.y $ $ c_0.x $ $ c_0.y $ $ a_1.x $ $ a_1.y $ $ b_1.x $ $ b_1.y $ $ c_1.x $ $ c_1.y $ $ : $ $ a_{N-1}.x $ $ a_{N-1}.y $ $ b_{N-1}.x $ $ b_{N-1}.y $ $ c_{N-1}.x $ $ c_{N-1}.y $

Output Format

Print the smallest $ i $ such that $ d_{i+1} $ cannot be defined. If all points are defined, print $ N $.

Sample Input and Output

Sample Input #1

6
0 0
10 -10 10 10 10 0
0 10 20 10 10 10
0 -10 0 -100 0 10
0 0 0 -100 0 0
0 0 0 1 0 0
31 14 15 92 65 35

Sample Output #1

3

Sample Input #2

11
0 0
299 0 299 1 3 1
1 0 1 1 300 100
299 0 299 1 3 1
1 0 1 1 300 100
299 0 299 1 3 1
1 0 1 1 300 100
299 0 299 1 3 1
1 0 1 1 300 100
299 0 299 1 3 1
1 0 1 1 300 100
0 0 3 1 3 1

Sample Output #2

10

Notes/Hints

Constraints

• $1\ \leq\ N\ \leq\ 100,000$
• $|a_i.x|,\ |a_i.y|,\ |b_i.x|,\ |b_i.y|,\ |c_i.x|,\ |c_i.y|\ \leq\ 1,000$
• $|d_0.x|,\ |d_0.y|\ \leq\ 1000$
• $a_i\ \neq\ b_i$
• All values in input are integers.

见题面 Input 部分

见题面 Output 部分