eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Ну, погоди!

Ну, погоди!

Лимит времени 8 секунд
Лимит использования памяти 128 MiB

В один простой летний день Заяц как всегда убегал от Волка. И вот в этот раз он добежал до длинного коридора с дверьми и забежал в одну из них. Все проходы через эти двери были очень запутаны, но так получилось, что некоторые из дверей могут вести к одной комнате. Волк не заметил, куда именно забежал Заяц, но видел, что это была дверь на промежутке от l до r. Для каждого прохода известно, в какую комнату он ведет. Теперь Волк называет число – номер комнаты, и забегает в любую дверь, ведущую к этой комнате (если такой нет, то Волк остается на месте).

Ваша задача, вычислить какая вероятность того, что Волк попадет в ту же комнату, что и Заяц, если учесть, что Заяц выбирал случайную дверь на промежутке от l до r.

Входные данные

В первой строке находится одно число N (1N10^5), количество дверей в коридоре. Далее следует N чисел A_{i }(0A_i10^9) – номера комнат, в которые ведет каждый проход соответственно. Затем следует число М (1M 10^5) – количество запросов одного из двух типов. Затем находится М строк, где если первое число в строке равно единице, то далее следует три числа l, r, p – указанный промежуток и номер комнаты, которую назвал Волк. Если первое число было равно двум, то далее следует два числа l, r и это значит, что теперь дверь, стоящая на позиции l ведет в комнату r.

Выходные данные

Для каждого запроса с номером один выведите ответ на задачу. Результат выводить в виде несократимой дроби (см. пример).

Пример

Входные данные #1
6
1 2 3 1 2 3
5
1 1 6 2
2 1 2
1 1 6 2
1 1 1 1
1 2 2 2
Выходные данные #1
1/3
1/2
0/1
1/1
Автор Александр Бурков
Источник Дистанционная Летняя Компьютерная Школа - лето 2013 года