题目描述

小 A 正在一条笔直的公路上行驶（可以随时掉头，掉头的时间和路程忽略不计），这条公路可以被抽象为一条数轴。

你现在得到了 $n$ 个监控的信息，第 $i$ 条信息记录到：小 A 在 $t_i$ 时刻经过了坐标为 $x_i$ 之处。

有 $m$ 次询问，第 $i$ 次询问给定 $u_i$ 和 $v_i$，表示：假如将第 $u_i$ 个监控记录到小 A 经过 $x_i$ 的时间改为 $v_i$，小 A 所有可能的行驶过程中，最快时速的最小值是多少（答案向下取整）？询问之间互相独立，即每次询问的改动是暂时的。

形式化题意

给定 $n,m$，有长度为 $n$ 的数组 $x$ 与 $t$。进行 $m$ 次独立的修改，第 $i$ 次会将 $t_{u_i}$ 修改为 $v_i$，并询问：

$$\max_{i=1}^{n}\max_{j=i+1}^n \left\lfloor\frac{|x_i-x_j|}{|t_i-t_j|}\right\rfloor$$

前一次修改不会影响后一次修改，即询问结束后会撤销修改。

输入格式

第一行，两个正整数 $n,m$。

接下来 $n$ 行，每行两个整数 $x_i,t_i$。

接下来 $m$ 行，每行两个整数 $u_i,v_i$。

输出格式

对于每个询问，输出一行一个整数表示答案。

5 3
10 3
-10 1
0 5
-5 0
10 7
1 2
2 2
3 100

20
20
10

提示

样例解释：

第 $1$ 次询问：

小 A 第 $0$ 时刻位于 $-5$，第 $1$ 时刻位于 $-10$，第 $2$ 时刻位于 $10$，第 $5$ 时刻位于 $0$，第 $7$ 时刻位于 $10$，最快时速最慢是 $20$（$1$ 时刻到 $2$ 时刻，从 $-10$ 移动到 $10$ 的时候）。

---

本题共有 $10$ 个测试点，每个测试点分值均为 $10$ 分。

测试点编号	特殊性质
$1 \sim 3$	$n,m\leq 10^3$
$4 \sim 5$	$-10^5\leq x_i\leq 10^5$
$6 \sim 7$	$m\leq 100$
$8 \sim 10$	N/A

对于 $100\%$ 的数据，$2\leq n\leq 10^5$，$1\leq m\leq 10^5$，$-10^9\leq x_i\leq 10^9$，$0\leq t_i,v_i\leq 10^9$，$1\leq u_i\leq n$，保证任意时刻不存在两个监控记录的时间相同。