Dữ liệu vào

Dòng đầu tiên chứa kích thước của dãy $N$.

Dòng thứ hai chứa $A_1, A_2, \ldots, A_N$.

Dòng thứ ba chứa số lượng truy vấn $M$.

$M$ dòng tiếp theo, mỗi dòng chứa một truy vấn.

• $1 \le N, M \le 100{,}000$
• $1 \le A_i, y \le 10^9+6$
• $1 \le x \le |A|$
• $1 \le l \le r \le |A|$
• $0 \le z \le |A|$

Dữ liệu ra

Đối với truy vấn loại 1 và loại 5, in ra một kết quả trên mỗi dòng theo thứ tự.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

6
3
24
0
78

Dữ liệu vào 2

10
5 4 3 5 4 1 5 4 3 1
15
2 8 580347
4 6 503576
1 2 5
5 8 11
1 2 6
4 7 565239
3 6
3 11
3 3
2 9 674360
1 1 6
2 2 589693
4 5 236488
1 8 9
5 2 7

Dữ liệu ra 2

60
4
107
788510349
0
6