#5078. 「POI2018 R3」出租车 Taxis

传统
500 - 11000 ms
256 MiB

---

题目描述

题目译自 XXV Olimpiada Informatyczna — III etap Taksówki

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$。

若无解，输出 NIE。

---

样例

输入

3
8 3
12 2
9 4
2 1 3
3
1 3
1 2
2 3

输出

4/1
NIE
1/1
2/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$。

---

附加样例

• $n=10, q=10$，满足子任务 $4$ 的随机样例。
• $n=10, q=10$，随机样例。
• $n=10, q=10$，$d=1/3$ 时各公司费用相同。
• $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$，无并列
3	$n \leq 2000$，无并列	25
4	无 NIE	30
5	无附加限制	25