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

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

او یک آرایه $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