Задача №111744. Профессиональный декоратор заборов
Вася работает подмастерьем в известной студии. Недавно ему поручили помогать молодому, но подающему большие надежды художественному декоратору заборов и изгородей Витезславу Смолокурову. Миссия эта очень ответственная, и от ее выполнения зависит Васино будущее.
Стиль Смолокурова очень необычен, а его работы пользуются большим спросом. Процесс работы разделен на два этапа. На первом этапе Вася делает заготовку — длинный забор, который состоит из набора цветных вертикальных планок. На втором этапе Витезслав приступает к работе.
Для того, чтобы придать забору более спокойный и гармоничный вид, он несколько раз производит следующую операцию: выбирает некоторый цвет и отрезок, после чего перекрашивает этот отрезок забора в выбранный цвет. По своей творческой натуре, Смолокуров может в корне менять концепцию узора по нескольку раз за час, поэтому иногда он перекрашивает одну и ту же планку несколько раз. Кроме того, Витезслав не хочет, чтобы какой-то узор повторялся слишком часто. Для того, чтобы избежать этого, он иногда проверяет, не совпадает ли один отрезок забора с другим.
Несложно догадаться, что и перекрашивание, и проверки осуществляет Вася. Работа эта не самая простая, поэтому Вася просит ему помочь хотя бы с проверками на совпадение.
Первая строка входного файла содержит одно целое число n — количество планок в заборе (1 ≤ n ≤ 100 000). Вторая строка содержит n целых чисел, разделенных пробелами — цвета соответствующих планок.
Третья строка входного файла содержит одно целое число m — количество сравнений и перекрашиваний (1 ≤ m ≤ 100 000). Следующие m строк содержат описания заданий, который Вася получает от Витезслава: четыре целых числа q, l, r и k.
В случае перекрашивания q = 0. Эта запись означает перекрашивание всех планок с l по r включительно в цвет k (1 ≤ l ≤ r ≤ n). В запросе на сравнение q = 1. Эта запись означает сравнение кусков забора длины k начиная с позиций l и r соответственно (1 ≤ l, r ≤ n - k + 1, k > 0).
Все числа во входном файле положительные и не превышают 100 000.
Выведите одну строку: для каждого запроса на сравнение выведите ‘+’ в случае совпадения соответствующих кусков забора и ‘-’ в противном случае.
7 1 2 1 3 1 2 1 3 0 4 5 2 1 3 1 2 1 3 1 3
+-
2 1 2 5 1 1 2 1 0 2 2 1 1 1 2 1 0 1 2 3 1 1 1 2
-++