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