圣夜的奇迹跑者
Description
小栗帽在赛跑时主要可以分为起跑，巡航和冲刺三个阶段，巡航阶段的跑道可以看作一段 [1, m] 的区间，她的终极技能 "圣夜的奇迹跑者" 如果能在完美位置区间 [R, m]（巡航阶段的最后一段闭区间）发动，就能在冲刺阶段获得巨大优势，但为了开启终极技能，她需要学习一些别的普通技能。
这些技能一共有 n 个，根据触发条件的不同，可以简化为第 i 个技能在闭区间 [li, ri] 等概率发动。
为了能够获得最好的位置，小栗帽需要让第 k 个触发的技能在完美位置区间触发。
但是，技能不是学习了就一定可以触发的，技能的触发还和小栗帽的智力有关，可以简化为每个技能学习后都有 P 的概率可以在这一局比赛中触发。
请你帮小栗帽找出对于每一个 k 的最合理的技能搭配方案，输出第 k 个触发的技能在完美位置区间的最大概率。
第一行包含五个整数 n, m, R, q, P (1 ≤ n, q ≤ 5000, 1 ≤ R ≤ m ≤ 2400, 0 ≤ P ≤ 100)，表示技能的数量，巡航的长度，完美位置的起点，询问的数量，技能触发的概率为 
。
接下来的 n 行，每行包含两个整数 li, ri (1 ≤ li < ri ≤ m)，表示第 i 个技能在区间 [li, ri] 等概率发动。
接下来的 q 行，每行包含一个整数 k(1 ≤ k ≤ n) ，表示一次询问。
一共 q 行，每行一个浮点数表示第 k 个触发的技能在完美位置的最大概率，误差不超过 10 - 6。
Input
第一行包含五个整数 n, m, R, q, P (1 ≤ n, q ≤ 5000, 1 ≤ R ≤ m ≤ 2400, 0 ≤ P ≤ 100)，表示技能的数量，巡航的长度，完美位置的起点，询问的数量，技能触发的概率为 。
接下来的 n 行，每行包含两个整数 li, ri (1 ≤ li < ri ≤ m)，表示第 i 个技能在区间 [li, ri] 等概率发动。
接下来的 q 行，每行包含一个整数 k(1 ≤ k ≤ n) ，表示一次询问。
Output
一共 q 行，每行一个浮点数表示第 k 个触发的技能在完美位置的最大概率，误差不超过 10 - 6。
5 2400 2000 1 100
1800 2200
1900 2100
1600 2400
1700 2300
1800 2200
3
6 2000 1500 3 80
1000 1200
1200 1600
1000 1800
1000 2000
1400 1700
800 1800
3
4
5
0.875000000
0.609066667
0.599253333
0.541354667