当前没有测试数据。

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

小栗帽在赛跑时主要可以分为起跑，巡航和冲刺三个阶段，巡航阶段的跑道可以看作一段 $[1, m]$ 的区间，她的终极技能“圣夜的奇迹跑者”如果能在完美位置区间 $[R, m]$（巡航阶段的最后一段闭区间）发动，就能在冲刺阶段获得巨大优势，但为了开启终极技能，她需要学习一些别的普通技能。

这些技能一共有 $n$ 个，根据触发条件的不同，可以简化为第 $i$ 个技能在闭区间 $[l_i, r_i]$ 等概率发动。

为了能够获得最好的位置，小栗帽需要让第 $k$ 个触发的技能在完美位置区间触发。

但是，技能不是学习了就一定可以触发的，技能的触发还和小栗帽的智力有关，可以简化为每个技能学习后都有 $P$ 的概率可以在这一局比赛中触发。

请你帮小栗帽找出对于每一个 $k$ 的最合理的技能搭配方案，输出第 $k$ 个触发的技能在完美位置区间的最大概率。

输入格式

第一行包含五个整数 $n, m, R, q, P$ $(1 \leq n, q \leq 5000, 1 \leq R \leq m \leq 2400, 0 \leq P \leq 100)$，表示技能的数量，巡航的长度，完美位置的起点，询问的数量，技能触发的概率为 $\frac{P}{100}$。

接下来的 $n$ 行，每行包含两个整数 $l_i, r_i$ $(1 \leq l_i < r_i \leq m)$，表示第 $i$ 个技能在区间 $[l_i, r_i]$ 等概率发动。

接下来的 $q$ 行，每行包含一个整数 $k$ $(1 \leq k \leq n)$，表示一次询问。

输出格式

一共 $q$ 行，每行一个浮点数表示第 $k$ 个触发的技能在完美位置的最大概率，误差不超过 $10^{-6}$。

5 2400 2000 1 100
1800 2200
1900 2100
1600 2400
1700 2300
1800 2200
3

0.875000000

6 2000 1500 3 80
1000 1200
1200 1600
1000 1800
1000 2000
1400 1700
800 1800
3
4
5

0.609066667
0.599253333
0.541354667