Positivo, negativo y cero
Quien más quien menos sabe que en el mundo de las matemáticas la complejidad de demostrar una afirmación puede cambiar muchísimo ante cambios pequeños del enunciado.
Por ejemplo, es más o menos sencillo demostrar que existen infinitas ternas de números positivos que cumplen x2 + y2 = z2 pero costó más de 300 años demostrar que si en lugar de un 2 ponemos cualquier otro número mayor, entonces no existe ninguna terna que lo cumpla fuera de las triviales como (1,0,1)*.
En el mundo de la algoritmia y la resolución de problemas ocurre algo similar. Por ejemplo es bastante sencillo determinar si, dado un grafo, se puede encontrar un recorrido que pase por todas las aristas sin repetir ninguna pero es tremendamente costoso saber si hay un recorrido que pase por todos los vértices sin repetir ninguno.
Hay ejemplos más fáciles de ver, al alcance de cualquiera con un poco de sentido común. Por ejemplo, saber si un número es la raiz cuadrada de otro no requiere saber hacer raíces cuadradas, sino que basta con saber multiplicar; conocer el dígito menos significativo de un número elevado a otro no requiere calcular el valor completo; incluso saber cuál es el último dígito del factorial requiere únicamente comparaciones.
El último ejemplo que mencionaremos es el de la multiplicación de números enteros: para saber si al multiplicar un puñado de números el resultado dará positivo, negativo o cero, no se necesita hacer ninguna multiplicación.
Entrada
La entrada está compuesta por distintos casos de prueba, cada uno ocupando varias líneas.
La primera línea de cada caso tiene dos números: el primero, N, indica cuántos valores hay que considerar y el segundo cuántas operaciones C se realizan (ambos entre 1 y 300.000).
La siguiente línea contiene N valores entre -1000 y 1000. Tras ella vienen C líneas con las distintas operaciones que pueden tener el siguiente formato:
- C pos val: indica que el valor que ocupa la posición pos (entre 1 y N) debe cambiarse a val.
- ? a b: indica que se quiere analizar el producto de todos los valores entre a y b (1 ≤ a < b ≤ N) para determinar si el resultado es positivo, negativo o cero.
La entrada termina con una línea con dos ceros que no debe procesarse.
Salida
Por cada caso de prueba se escribirá una única línea con tantos caracteres como operaciones de tipo ? haya en el caso. El resultado de la operación será 0 si la multiplicación del intervalo de números dio 0, + si dio un número positivo y - si fue negativo.
Entrada de ejemplo
5 4 0 3 4 3 5 ? 1 5 ? 2 5 C 2 -3 ? 2 5 6 1 -1 1 -1 1 -1 1 C 1 2 6 1 -1 1 -1 1 -1 1 ? 1 6 0 0
Salida de ejemplo
0+- -