Description

这天，rockdu 正在复习操作系统，但是被一个叫做 HRRN 的算法难住了。

HRRN（最高响应比优先调度）算法是操作系统中的一个经典算法。其背景如下：给出许多进程，第 $i$ 个进程有一个出现时刻 $x_i$ 和一个持续时间 $s_i$，表示该进程从 $x_i$ 时刻才出现（进程出现之后才可以被选择），并且需要分配 $s_i$ 个单位的执行时间。若当前时刻为 $t$，定义一个进程在当前时刻的响应比为 $1 + \frac{t - x_i} {s_i}$，HRRN 算法的关键步骤就是要选择已经出现的进程（即 $x_i\le t$ 的进程）中响应比最大的进程。

现在给定 $m$ 个询问 $t_j$，为了使问题变得更简单，只需要对每个询问都求出该时刻能选择出的进程的最大响应比。如果直到 $t_j$ 时刻还没有进程出现，需要回答 $-1$。rockdu 的操作系统学得很差，所以他只好找到你来出出主意，聪明的你可以解决这个问题吗？

简化题意：给你 $n$ 个二元组 $(x_i,s_i)$，并给定 $m$ 次查询，每次查询一个数 $t_j$，询问所有满足 $x_i\le t_j$ 的元组中 $1 + \frac{t - x_i} {s_i}$ 的最大值。

Input

第一行一个正整数 $n\ (1\le n\le 10^6)$，表示共有 $n$ 个进程。

接下来 $n$ 行每行两个整数 $x_i,s_i\ (0\le x_i\le 10^6, 1\le s_i\le 10^6)$，两数用空格隔开，依次表示第 $i$ 个进程的出现时间和持续时间。

接下来一行一个正整数 $m\ (1\le m\le 10^6)$，表示共有 $m$ 个询问。

接下来 $m$ 行每行一个整数 $t_j\ (0\le t_j\le 10^6)$，表示第 $j$ 个询问为 $t_j$。

Output

输出共 $m$ 行。

若 $t_j$ 时刻及以前已有进程出现，则第 $j$ 行一个实数，表示在 $t_j$ 时刻，已经出现的进程中响应比最大的进程的响应比；

若 $t_j$ 时刻前没有进程出现，则该行输出 $-1$。

你的输出与答案的绝对误差或相对误差在 $10^{-6}$ 以内都被视为正确。

Samples

5
2 9
6 2
8 2
4 9
3 9
5
4
2
10
2
2

1.222222
1.000000
3.000000
1.000000
1.000000

Resources

The 21st UESTC Programming Contest Preliminary