Faulty BIT – Parity Query Probability

In this problem, you are given an array A of length n (indexed from 1 to n) which is initially all zeros. There are m operations. There are two kinds of operations:

• Update Operation: 1 l r. In this operation, an index x is chosen uniformly at random from the interval [l, r] and an update is performed by calling Add(x) on a Fenwick tree (also known as BIT). However, the implementation of the BIT is erroneous: the update and query functions use the wrong direction when iterating. Specifically, instead of using the standard update (increasing indices) and query (decreasing indices) routines, the functions are written as follows (operations are performed modulo 2):

// Erroneous BIT implementation (mod 2 arithmetic)

// lowbit(x) returns the lowest nonzero bit of x, i.e. x & -x

// ErrAdd(x): for updating at index x
function ErrAdd(x):
    while x > 0:
        BIT[x] = BIT[x] ⊕ 1
        x = x - lowbit(x)

// ErrQuery(x): for querying prefix sum in BIT
function ErrQuery(x):
    sum = 0
    while x <= n:
        sum = sum ⊕ BIT[x]
        x = x + lowbit(x)
    return sum

The answer returned for a query 2 l r is computed as ErrQuery(r) ⊕ ErrQuery(l-1) (recall that modulo‐2 addition is the same as XOR) and it is intended to equal the true parity \(\sum_{i=l}^{r}A_i \bmod 2\) under correct implementation.

Due to the reversed iteration directions in both Add and Query, the BIT does not work as expected. However, in the original testcases the erroneous code passed. Now, before each query the only uncertainty is in every update operation: the value x for an update operation 1 l r is chosen uniformly at random from the interval [l, r]. With this model, you are to compute, for every query operation, the probability that the result returned by the erroneous BIT equals the correct answer computed directly from the array A (which is updated by toggling A[x] modulo 2).

Observation: One may show that for any update operation with parameters 1 L R and for a given query 2 l r, the erroneous BIT’s contribution from that update is correct if and only if the chosen index x is not exactly l-1 or r (when these values lie in the interval [L,R]). In other words, if we define an error indicator for an update as

[ e = \begin{cases} 1, & \text{if } x = l-1 \text{ or } x = r,
0, & \text{otherwise,} \end{cases} ]

then the update has error probability:

[ q = \frac{[L \le l-1 \le R] + [L \le r \le R]}{R - L + 1}, ]

where \([P]\) equals 1 if the predicate P is true and 0 otherwise. Since the BIT works over \(\mathbb{F}_2\) (i.e. modulo 2) and each update’s effect is independent, the final answer for a query is correct if and only if the XOR (i.e. sum modulo 2) of the errors over all previous update operations equals 0. If we denote by \(q_i\) the error probability for the i\(\textsuperscript{th}\) update, then the probability that the XOR of errors is 0 is given by:

[ P = \frac{1}{2} \Biggl(1 + \prod_{i}(1 - 2q_i)\Biggr). ]

Your task is to process the operations in order. For an update operation, record the parameters. For a query operation 2 l r, compute the probability P (as described above) that the BIT operation returns the correct value. Print the answer as a floating‐point number with at least 6 decimal places.

---

Input Format:

1. The first line contains two integers n and m (\(1 \le n, m \le 10^5\)).
2. The next m lines each describe an operation. An operation is either of the form 1 l r or 2 l r (\(1 \le l \le r \le n\)).

---

Output Format:

1. For each query operation, output a line containing the probability that the BIT returns the correct answer. Answers within an absolute or relative error of 10^-6 will be accepted.

inputFormat

The first line contains two integers n and m.

The following m lines each contain an operation: either 1 l r for an update or 2 l r for a query.

outputFormat

For each query operation, output the probability (as a floating‑point number with at least 6 decimal places) that the erroneous BIT returns the correct answer.

sample

8 3
1 1 5
1 2 7
2 3 7

0.600000

</p>