409721: GYM103708 C Candies median

You are the teacher of a kindergarten classroom and there will be a party in a few days. As expected, you are in charge of bringing all the candies for the kids. You have created $$$q$$$ possible plans over the $$$n$$$ types of candies that exist. For each plan:

First of all, the $$$i$$$-th type of candy has a sweetness level of $$$a_{i}$$$ (this value can be negative, in the case of sour or spicy ones). You have sorted all these values in ascending order ($$$a_{i} < a_{i + 1}$$$ for all valid $$$i$$$).

Then, you choose $$$k$$$ tuples $$$(l, r, x)$$$ that mean that you'll buy $$$x$$$ candies of each type with id in the range $$$[l, r]$$$.

The beauty of a plan is the value of the median of all the sweetness levels of the candies you choose. Your task is to compute the beauty of each plan.

The first line of input contains two integers $$$n$$$ and $$$q$$$ ($$$1 \leq n, q \leq 5 \cdot 10^{5}$$$) — The number of types of candies and the number of plans to analyze.

The second line of input contains $$$n$$$ integers $$$a_{i}$$$ ($$$|a_{i}| \leq 10^{9}$$$, $$$a_{i} < a_{i + 1}$$$ for all valid $$$i$$$) — The sweetness level of the types of candy.

The lines describe $$$q$$$ plans.

The first line of a plan contains an integer $$$k_{i}$$$, the number of tuples of the $$$i$$$-th plan.

The following $$$k_{i}$$$ lines contain three integers $$$l_{j}$$$, $$$r_{j}$$$ and $$$x_{j}$$$ ($$$1 \leq l_{j} \leq r_{j} \leq n$$$, $$$1 \leq x_{j} \leq 10^{6}$$$) — The limits of the range of ids to choose and the number of candies to choose from each type, respectively.

It is guaranteed that the sum of $$$k_{i}$$$ among all the plans doesn't exceed $$$5\cdot 10^{5}$$$.

Print $$$q$$$ lines — The $$$i$$$-th line must contain the beauty of the $$$i$$$-th plan. Your answer will be considered correct if its relative or absolute value doesn't exceed $$$10^{-9}$$$.

In other words, let's assume that your answer is $$$a$$$, and the answer of the jury is $$$b$$$. The checker program will consider your answer correct, if $$$\frac{|a-b|}{\max(1, b)} \leq 10^{-9}$$$

7 3
-19 -2 0 9 17 18 20
2
4 6 1
2 6 4
1
3 3 1
2
3 4 2
1 5 1

9
0
0

7 3
-15 -9 -7 0 1 12 15
1
2 7 1
1
7 7 1
4
5 6 1
3 6 5
6 7 4
7 7 2

0.5
15
6.5