시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 127 52 35 37.634%

문제

길이 $N$의 수열 $A$가 주어집니다. 이 수열에 아래 세 가지 종류의 쿼리를 처리하는 프로그램을 만들어 봅시다.

  • $1$ $l$ $r$: $l \le i \le r$인 모든 $A_i$를 $f(A_i)$로 바꿉니다.
  • $2$ $l$ $r$: $l \le i \le r$인 모든 $A_i$를 $g(A_i)$로 바꿉니다.
  • $3$ $x$: $A_x$를 출력합니다. 답이 매우 커질 수 있으니, $100 003$으로 나눈 나머지를 출력합니다.

단, $f(x)=2x^2 -1$, $g(x) = 4x^3 - 3x$입니다.

입력

첫 줄에는 수열의 길이 $N$과 쿼리의 수 $Q$가 주어집니다.

둘째 줄에는 수열 $A$의 초기 상태 $A_1, A_2, \cdots, A_N$이 주어집니다.

셋째 줄부터 $Q$개의 줄에는 각 쿼리에 대한 정보가 위의 형태 ($t$ $l$ $r$ 또는 $t$ $x$)로 순서대로 주어집니다.

출력

모든 3번 쿼리에 대해, 그 답을 한 줄에 하나씩 출력합니다.

제한

  • $1 \le N \le 5 \times 10^5$
  • $1 \le Q \le 5 \times 10^5$
  • $1 \le A_i \le 10^5$
  • 모든 쿼리에 대해, $1 \le t \le 3$, $1 \le l \le r \le N$, $1 \le x \le N$
  • 3번 쿼리가 적어도 하나는 주어집니다.

서브태스크

번호 배점 제한
1 30

$N \le 100$, $Q \le 100$

2 10

$A_1 = A_2 = \cdots = A_N = 1$

3 40

$t \neq 2$, $A_1 = A_2 = \cdots = A_N$

4 150

$1 \le t \le 2$이면 $l=1$, $r=N$

5 170

추가 제한 조건이 없습니다.

예제 입력 1

3 3
1 2 3
1 1 3
2 1 3
3 2

예제 출력 1

1351

채점 및 기타 정보

  • 예제는 채점하지 않는다.