Description

Little A is driving on a straight highway (can make U-turns instantly, ignoring time and distance), abstracted as a number line.

You are given information from $n$ surveillance records. The $i$-th record indicates Little A was at coordinate $x_i$ at time $t_i$.

There are $m$ queries. The $i$-th query provides $u_i$ and $v_i$: if the time of the $u_i$-th record is temporarily changed to $v_i$, what is the minimal possible value of the maximum speed (floor to integer) in any valid driving path? Queries are independent; modifications are reverted after each query.

Formal Description

Given $n$, $m$, arrays $x$, and $t$ of length $n$. For each of $m$ independent modifications (changing $t_{u_i}$ to $v_i$), compute:

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

Input Format

First line: Two integers $n$, $m$.

Next $n$ lines: Two integers $x_i$, $t_i$.

Next $m$ lines: Two integers $u_i$, $v_i$.

Output Format

For each query, output the floor of the maximum speed.

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

20
20
10

Hint

Sample Explanation

After the first query:

• Little A's positions: $(-5, 0)$, $(-10, 1)$, $(10, 2)$, $(0, 5)$, $(10, 7)$.
• The minimal maximum speed is $20$ (from $t=1$ to $t=2$, moving $-10$ to $10$).

---

Constraints:

• $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$.
• All $t_i$ (after modifications) are distinct.

Test Cases

Test Case	Special Properties
1~3	$n, m \leq 10^3$
4~5	$-10^5 \leq x_i \leq 10^5$
6~7	$m \leq 100$
8~10	None