Expected Spell Triggers

In this problem, you are given a modified version of a Hearthstone spell. The spell works as follows: a damage value \(d\) is chosen uniformly at random from the interval \([L,R]\). The spell deals \(d\) damage to every minion on the board. After each cast, if at least one minion dies (i.e. its health becomes \(\le 0\)), the spell is cast again with the same damage \(d\). Otherwise, if no minion dies in a cast, the spell stops. Note that when a minion dies, it is removed from the board; however, its death may cause additional subsequent triggers even if many minions have already died. Also, there is no limit on the number of minions on the board or on the total number of triggers.

You will process a sequence of \(m\) operations. There are two types of operations:

1. Add Operation: A minion with health \(h\) is added to the board. Note that \(h \le n\).
2. Query Operation: Given two integers \(L\) and \(R\), compute the expected number of times the spell will be triggered. In other words, if the damage \(d\) is chosen uniformly at random from \([L,R]\) and the effect of the spell is simulated based on the current board, what is the expected number of rounds (triggers) including the final cast that causes no deaths?

For simulation purposes, consider the following procedure when the spell is cast with a fixed damage \(d\):

• The process is carried out in rounds. In round \(r\), every minion currently on the board takes \(d\) damage. A minion will die in round \(r\) if its initial health \(h\) satisfies \[ (r-1)d < h \le rd. \] (Note that each minion falls into exactly one bucket based on its health.)
• The spell is cast for the first time (round 1). If at least one minion dies in round 1, the spell is cast again for round 2, and the process repeats. Otherwise, if no minion dies in a round, the spell stops immediately.
• In particular, if the spell manages to kill at least one minion in each of rounds \(1, 2, \dots, k\), then the spell is cast a final (\(k+1\)th) time; in round \(k+1\) no minion dies (possibly because the board is empty), and the process terminates.

Define \(f(d)\) as the number of rounds (spell triggers) when the fixed damage is \(d\). Notice that \(f(d) = k+1\), where \(k\) is the maximum number of consecutive rounds for which the damage buckets \(((r-1)d+1, rd]\) (for \(r=1,2,\dots,k\)) are all non-empty. Even if some minions remain on the board after round \(k\), if there is a gap (i.e. no minion with \(h \in ((k-1)d+1, kd]\)), the spell stops at that round.

Your task is to process the operations. Initially, the board is empty. For each query operation, output the expected value of \(f(d)\), where \(d\) is chosen uniformly at random from \([L,R]\). Output the result as a floating-point number with at least 6 decimal places.

inputFormat

The input begins with a line containing two integers \(n\) and \(m\) \( (1 \le n, m \le \text{small limits})\):

• \(n\): the maximum possible health of any minion.
• \(m\): the number of operations.

Each of the following \(m\) lines represents an operation in one of the following formats:

• If the line starts with 1, it represents an add operation and is followed by an integer \(h\) \(1 \le h \le n\). This means a minion with health \(h\) is added to the board.
• If the line starts with 2, it represents a query operation and is followed by two integers \(L\) and \(R\) \(1 \le L \le R \le n\). You must compute the expected number of spell triggers if the damage \(d\) is chosen uniformly at random from \([L,R]\).

outputFormat

For each query operation (operation type 2), output a single line containing the expected number of times the spell will be triggered. The number should be printed as a floating-point value with at least 6 decimal places of precision.

sample

10 5
1 3
1 7
2 3 3
1 5
2 2 4

1.000000
2.000000

</p>