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

سینا به عرفان یک آرایه از $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$