Произведение на отрезке
Произведение на отрезке
Это нормально чувствовать себя взволнованным и напряженным за день до олимпиады по программированию. Чтобы расслабиться, вы пошли выпить со своими друзьями в соседний паб. Для сохранения остроты ума до следующего дня, Вы решили сыграть в следующую игру. Для начала Ваши друзья написали последовательность n целых чисел x[1], x[2],..., x[n]. Потом следует k раундов, на каждом из которых выполняется одна из следующих команд:
команда изменения, когда необходимо изменить одно значение в последовательности;
команда умножения, когда по заданным значениям i и j необходимо определить, является ли произведение
x[i]*x[i+1]* ... *x[j-1]*x[j]положительным, отрицательным или равным нулю.
Так как Вы находитесь в пабе, то штрафом за неправильный ответ будет употребление дополнительной пинты пива. Вы беспокоитесь, что это может негативно повлиять на Вас при участии в конкурсе на следующий день, и у Вас нет желания проверять на корректность теорию пика Баллмера. К счастью, друзья разрешили Вам пользоваться ноутбуком. Поскольку Вы больше доверяете Вашим способностям программировать, нежели математике, то было решено написать программу, которая поможет сыграть в игру.
Входные данные
Каждый тест состоит из нескольких строк. Первая строка каждого теста содержит два числа n и k (1 ≤ n, k ≤ 10^5) - количество элементов в последовательности и число раундов в игре. Вторая строка содержит n целых чисел x[i] - начальные значения последовательности (-100 ≤ x[i] ≤ 100 для i = 1, 2,..., n). Каждая из следующих k строк описывает команду, начинающуюся заглавной буквой 'C' или 'P'. Если это буква 'C', то строка содержит команду замены, за буквой следуют два числа i и v, указывающих на то что x[i] необходимо заменить на v (1 ≤ i ≤ n и -100 ≤ v ≤ 100). Если это буква 'P', то строка задает команду умножения, за буквой следуют два числа i и j - необходимо вычислить произведение от x[i] до x[j] включительно (1 ≤ i ≤ j ≤ n). Каждый тест содержит как минимум одну команду умножения.
Выходные данные
Для каждого теста вывести одну строку, содержащую ответы на все команды умножения. i-ый символ строки является результатом i-ой команды умножения. Если произведение положительно, то вывести символ '+' (плюс); если произведение отрицательно, то вывести '-' (минус); если произведение равно нулю, то вывести 0 (ноль).
Пример
4 6 -2 6 0 -1 C 1 10 P 1 4 C 3 7 P 2 2 C 4 -5 P 1 4 5 9 1 5 -2 4 3 P 1 2 P 1 5 C 4 -5 P 1 5 P 4 5 C 3 0 P 1 5 C 4 -5 C 4 -5
0+- +-+-0