在一条美丽的海岸线上，有 $N$ 栋摩天大楼排成一排。对于每栋楼 $i$（从 $1$ 到 $N$），我们已知它到海边的距离 $L_i$ 和它的高度 $H_i$。我们可以将每栋楼的顶部建模为二维平面上坐标为 $(L_i, H_i)$ 的一个点。这些大楼按到海边的距离排序，因此保证对于所有 $1 \le i < N$，都有 $L_i < L_{i+1}$。

你是一名专业的跳伞运动员，并计划在 $Q$ 个不同的日子里进行壮丽的跳伞。在第 $i$ 天（$1 \le i \le Q$），你会得到一个计划的跳伞位置，即一个水平坐标 $d_i$。保证没有大楼恰好位于 $d_i$ 处。

为了准备第 $i$ 天的跳伞，你必须进行以下准备工作：

• 首先，选择两栋大楼：一栋大楼 $l$ 位于你跳伞位置的左侧（即 $L_l < d_i$），另一栋大楼 $r$ 位于右侧（即 $L_r > d_i$）。保证这样的一对大楼总是存在。
• 接着，用一条直绳连接这两栋大楼的顶部，即点 $(L_l, H_l)$ 和 $(L_r, H_r)$，形成一条线段。
• 最后，你将从这条绳子上水平坐标恰好为 $d_i$ 的点处起跳。

作为一名谨慎的专业人士，你希望将与高海拔相关的风险降至最低。因此，对于每次跳伞，你必须选择一对大楼 $(l, r)$，使得在你的起跳坐标 $d_i$ 处，绳子的高度尽可能低。

请注意，绳子是一条理想化的线段。它允许穿过或与其他大楼相交；它的路径仅由所选的两个端点决定。

对于这 $Q$ 次计划的跳伞，求出这个最小可能的起跳高度。

输入格式

第一行包含一个整数 $N$ —— 大楼的数量。

接下来的 $N$ 行描述这些大楼。其中第 $i$ 行包含两个整数 $L_i$ 和 $H_i$ —— 第 $i$ 栋大楼到海边的距离和高度。保证 $L_1 < L_2 < \dots < L_N$。

下一行包含一个整数 $Q$ —— 计划跳伞的天数。

接下来的 $Q$ 行描述计划的跳伞。其中第 $i$ 行包含一个整数 $d_i$ —— 当天跳伞的水平坐标。保证 $d_i$ 不会与任何 $L_i$ 相等。

输出格式

对于这 $Q$ 次跳伞，每行输出两个空格分隔的整数 $s$ 和 $t$。这两个整数必须表示最小可能起跳高度的最简分数形式 $s/t$。如果分母为 $1$，仍需输出。

数据范围

• $2 \le N \le 2 \cdot 10^5$
• $1 \le Q \le 2 \cdot 10^5$
• $1 \le L_i, H_i \le 10^9$
• $L_1 < d_i < L_N$ ($1 \le i \le Q$)

样例

输入样例 1

4
1 4
4 3
7 5
11 2
7
2
3
5
6
8
9
10

输出样例 1

11 3
10 3
20 7
19 7
17 7
16 7
15 7

输入样例 2

4
1 1
3 3
5 5
7 7
3
2
4
6

输出样例 2

2 1
4 1
6 1