Byteasar 是《Your taxi》杂志的主编，该杂志每年都会发布 Byteotia 地区最佳出租车公司的排名。最新一期的准备工作即将开始，重点关注最实惠的出租车公司。

第 $i$ 家出租车公司的乘车费用总是由以下两部分之和决定： 固定费用 $s_i$：乘车费用，与行程距离无关； 可变距离费用：行程距离 $d$（单位：字节米）乘以每字节米的费用 $c_i$。

每家公司都有其各自的参数 $s_i$ 和 $c_i$。

Byteasar 对出租车公司的真实排名有很强的个人见解。在过去的排名中，他考虑了多种标准，并经过精心挑选，使得最终的“客观”排名符合他的信念。严厉的批评迫使他简化了规则：今年的版本将侧重于乘车价格，大多数读者认为这是客观的。然而，Byteasar 仍然可以调整一个参数，使最终排名符合他的信念：行程距离 $d$，该距离必须为正数（但不一定是整数）。当然，Byteasar（凭他自己的良心）被允许以任意方式处理平局。

话虽如此，Byteasar 的观点既坚定又不断变化，原因很充分：出租车公司不仅向 Byteasar 行贿，而且还不断改变其服务质量，这使得排名必须进行调整。请编写一个程序，在每次条件变更后找出合适的行程距离 $d$。

输入格式

标准输入的第一行包含一个正整数 $n$，表示出租车公司的数量。 接下来的 $n$ 行描述了各家公司：每行包含两个非负整数 $s_i$ 和 $c_i$，用空格分隔，分别表示第 $i$ 家公司的固定费用和每字节米的可变距离费用。 下一行包含一个由 $n$ 个互不相同的正整数组成的序列，范围从 $1$ 到 $n$，这是 Byteasar 的初始排名（序列中的第 $i$ 个元素是排名第 $i$ 的公司编号）。 下一行包含一个非负整数 $q$，表示更新次数。接下来的 $q$ 行描述了连续的更新：每行包含两个不同的正整数 $a_i$ 和 $b_i$，表示 Byteasar 想要交换当前排名第 $a_i$ 位和第 $b_i$ 位的公司。

输出格式

你的程序应向标准输出打印恰好 $q + 1$ 行。第 $i$ 行应包含一个正有理数：在第 $i-1$ 次更新后，使得价格规则下的排名与 Byteasar 期望的排名相符的行程距离。距离应以不可约分数 $x/y$ 的形式打印，且分子 $x$ 和分母 $y$ 均不超过 $10^9$。 如果不存在这样的距离，则应打印单词 NIE。

样例

样例输入 1

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

样例输出 1

4/1
NIE
1/1
2/1

说明

对于样例的解释：要使排名为 2, 1, 3，Byteasar 应将距离设为 $d = 4$。此时总行程费用分别为 $8 + 3d = 20$，$12 + 2d = 20$ 和 $9 + 4d = 25$。由于第 1 家和第 2 家公司的费用相同，Byteasar 可以选择它们在排名中的顺序。在交换排名第 1 位和第 3 位的公司后，我们得到排名 3, 1, 2，无论 $d$ 取何值都无法达到。在下一次更新后，排名为 1, 3, 2；使用 $d = 1$ 可得到符合条件的费用 11, 14 和 13。在最后一次交换后，排名为 1, 2, 3，这可以在 $d = 2$ 时达到：此时费用分别为 14, 16 和 17。

子任务

测试集由以下子任务组成。每个子任务内可能包含多个测试点。 在所有测试中，满足：$1 \le n \le 500\,000$，$0 \le q \le 500\,000$ 且 $1 \le s_i, c_i \le 10^9$。

在上表中，“无同时平局”意味着对于所有正数 $d$，至多只有一对（不同的）公司在行程距离为 $d$ 时的总费用相同。此外，“无 NIE”意味着正确输出中不包含单词 NIE。