Time Limit: 2 sec / Memory Limit: 1024 MB

Score : `100` points

### Problem Statement

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

Firstly, 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}` can not 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}` can not be defined.
To be precise, `d_{i+1}` can not 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.

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

Input is given from Standard Input in the following format:

Nd_0.xd_0.ya_0.xa_0.yb_0.xb_0.yc_0.xc_0.ya_1.xa_1.yb_1.xb_1.yc_1.xc_1.y:a_{N-1}.xa_{N-1}.yb_{N-1}.xb_{N-1}.yc_{N-1}.xc_{N-1}.y

### Output

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

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