Well, just you wait!
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 l and r. 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 l and r.
Input
The first line contains a single integer N (1 ≤ N ≤ 10^5), representing the number of doors in the corridor. The next line contains N integers A_{i} (0 ≤ A_{i} ≤ 10^9), where each A_{i} indicates the room number that the corresponding door leads to. Following this, there is an integer M (1 ≤ M ≤ 10^5), which is the number of queries. Each of the next M lines contains a query of one of two types. If the first number in the line is one, 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 two, it is followed by two numbers l, r, indicating that the door at position l now leads to room r.
Output
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.