Minimum Maximum Speed

ID: 13073

Type: Default

1000ms

256MiB

A is driving on a straight road which can be abstracted as a number line. You are given n monitoring records. The i-th record indicates that A passed coordinate x_i at time t_i. You then have m independent queries. In the i-th query, you are given two integers u_i and v_i. In that query, the time recorded at the u_i-th monitor is temporarily changed to v_i (the modification is effective only for the current query), and you are to determine the smallest possible value of the maximum speed that A could have ever achieved on any valid driving trajectory, rounded down.

More formally, for each query after modifying t_{u_i}</em> to v_i, you need to compute:

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

Note: Time modifications in queries are independent; that is, after each query, the modified time is reverted back to the original value.

inputFormat

The first line contains two integers n and m (number of monitoring records and number of queries).

The second line contains n integers x₁, x₂, ..., x_n representing the coordinates.

The third line contains n integers t₁, t₂, ..., t_n representing the times A passed the corresponding coordinates.

The following m lines each contain two integers u_i and v_i, representing that in this query, the time at index u_i is temporarily modified to v_i.

outputFormat

For each query, output a single integer on a separate line, which is the answer as defined in the problem statement.

sample

#P11021. Minimum Maximum Speed

Minimum Maximum Speed