성 대표 선발전이 끝난 후, White는 오랜 실망감에 빠졌습니다. 그녀는 자신의 성적에서 어떤 희망도 찾을 수 없었습니다. 그럼에도 White는 NOI를 앞둔 마지막 훈련을 이어갔습니다. 정규 훈련 외에도 그녀는 OI 시절 동안 배울 기회가 없었던 주제들을 탐구하기 시작했습니다 — 작별을 고하기 전에 더 이상 후회가 남지 않기를 바라면서 말입니다.

어지러운 생각들을 떨쳐내고, White는 문득 눈앞의 문제 하나에 집중했습니다. 평범하고 지루한 자료구조 문제였습니다 —

White에게는 $n$개의 정수로 이루어진 수열 $a_1, a_2, \dots, a_n$이 있습니다. 그녀는 이 수열에 $q$번의 연산을 수행할 것입니다. 각 연산은 다음 세 가지 유형 중 하나입니다:

• 1 l r v — 구간 $[l, r]$의 각 원소에 $v$를 더합니다.
• 2 l r v — 구간 $[l, r]$의 각 원소를 $v$로 변경합니다.
• 3 l r — $\sum_{i=l}^r (\min_{j=l}^i a_j) \times (\max_{j=l}^i a_j)$를 $2^{64}$로 나눈 나머지를 질의합니다.

당신의 임무는 모든 연산을 시뮬레이션하고 모든 질의의 결과를 출력하는 것입니다.

입력

입력의 첫째 줄에는 원소의 개수와 연산의 개수를 나타내는 두 정수 $n, q$ ($1 \le n, q \le 2 \times 10^5$)가 주어집니다.

둘째 줄에는 초기 원소를 나타내는 $n$개의 정수 $a_1, a_2, \cdots, a_n$ ($0 \le a_i \le 10^9$)이 주어집니다.

다음 $q$개의 줄 각각은 세 가지 형식 중 하나로 연산을 설명합니다:

• 1 l r v ($1 \le l \le r \le n, -10^9 \le v \le 10^9$), 덧셈 연산을 나타냅니다.
• 2 l r v ($1 \le l \le r \le n, 1 \le v \le 10^9$), 대입 연산을 나타냅니다.
• 3 l r ($1 \le l \le r \le n$), 질의 연산을 나타냅니다.

전체 과정 동안 모든 $1 \le i \le n$에 대해 $0 \le a_i \le 10^9$임이 보장됩니다.

출력

각 질의 연산마다 한 줄에 정수 하나, 즉 질의 결과를 $2^{64}$로 나눈 나머지를 출력하세요.

예제

입력

5 8
2 3 5 4 1
3 1 5
3 2 4
2 4 5 2
3 1 5
3 2 4
1 1 2 5
3 1 5
3 2 4

출력

35
39
40
34
177
120

입력

10 20
1 2 3 4 5 6 7 8 9 10
1 1 10 1
3 1 5
3 2 9
3 8 10
1 2 5 10
3 1 5
3 2 9
3 8 10
1 5 9 -5
3 1 5
3 2 9
3 8 10
1 2 5 -10
3 1 5
3 2 9
3 8 10
1 5 9 5
3 1 5
3 2 9
3 8 10

출력

40
156
270
120
1202
270
118
831
80
33
61
80
40
156
270

노트

첫 번째 테스트케이스에서:

원래 수열은 2 3 5 4 1입니다. 세 번째 연산 후에는 2 3 2 2 1이 되고, 여섯 번째 연산 후에는 7 8 7 7 6이 됩니다.

첫 번째 질의의 답은 $\sum_{i=1}^5 (\min_{j=1}^i a_j) \times (\max_{j=1}^i a_j) = 2 \times 2 + 2 \times 3 + 2 \times 5 + 2 \times 5 + 1 \times 5 = 35$입니다.

두 번째 질의의 답은 $\sum_{i=2}^4 (\min_{j=2}^i a_j) \times (\max_{j=2}^i a_j) = 3 \times 3 + 3 \times 5 + 3 \times 5 = 39$입니다.