30916번 - 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번 연산에 대한 출력값을 한 줄에 하나씩 순서대로 출력한다.

제한

힌트