Sir Nataflet

Cerință

Se dă un șir de numere întregi $a_1, a_2, \dots, a_n$ de lungime $n$ și un număr $x$, de asemenea se garantează că fiecare element $a_i$ este impar.

Asupra acestui șir se vor efecta două tipuri de operații:

1. $l$, $r$, $val$ - adaugă $val$ la toate elemente $a_l, \dots, a_r$ unde $val$ este par;
2. $l$, $r$, $k$ - găsește produsul numerelor $a_l, \dots, a_r$ modulo $2^{k}$.

Date de intrare

Pe prima linie se găsesc două numere întregi, $n$ și $q$ reprezentând lungimea șirului și numărul de operații.
Cea dea doua linie conține șirul de numere $a_1, a_2, \dots, a_n$.
Următoarele $q$ linii corespund operațiilor, fiecare având una dintre cele 2 forme:

• 1 l r val reprezentând operațiile de primul tip;
• 2 l r k reprezentând operațiile de al doilea tip.

Date de ieșire

Pentru fiecare operație de tipul 2 afișati o linie cu răspunsul acesteia.

Restricții și precizări

• $1 \leq n, q \leq 200 \ 000$;
• $1 \leq a_i, val \leq 2^{20}$;
• $k \leq 20$

Exemplu

stdin

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

stdout

5
119
558151
23357
3
1