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

---

عمو که دیگر حال داستان سرایی ندارد، صورت سوال را بدون هیچ گونه داستانی برای شما میگوید:

او یک آرایه \(n\) عضوی به نام \(a\) دارد که تمامی عناصر آن فرد هستند. سپس او \(q\) درخواست از شما میکند که به یکی از تو فرم زیر می‌باشند.

1. اعداد \(l, r, x\) به ترتیب داده می‌شوند. سپس به ازای هر \(l \leq i \leq r\) مقدار عنصر \(a_i\) به اندازه \(x\) واحد زیاد کنید. همچنین به علت علاقه عمو به اعداد زوج، تضمین میکند که \(x\) حتما زوج است.
2. اعداد \(l, r\) به ترتیب داده می‌شوند. سپس شما باید به عمو ضرب \(a_i\) که \(l \leq i \leq r\) است را بگویید. عمو به علت کهولت سن توانایی پردازش اعداد بزرگ را ندارد، به همین علت شما کافی است جواب را باقی مانده به پیمانه \(2^{20}\) بگویید.

ورودی

در خط اول ورودی شامل دو عدد \(n\) و \(q\) است که به ترتیب نشانگر سایز آرایه و تعداد درخواست ها می‌باشد. در خط بعدی \(n\) عدد داده میشود که اعداد آرایه عمو هستند. در \(q\) خط بعدی در هر خط یک پرسش داده میشود. در ابتدای هر پرسش عدد \(t\) می‌آید که نوع درخواست را مشخص می‌کند. سپس با توجه به نوع درخواست یکی از دو حالت زیر داده میشود

1. 1 l r x که درخواست از نوع اول را نشان میدهد.
2. 2 l r که درخواست از نوع دوم را نشان میدهد.

خروجی

به ازای هر درخواست نوع دوم جواب را چاپ کنید.

محدودیت‌ها

\[1 \leq n, q \leq 2 \times 10^5\] \[1 \leq ai < 2^{20}\] \[1 \leq l \leq r \leq n\] \[0 \leq x \leq 2^{20}\]

ورودی نمونه ۱

10 10
969575 741825 24903 1047319 450475 256145 1045323 479255 810659 768323
1 5 6 3034
2 1 10
2 1 9
2 1 4
1 3 6 126904
2 5 5
2 9 9
1 7 7 853094
1 4 9 1025178
2 5 8

خروجی نمونه ۱

1045541
1012343
558151
580413
810659
527353