Interval Product

Source: UVa

Version: Phuoc Hung OJ Extended

Problem Statement

Given a sequence $X_1,X_2,\ldots,X_N$, process $K$ commands. C I V changes $X_I$ to $V$. P I J asks whether $X_I X_{I+1}\cdots X_J$ is positive, negative, or zero.

Input

• The first line contains $N$ and $K$.
• The second line contains $N$ integers $X_i$ with $-100 \le X_i \le 100$.
• Each of the next $K$ lines is C I V or P I J. For C, $1 \le I \le N$ and $-100 \le V \le 100$. For P, $1 \le I \le J \le N$. At least one P command is present.

Output

Print one line whose characters correspond to the P commands: + for a positive product, - for a negative product, and 0 for a zero product.

Subtasks

• Subtask 1 — 20%: $1 \le N,K \le 1000$.
• Subtask 2 — 30%: $1 \le N,K \le 50000$.
• Subtask 3 — 50%: $1 \le N,K \le 10^5$.

Examples

Input

4 6
-2 6 0 -1
C 1 10
P 1 4
C 3 7
P 2 2
C 4 -5
P 1 4

Output

0+-

Explanation

After C 1 10, range $[1,4]$ still contains the zero at position $3$, so the first character is 0. After C 3 7, P 2 2 examines only $6>0$, giving +. Finally $X_4=-5$, so $10\cdot6\cdot7\cdot(-5)$ is negative and gives -.