Setelah seleksi tim provinsi, White jatuh ke dalam kekecewaan yang panjang. Ia tidak dapat menemukan harapan apa pun dalam hasilnya. Meski begitu, White tetap melanjutkan pelatihan terakhirnya sebelum NOI. Selain pelatihan rutinnya, ia juga mulai menjelajahi topik-topik yang belum pernah sempat ia pelajari selama masa-masa OI-nya — berharap bahwa sebelum mengucapkan selamat tinggal, tidak akan ada lagi penyesalan.

Menepis pikiran-pikirannya yang melayang, White tiba-tiba memusatkan perhatian pada sebuah soal di hadapannya, sebuah soal struktur data yang polos dan membosankan —

White memiliki sebuah barisan yang terdiri dari $n$ bilangan bulat $a_1, a_2, \dots, a_n$. Ia akan melakukan $q$ operasi pada barisan ini. Setiap operasi merupakan salah satu dari tiga jenis berikut:

• 1 l r v — Tambahkan $v$ ke setiap elemen dalam interval $[l, r]$.
• 2 l r v — Ubah nilai setiap elemen dalam interval $[l, r]$ menjadi $v$.
• 3 l r — Tanyakan nilai $\sum_{i=l}^r (\min_{j=l}^i a_j) \times (\max_{j=l}^i a_j)$ modulo $2^{64}$.

Tugas Anda adalah menyimulasikan semua operasi dan mengeluarkan hasil dari semua kueri.

Masukan

Baris pertama masukan berisi dua bilangan bulat $n, q$ ($1 \le n, q \le 2 \times 10^5$), yang menyatakan banyaknya elemen dan banyaknya operasi.

Baris kedua berisi $n$ bilangan bulat $a_1, a_2, \cdots, a_n$ ($0 \le a_i \le 10^9$), yang menyatakan elemen-elemen awal.

Masing-masing dari $q$ baris berikutnya mendeskripsikan sebuah operasi, dalam salah satu dari tiga format:

• 1 l r v ($1 \le l \le r \le n, -10^9 \le v \le 10^9$), menyatakan operasi Tambah (Add).
• 2 l r v ($1 \le l \le r \le n, 1 \le v \le 10^9$), menyatakan operasi Penugasan (Assign).
• 3 l r ($1 \le l \le r \le n$), menyatakan operasi Kueri (Query).

Dijamin bahwa $0 \le a_i \le 10^9$ untuk setiap $1 \le i \le n$ selama keseluruhan proses.

Keluaran

Untuk setiap operasi Kueri, cetak sebuah bilangan bulat dalam satu baris — hasil kueri modulo $2^{64}$.

Contoh

Masukan

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

Keluaran

35
39
40
34
177
120

Masukan

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

Keluaran

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

Catatan

Pada kasus uji pertama:

Barisan aslinya adalah 2 3 5 4 1. Setelah operasi ketiga, barisan menjadi 2 3 2 2 1, dan setelah operasi keenam, barisan menjadi 7 8 7 7 6.

Untuk kueri pertama, jawabannya adalah $\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$.

Untuk kueri kedua, jawabannya adalah $\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$.