Dấu của tích trên đoạn (Interval Product)

Nguồn: UVa

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho dãy $X_1,X_2,\ldots,X_N$. Có $K$ lệnh. Lệnh C I V thay đổi $X_I$ thành $V$. Lệnh P I J hỏi dấu của tích $X_I X_{I+1}\cdots X_J$: dương, âm hay bằng $0$.

Input

• Dòng đầu chứa $N$ và $K$.
• Dòng thứ hai chứa $N$ số nguyên $X_i$ với $-100 \le X_i \le 100$.
• Mỗi trong $K$ dòng tiếp theo là C I V hoặc P I J. Với lệnh C, $1 \le I \le N$ và $-100 \le V \le 100$. Với lệnh P, $1 \le I \le J \le N$. Có ít nhất một lệnh P.

Output

In một dòng gồm các ký tự theo thứ tự các lệnh P: + nếu tích dương, - nếu tích âm và 0 nếu tích bằng $0$.

Subtask

• 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$.

Ví dụ

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+-

Giải thích

Sau C 1 10, đoạn $[1,4]$ vẫn chứa số $0$ ở vị trí $3$, nên ký tự đầu là 0. Sau C 3 7, lệnh P 2 2 chỉ xét số $6>0$ nên cho +. Cuối cùng $X_4=-5$, tích $10\cdot6\cdot7\cdot(-5)$ âm nên cho -.