问题描述

Takahashi君每年都会将整数序列作为他的生日礼物发送给Aoki君。但是在今年，他打算给Aoki君发送二维平面上的点序列。

首先，他创建了三个点序列：$(a_0, a_1, ..., a_{N-1})$，$(b_0, b_1, ..., b_{N-1})$和$(c_0, c_1, ..., c_{N-1})$，并创建了一个点$d_0$。然后按照以下方式依次创建点$d_1, d_2, ..., d_N$：

• 对于每个$i = 0, 1, ..., {N-1}$，$d_{i+1}$被定义为两条直线的交点：通过$a_i$和$b_i$的直线以及通过$c_i$和$d_i$的直线。

可能会出现某些$i$无法定义点$d_{i+1}$的情况。例如，当两条直线重合时，有无限多个交点。

Takahashi君想知道最小的$i$，使得无法定义$d_{i+1}$。具体而言，如果满足以下任一条件，则无法定义$d_{i+1}$。

• $c_i = d_i$
• 由$a_i$，$b_i$，$c_i$和$d_i$所确定的两条直线相同或平行。

保证对于所有的$i$，都有$a_i \neq b_i$。

请注意，在以下各节中，点$p$的$x$和$y$坐标分别表示为$p.x$和$p.y$。

约束条件

• $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$
• 输入中的所有值都是整数。

输入

输入以以下格式从标准输入给出：

$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$

输出

输出最小的$i$，使得无法定义$d_{i+1}$。如果所有点都被定义，则输出$N$。

示例输入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

示例输出1

3

示例输入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

示例输出2

10