Well, just you wait!#4490
One ordinary summer day, the Hare was, as usual, fleeing from the Wolf. This time, he dashed into a long corridor lined with doors and slipped through one of them. The passages behind these doors were quite bewildering, with some doors leading to the same room. The Wolf didn't catch which exact door the Hare used, but he did see that it was a door numbered between and . Each door is known to lead to a specific room. The Wolf then calls out a room number and rushes through any door that leads to that room (if no such door exists, he remains where he is).
Your task is to determine the probability that the Wolf ends up in the same room as the Hare, given that the Hare randomly chose a door between and .
The first line contains a single integer (1 \leq N \leq 10^5), representing the number of doors in the corridor. The next line contains integers A_i (0 \leq A_i \leq 10^9), where each A_i indicates the room number that the corresponding door leads to. Following this, there is an integer (1 \leq M \leq 10^5), which is the number of queries. Each of the next lines contains a query of one of two types:
If the first number in the line is , it is followed by three numbers l, r, p — specifying the range of doors and the room number called by the Wolf.
If the first number is , it is followed by two numbers , indicating that the door at position now leads to room .
For each query of the first type, output the probability as an irreducible fraction that the Wolf ends up in the same room as the Hare.
Example 1