+ محدودیت زمان: ۱۰ ثانیه + محدودیت حافظه: ۱۰۲۴ مگابایت ---------- عمو که دیگر حال داستان سرایی ندارد، صورت سوال را بدون هیچ گونه داستانی برای شما میگوید: او یک آرایه $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*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 ```