Ito

수학은 매우 흥미롭고 매력적이어서 평생을 바칠 가치가 있다는 데 의심의 여지가 없다. 하지만 카리브해 어딘가에서 따뜻한 모래를 발끝으로 느끼고, 아름다운 여인들이 피냐 콜라다를 하나씩 가져다주는 모습을 보며 여생을 보내려 한다면, 실력을 다른 곳에 써야 한다.

그래서 키요시는 수학에 남긴 자신의 영향이 이미 충분히 크다고 판단하고, 돈을 벌러 나서기로 했다. 들어서 알고 있겠지만 경제 위기가 빠르게 다가오고 있고, 모두가 저축을 효율적으로 지킬 방법을 찾는다. 새로운 시장 흐름을 따르려고 키요시는 고객이 저축을 적절히 투자하도록 돕는 컨설팅 회사를 열었다. 이 문제의 투자 과정은 세 단계로 이루어진다. 시장에 가서 귀중품을 사고, 1년을 기다린 뒤, 다시 시장에 가서 판다.

투자에 쓸 수 있는 귀중품은 서로 다른 $N$개이다. 각 귀중품마다 현재 단위당 가격 $c_i$ 우드달러가 주어진다. 모든 귀중품은 수량에 제한이 없고 임의로 나눌 수 있다. 즉, 어떤 귀중품이든 0 이상의 실수량만큼 살 수 있다. 각 귀중품에는 두 제한값 $a_i$와 $b_i$가 알려져 있다. 내년에 단위당 가격은 이 두 값 사이에서 연속적으로 균등하게 분포한다.

$M$명의 고객이 각자에게 좋은 투자 계획을 세워 달라고 한다. $i$번째 고객은 $s_i$ 우드달러를 가지고 있다. 고객은 한편으로는 모든 귀중품을 판 뒤 손에 쥘 금액의 기댓값을 최대화하고 싶어 한다. 다른 한편으로는 많이 잃는 것이 두려워서, 최악의 경우에도 최소 $l_i$ 우드달러는 남기기를 원한다.

각 고객에 대해 키요시는 귀중품을 각각 얼마나 살지 정해야 한다. 고객은 가진 돈 안에서 임의의 금액을 쓸 수 있지만, 가진 금액을 넘을 수는 없다. 쓰지 않은 돈은 내년까지 그대로 남는다. 위험을 지나치게 떠안지 않으면서 각 고객이 가질 수 있는 기댓값의 최댓값을 구하라.

첫 줄에 두 정수 $N$과 $M$이 주어진다 ($0 \leq N, M \leq 100000$). 각각 귀중품의 개수와 고객의 수이다.

다음 $N$개 줄은 귀중품을 나타낸다. 각 줄에는 세 정수 $c_i$, $a_i$, $b_i$가 있다. 현재 가격, 그리고 내년 가격에 대한 제한 $a_i$와 $b_i$이다 ($1 \leq c_i \leq 100000$, $0 \leq a_i \leq b_i \leq 100000$).

그 뒤 $M$개 줄은 고객을 나타낸다. 각 줄에는 두 정수 $s_i$와 $l_i$가 있다. 고객이 가진 금액과, 최악의 경우에도 받아들일 최소 금액이다 ($1 \leq l_i \leq s_i \leq 100000$).

$M$개 줄을 출력한다. $i$번째 줄에는 $i$번째 고객이 위험을 지나치게 떠안지 않고 가질 수 있는 기댓값의 최댓값을 실수 하나로 적는다. 절대 오차 또는 상대 오차가 $10^{-6}$을 넘지 않으면 정답으로 인정한다. 정답을 $B$, 출력값을 $A$라 할 때 $\frac{|A-B|}{\max(1,B)} \leq 10^{-6}$이면 맞는 것으로 본다.

위 예제에서 첫 번째 고객은 두 번째 귀중품을 $0.1$ 단위, 세 번째 귀중품을 $9$ 단위 살 수 있다. 두 번째 고객은 첫 번째 귀중품을 $0.4$ 단위, 두 번째 귀중품을 $0.3$ 단위, 세 번째 귀중품을 $3$ 단위 살 수 있다. 세 번째 고객은 두 번째 귀중품을 $1$ 단위만 사면 된다.