Hạ Trần

Cho dãy số nguyên không âm $a_1,\dots ,a_n$. Hỗ trợ các thao tác trên đoạn đóng $[l,r]$:

• $1$ $l$ $r$ $x$: thay mỗi $a_i$ bằng $\min (a_i,x)$.
• $2$ $l$ $r$: tìm giá trị lớn nhất trên đoạn.
• $3$ $l$ $r$: tính tổng các phần tử trên đoạn.

Input

• Dòng đầu chứa $n$.
• Dòng thứ hai chứa $n$ phần tử ban đầu.
• Dòng thứ ba chứa số thao tác $m$.
• $m$ dòng sau mô tả các thao tác.

Output

• Với mỗi thao tác loại $2$ hoặc $3$, in kết quả trên một dòng.

Constraints

• $1\le n,m\le 10^6$.
• $0\le a_i,x<2^{31}$.
• $1\le l\le r\le n$; tổng được tính bằng số nguyên $64$ bit.

Scoring

• Subtask $1$ ($50\%$ số điểm): $n,m\le 3000$.
• Subtask $2$ ($50\%$ số điểm): Không có giới hạn bổ sung.

Example

5
9 5 9 1 7
6
2 1 5
3 1 5
1 1 4 6
3 1 5
1 3 5 4
2 2 5

9
31
25
5