坐标

题目描述

给定平面上的一个坐标 $(a, b)$。接下来，我们对这个坐标按顺序执行 $N$ 次操作。第 $i$ 次操作$（1 ≤ i ≤ N）$是将坐标的 $x$ 值增加 $x_i$，$y$ 值增加 $y_i$。因此 $N$ 次操作结束后，坐标将变为 $(c, d)$，其中 $c = a + x_1 + x_2 + x_3 + … + x_N$，$d = b + y_1 + y_2 + y_3 + … + y_N$。 假设现在已经知道了一开始的坐标 $(a, b)$ 和最终的坐标 $(c, d)$，而 $N$ 次操作中恰好混入了一次多余的操作。你能判断哪一次操作是多余的吗？

输入格式

第一行为四个整数 $a, b, c, d$，分别表示最开始的坐标、操作结束时的坐标。 第二行为一个整数 $N$，表示操作次数（多余的那次操作未计入在内）。 接下来 $N + 1$ 行，每行两个整数 $x_i, y_i$，按顺序表示每一次的操作。保证其中恰好有一次操作是多余的。

输出格式

一个整数 $k$，表示输入的第k次操作是多余的。也就是说，将 $N + 1$ 次操作中的第 $k$ 次操作删去，按顺序执行其他的 $N$ 次操作，坐标 $(a, b)$ 正好可以变为 $(c, d)$。如果有多个满足要求的答案，请输出编号最小的。

1 2 4 5
1
3 3
1 2

2

3 5 20 0
4
1 1
-2 -8
10 2
7 3
8 0

4

提示

#### 数据范围与提示 对于 $30\%$ 的测试点，保证 $1 ≤ N ≤ 2$。 对于 $60\%$ 的测试点，保证 $1 ≤ N ≤ 2000$。 对于 $100\%$ 的测试点，保证 $1 ≤ N ≤ 2000000，-10000 ≤ a, b, x_i, y_i ≤ 10000$。 #### 样例 $1$ 解释 如果将第 $2$ 次操作 $(1, 2)$ 删去，坐标 $(1, 2)$ 按剩余操作 $(3, 3)$ 执行，恰好可以得到最终的坐标 $(4, 5)$。 #### 样例 $2$ 解释 如果将第 $4$ 次操作 $(7, 3)$ 删去，坐标 $(3, 5)$ 按剩余操作 $(1, 1)$、$(-2, -8)$、$(10, 2)$、$(8, 0)$依次执行，恰好可以得到最终的坐标$(20, 0)$。

来源

童程童美