Interplanetary Teleportation

You are given n planets arranged on a number line with coordinates 1 to n. For each planet i (with i ≥ 2) a signal is sent which reaches all planets with indices in the interval \([l_i, i-1]\). When a planet i connects with a planet j (where \(l_i \le j \le i-1\)), a bidirectional teleportation portal is established between them. It takes 1 unit of time to use any portal in either direction.

You will be given q queries. In each query, a merchant is initially at planet \(x\) and his destination is chosen uniformly at random from the planets with indices in an interval \([a, b]\) where \(a < b < x\). The merchant travels from his starting planet \(x\) to the chosen destination using a series of teleportation portals and always takes the path that minimizes the travel time. Let \(dist(x,y)\) denote the minimum number of portals needed to travel from planet \(x\) to planet \(y\). The expected travel time is given by \[ E = \frac{1}{b-a+1} \sum_{y=a}^{b} dist(x,y). \] Your task is to compute and output the expected travel time for each query.

Note: It is guaranteed that for each query, \(a < b < x\), and the connections between planets ensure that every planet is reachable from any other planet.

inputFormat

The first line contains two integers n and q -- the number of planets and the number of queries.

The second line contains n-1 integers: \(l_2, l_3, \dots, l_n\), where the i-th integer represents the left endpoint for planet i's connection. (Planet 1 does not send a signal.)

Each of the next q lines contains three integers \(x, a, b\), describing a query where the merchant starts at planet \(x\) and chooses a destination uniformly at random from the interval \([a, b]\) (with \(a < b < x\)).

outputFormat

For each query, output a single line containing the expected travel time. Your answer will be accepted if its absolute or relative error does not exceed 10^-6.

sample

5 3
1 1 2 3
5 1 2
5 2 3
4 1 2

2.000000
1.500000
1.500000