D. M-Mart Coupons
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Magikarp is shopping at M-Mart. He has $$$n$$$ coupons in his pocket, numbered from $$$1$$$ to $$$n$$$. Each coupon gives either a percentage discount or a dollar discount.

There are $$$q$$$ items Magikarp might buy. For each item, he chooses a contiguous subarray of his coupons and may use those coupons in any order. He wants to pay as little as possible. A price cannot go below $$$0$$$; if a discount would make it negative, the price becomes $$$0$$$.

Magikarp has already chosen which coupons to apply to each item, but not the order in which to apply those coupons. Help Magikarp find the minimum possible price of each item.

Input

The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n,q \le 200\,000$$$) — the number of coupons and the number of items, respectively.

Each of the next $$$n$$$ lines describes one coupon. The $$$i$$$th line contains a character $$$t_i$$$ and an integer $$$x_i$$$. If $$$t_i=\texttt{P}$$$, the coupon discounts the current price by $$$x_i$$$ percent ($$$0 \le x_i \le 99$$$). If $$$t_i=\texttt{D}$$$, the coupon discounts the current price by $$$x_i$$$ dollars ($$$0 \le x_i \le 10^9$$$).

Each of the next $$$q$$$ lines contains three integers $$$p$$$, $$$l$$$, and $$$r$$$ ($$$1 \le p \le 10^6$$$, $$$1 \le l \le r \le n$$$) — the item's original price and the endpoints of the chosen coupon subarray, respectively.

It is possible that the same coupon is used on multiple items.

It is guaranteed that applying all percentage coupons among the $$$n$$$ coupons to a price of $$$1$$$ (ignoring dollar coupons) leaves a price of at least $$$10^{-250}$$$. The smallest positive value of a 64-bit double is around $$$10^{-308}$$$.

Output

For each item, output its minimum possible price if Magikarp applies his chosen coupons in the optimal order. Your answer is accepted if its absolute error is at most $$$10^{-4}$$$.

Examples
Input
3 3
D 10
P 50
D 5
100 1 3
10 1 3
100 2 2
Output
35.000000000000000
0.000000000000000
50.000000000000000
Input
4 2
P 90
D 1
P 10
D 50
100 1 4
1000 2 4
Output
0.000000000000000
849.000000000000000
Note

In the first sample, Magikarp can use the $$$50\%$$$ coupon first, reducing the price from $$$100$$$ to $$$50$$$, then use both dollar coupons to reduce it to $$$35$$$. For the second item, the same discounts reduce the price to $$$0$$$. The second query uses only the $$$50\%$$$ coupon.

In the second sample, the $$$90\%$$$ and $$$10\%$$$ coupons reduce the first item's price from $$$100$$$ to $$$9$$$, and the two dollar coupons reduce it to $$$0$$$. For the second item, the $$$10\%$$$ coupon reduces $$$1000$$$ to $$$900$$$, and the two dollar coupons then reduce it by $$$51$$$.

Hint: in order to satisfy the above error bound, be sure to print many digits of your answer (at least 8).

For example, if your answer is stored in ans:

  • Java: System.out.printf("%.10f%n", ans);
  • C++: cout << fixed << setprecision(10) << ans << '\n'; (include <iomanip>)
  • Python: print(f"{ans:.10f}")