P12770 [POI 2018 R3] 出租车 Taxis

翻译来自于 [LibreOJ](https://loj.ac/p/5078)。

**题目译自 [XXV Olimpiada Informatyczna — III etap](https://sio2.mimuw.edu.pl/c/oi25-3/dashboard/) [Taksówki](https://szkopul.edu.pl/problemset/problem/pxbqUTPy3IuPDul9FdT2_Sth/statement/)** Bajtazar 是《出租车与你》杂志的主编，每年发布拜托尼亚最便宜出租车公司排行榜。新一期排行榜即将来袭。 每家出租车公司 $i$ 的乘车费用由两部分组成： - 固定上车费 $s_i$，与行程距离无关； - 行程费，距离 $d$（单位：拜托米）乘以每拜托米的单价 $c_i$。 每家公司有固定的 $s_i$ 和 $c_i$ 参数。 Bajtazar 希望综合多种标准制定排行，但为避免偏见指控，他决定仅以价格为依据。他设定了理想的排行榜，希望通过选择一个正数（不一定为整数）的行程距离 $d$，使 $d$ 拜托米的费用排序与理想排行一致，允许自行处理平局情况。 然而，各公司试图贿赂 Bajtazar，且服务标准时有变动，导致理想排行频繁调整。编写程序，帮助他在每次调整后确定合适的距离参数 $d$。

第一行包含一个自然数 $n$，表示出租车公司数量。 接下来的 $n$ 行描述各公司，每行包含两个自然数 $s_i, c_i$，分别表示上车费和每拜托米费用。 下一行包含 $n$ 个互不相同的自然数（范围 $[1, n]$），表示 Bajtazar 的初始理想排行（第 $i$ 个数为应排在第 $i$ 位的公司编号）。 再下一行包含一个自然数 $q$，表示调整次数。 接下来的 $q$ 行描述调整，每行包含两个不同的自然数 $a_i, b_i$，表示将排行中第 $a_i$ 位与第 $b_i$ 位交换。

输出 $q+1$ 行，第 $i$ 行包含一个正有理数，表示使排行与前 $i-1$ 次调整后一致的距离 $d$，以不可约分数 $x/y$ 形式输出，$x, y \leq 10^9$。**若有多个 $d$ 满足条件，你需要输出最小的合法的 $d$。** 若无解，输出 `NIE`。

**样例 1 解释** 为实现排行 $2,1,3$，Bajtazar 可设 $d=4$，费用为 $8+3d=20, 12+2d=20, 9+4d=25$。公司 $1$ 和 $2$ 费用相等，可按理想顺序排列。交换第 $1$ 位和第 $3$ 位得 $3,1,2$，无任何 $d$ 可实现。再次交换第 $3$ 位和第 $2$ 位得 $1,3,2$，设 $d=1$，费用为 $11, 14, 13$。最后交换第 $2$ 位和第 $3$ 位得 $1,2,3$，设 $d=2$，费用为 $14, 16, 17$。 **附加样例** 1. $n=10, q=10$，满足子任务 $4$ 的随机样例。 2. $n=10, q=10$，随机样例。 3. $n=10, q=10$，$d=1/3$ 时各公司费用相同。 4. $n=1000, q=1000$，仅一种可能排行：任意 $d$ 下公司 $1$ 比 $2$ 便宜，$2$ 比 $3$ 便宜，依此类推，初始排行如此。每偶数次调整交换两位置，奇数次调整复原。 所有测试点满足 $1 \leq n \leq 500000, 0 \leq q \leq 5000000, 1 \leq s_i, c_i \leq 10^9$。 详细子任务附加限制及分值如下表所示。「无并列」表示任意正 $d$ 至多一对不同公司费用相等；「无 `NIE`」表示答案不含 `NIE`。 | 子任务 | 附加限制 | 分值 | | :---: | :--: | :---: | | $1$ | $q=0$，无并列 | $10$ | | $2$ | $n, q \leq 2000$，无并列 | $10$ | | $3$ | $n \leq 2000$，无并列 | $25$ | | $4$ | 无 `NIE` | $30$ | | $5$ | 无附加限制 | $25$ |