cho.sh

등차수열? 등비수열?

아직 제출이 없습니다시간 제한2초메모리 제한1024 MB

문제

길이 NN인 수열 AA이 있다. 당신은 이 수열에 총 MM번의 연산을 수행할 것이다.

하나의 연산은 두 정수 ii와 xx로 나타난다. 이 연산은 AA의 ii번째 원소를 xx로 바꾼다는 뜻이다.

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

  • 등차수열이란 2≤i≤N2 \le i \le N인 모든 ii에 대해 A_i−A_i−1A\_{i}-A\_{i-1}이 일정한 수열을 말한다.
  • 등비수열이란 2≤i≤N2 \le i \le N인 모든 ii에 대해 A_iA_i−1\frac{A\_{i}}{A\_{i-1}}가 일정한 수열을 말한다.
  • 양의 등차수열이란 A_i−A_i−1A\_{i}-A\_{i-1}이 양의 정수인 등차수열을 말한다.
  • 양의 등비수열이란 A_iA_i−1\frac{A\_{i}}{A\_{i-1}}가 양의 정수인 등비수열을 말한다.

입력

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

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

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

출력

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