Polynomial and Easy Queries

You are given a sequence $A$ of length $N$. Write a program that processes the following three kinds of queries on this sequence.

• $1$ $l$ $r$: replace every $A_i$ with $f(A_i)$ for all $l \le i \le r$.
• $2$ $l$ $r$: replace every $A_i$ with $g(A_i)$ for all $l \le i \le r$.
• $3$ $x$: print $A_x$. The answer can grow very large, so print it modulo $100\,003$.

Here $f(x)=2x^2 -1$ and $g(x) = 4x^3 - 3x$.

The first line contains the length of the sequence $N$ and the number of queries $Q$.

The second line contains the initial state of the sequence, $A_1, A_2, \cdots, A_N$.

Each of the next $Q$ lines contains one query in the form above ($t$ $l$ $r$ or $t$ $x$), in order.

For every query of type 3, print its answer on a line.

• $1 \le N \le 5 \times 10^5$
• $1 \le Q \le 5 \times 10^5$
• $1 \le A_i \le 10^5$
• For every query, $1 \le t \le 3$, $1 \le l \le r \le N$, $1 \le x \le N$
• At least one query of type 3 is given.