• محدودیت زمان: ۳ ثانیه
• محدودیت حافظه: ۵۱۲ مگابایت

سینا به عرفان یک آرایه از $n$ عدد هديه داده است. ایلیا از عرفان می‌خواهد $Q$ عمليات روی آرایه انجام دهد. هر عملیات به یکی از ۴ حالت زیر است:

1. $0 \, l \, r : \sum a_i \quad (l \leq i \leq r)$
2. $1 \, l \, r \, v : a_i := a_i \oplus v \quad (l \leq i \leq r)$
3. $2 \, l \, r \, v : a_i := a_i \text{ and } v \quad (l \leq i \leq r)$
4. $3 \, l \, r \, v : a_i := a_i \text{ or } v \quad (l \leq i \leq r)$

عرفان باید عملیات های گفته شده را روی اعضای ارایه اعمال کند و در ازای هر نوع عملیات از نوع $0$ جمع اعداد درون بازه خواسته شده را به ایلیا بگوید. اما از انجایی که عرفان خسته شده است، از شما می خواهد پاسخ سوالات ایلیا را بدهید.

ورودی🔗

در سطر اول به ترتیب عدد $n$ که طول آرایه است و در سطر بعد $n$ عدد که $i$امین شان $a_i$ است می‌آید. در سطر بعد $Q$ می‌آید و در $Q$ سطر بعدی در هر سطر یک عملیات از ۴ عمليات ذکر شده می‌آید. $1 \leq n, Q \leq 100\,000$ $1 \leq l \leq r \leq n$ $1 \leq a_i , v \leq 1000\,000$

خروجی🔗

در ازای هر عملیات از نوع $0$ جمع اعداد درون بازه خواسته شده را خروجی دهید.

مثال🔗

ورودی نمونه ۱🔗

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

خروجی نمونه ۱🔗

31
24

نتیجه اعمال هر عملیات:

1. $a : [1, 10, 12, 8]$
2. $a : [9, 10, 12, 8]$
3. $print : 9 + 10 + 12 = 31$
4. $a : [8, 8, 8, 8]$
5. $print : 8 + 8 + 8 = 24$