Ну, постривай!#4490
Одного звичайного літнього дня Заєць, як завжди, утікав від Вовка. Цього разу він добіг до довгого коридору з дверима і забіг в одну з них. Усі проходи через ці двері були дуже заплутані, але так сталось, що деякі з дверей можуть вести до однієї кімнати. Вовк не помітив, куди саме забіг Заєць, але бачив, що це були двері на проміжку від до . Для кожного проходу відомо, у яку кімнату він веде. Тепер Вовк називає число — номер кімнати, і забігає у довільні двері, які ведуть до цієї кімнати (якщо такої немає, то Вовк залишається на місці).
Ваша задача — обчислити ймовірність того, що Вовк потрапить у ту ж кімнату, що і Заєць, якщо врахувати, що Заєць вибирав випадкові двері на проміжку від до .
У першому рядку знаходиться одне число (1 \leq N \leq 10^5) — кількість дверей у коридорі. Далі йде чисел A_i (0 \leq A_i \leq 10^9) — номери кімнат, у які веде кожен прохід відповідно. Потім йде число (1 \leq M \leq 10^5) — кількість запитів одного з двох типів. Потім знаходиться рядків. Якщо перше число у рядку рівне , то далі йде три числа l, r, p — вказаний проміжок та номер кімнати, яку назвав Вовк. Якщо перше число було рівне , то далі йде два числа і це означає, що тепер двері, які знаходяться на позиції ведуть у кімнату .
Для кожного запиту з номером виведіть відповідь до задачі. Результат виведіть у вигляді нескоротного дробу (див. приклад).
Приклад 1