시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 (추가 시간 없음) 1024 MB (추가 메모리 없음)5741167928.114%

문제

길이 $N$인 수열 $A$이 있다. 당신은 이 수열에 총 $M$번의 연산을 수행할 것이다.

하나의 연산은 두 정수 $i$와 $x$로 나타난다. 이 연산은 $A$의 $i$번째 원소를 $x$로 바꾼다는 뜻이다.

각각의 연산을 차례로 수행한 이후 $A$가 양의 등차수열인지, 양의 등비수열인지 혹은 둘 다 아닌지 판별해보자.

  • 등차수열이란 $2 \le i \le N$인 모든 $i$에 대해 $A_{i}-A_{i-1}$이 일정한 수열을 말한다.
  • 등비수열이란 $2 \le i \le N$인 모든 $i$에 대해 $\frac{A_{i}}{A_{i-1}}$가 일정한 수열을 말한다.
  • 양의 등차수열이란 $A_{i}-A_{i-1}$이 양의 정수인 등차수열을 말한다.
  • 양의 등비수열이란 $\frac{A_{i}}{A_{i-1}}$가 양의 정수인 등비수열을 말한다.

입력

첫째 줄에 수열의 길이 $N$과 연산의 개수 $M$이 주어진다. $(3 \leq N \leq 300\,000, 1 \leq M \leq 300\,000)$

둘째 줄에 수열 $A$의 원소가 차례로 주어진다. $(1 \leq A_i \leq 10^{18})$

셋째 줄부터 $M$개의 줄에 연산 $i$ $x$가 한 줄에 하나씩 주어진다. $(1 \leq i \leq N, 1 \leq x \leq 10^{18})$

출력

각각의 연산을 수행한 이후 $A$가 양의 등차수열이면 +를, 양의 등비수열이면 *를, 둘 다 아닌 경우 ?를 한 줄에 하나씩 출력한다.

예제 입력 1

4 3
1 2 3 4
1 1
3 4
4 8

예제 출력 1

+
?
*

예제 입력 2

3 4
9999999998 9999999999 10000000000
2 5000000000
1 2500000000
2 10000000000
1 10000000000

예제 출력 2

?
*
?
*

출처

High School > 선린인터넷고등학교 > 2022 선린 정보 알고리즘경시대회 B번