Enigmatic Device 2023

드디어 외계인이 지구를 방문한다고 한다! 외계인들은 지구의 현재 기술로는 만들 수 없는 Enigmatic Device™ 장치를 가져온다고 한다. 전 세계 과학자들도 이를 믿고 있고, 온갖 언론 매체에 기사가 실렸다.

이 장치는 정수 수열 $\\{a\_i\\}$를 초기 입력으로 받는다. 그다음부터는 다음의 두 가지 연산을 수행할 수 있다.

1. 구간 $\[l;r]$을 입력받아 $l$ 이상 $r$ 이하의 모든 정수 $i$에 대해 $a\_i$의 값을 $a\_i^2\bmod 2023$로 바꾼다.
2. 구간 $\[l;r]$을 입력받아 $l$ 이상 $r$ 이하의 모든 정수 $i$에 대한 $a\_i$의 값의 합을 출력한다.

이 장치의 놀라운 점은 $5$초 이내에 길이 $500 000$의 수열에 대해 이러한 연산을 $500 000$번 할 수 있다는 것이다. 지구상의 누구도 지금까지 이를 이루어내지 못했다.

하지만 외계인을 믿지 않는 Bojan은 이 모든 것이 그저 누군가가 주식으로 떼돈을 벌기 위해 뿌린 헛소문이라고 생각한다. 이를 증명하기 위해 그는 당신에게 이 장치를 따라하는 프로그램을 만들어 달라고 부탁했다.

정수 수열 $a\_i$와 연산의 순서가 주어졌을 때, Enigmatic Device™를 따라 하는 프로그램을 작성하시오.

첫 번째 줄에는 수열의 길이 $n$이 주어진다. ($1\le n\le 500 000$)

두 번째 줄에는 $n$개의 정수 $a\_i$가 주어진다. ($0\le a\_i\le 2022$)

세 번째 줄에는 연산의 횟수 $m$이 주어진다. ($1\le m\le 500 000$)

네 번째 줄부터 $m$개의 줄에 걸쳐서, 각 줄에 하나의 연산이 주어진다. $j$번째 연산은 연산의 종류 $k\_j$와 구간의 양 끝점 $l\_j$와 $r\_j$로 이루어져 있다. ($1\le k\_j\le 2$, $1\le l\_j\le r\_j\le n$) $k\_j = 1$이면 1번 연산, $k\_j = 2$이면 2번 연산을 의미하며, 2번 연산은 하나 이상 주어진다.

각각의 2번 연산에 대한 출력값을 한 줄에 하나씩 순서대로 출력한다.