Ну, погоди!
В один простой летний день Заяц как всегда убегал от Волка. И вот в этот раз он добежал до длинного коридора с дверьми и забежал в одну из них. Все проходы через эти двери были очень запутаны, но так получилось, что некоторые из дверей могут вести к одной комнате. Волк не заметил, куда именно забежал Заяц, но видел, что это была дверь на промежутке от 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.
Выходные данные
Для каждого запроса с номером один выведите ответ на задачу. Результат выводить в виде несократимой дроби (см. пример).