E. Хатан хаан шиг Дуфф

хугацааны хязгаарлалт 7 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Дуфф бол өөрийн Андарз Гу улсдаа хатан хаан. Тэр өрсөлдөөнт програмчлалын шүтэн бишрэгч. Энэ нь тэр өөрийн сайд Малекийг хараад түүнд $n$ эерэг бүхэл тоонуудаас тогтох $a_{1}, a_{2}, ..., a_{n}$ дарааллыг өгч түүнд $q$ даалгавар гүйцэтгэж өгөхыг хүссэн шалтгаан юм.

Энд хоёр төрлийн даалгавар байна:

  1. $l, r$ ба $k$ тоонууд өгөгдсөн ба Малек $l ≤ i ≤ r$ бүрийн хувьд гүйцэтгэх ёстой (, $a$ ба $b$ тоонуудын хоёртын битүүдийн OR үйлдэл).
  2. $l, r$ ба $k$ тоонууд өгөгдсөн ба Малек түүнд $a_{l}, a_{l + 1}, ... , a_{r}$ дарааллын оноог хэлж өгөх ёстой.

$b_{1}, ..., b_{k}$ дарааллын оноо гэдэг нь үүний ялгаатай Кештакуудын тоо. Эерэг бүхэл тоо $w$ нь зөвхөн дараах нөхцөлд энэ дарааллын Кэштак болно: хэрвээ байх $b_{i_{1}}, b_{i_{2}}, ... , b_{i_{x}}$ (хоосон байж болно) гэж тэмдэглэх $b$-ийн дэд дараалал оршин байвал. Хэрвээ энэ дэд дараалал хоосон байвал $w = 0$ байна.

Дуффээс ялгаатай нь Малек програмчлагч биш. Энэ нь түүнд таны тусламж хэрэгтэй болсон шалтгаан. Түүнд эдгээр даалгаваруудыг гүйцэтгэж өгч туслана уу.

Оролт

Оролтын эхний мөрөнд хоёр бүхэл тоон утга $n$ ба $q$ ($1 ≤ n ≤ 2 × 10^{5}$ ба $1 ≤ q ≤ 4 × 10^{4}$) байна.

Оролтын хоёр дахь мөрөнд зайгаар тусгаарлагдсан $n$ бүхэл тоон утга $a_{1}, a_{2}, ..., a_{n}$ байх ба ($1 ≤ i ≤ n$ бүрийн хувьд $0 ≤ a_{i} ≤ 10^{9}$) байна.

Дараагийн $q$ мөрөнд даалгаваруудыг агуулна. Мөр бүр $t$ ($1 ≤ t ≤ 2$) бүхэл тоон утгаар эхлэх ба харгалзах даалгаварын төрөл байна. Хэрвээ $t = 1$ байвал уг мөрөнд дахиад гурван бүхэл тоон утга $l, r$ ба $k$ байна. Бусад тохиолдолд уг мөрөнд дахиад хоёр бүхэл тоон утга $l$ ба $r$ ($1 ≤ l ≤ r ≤ n$ ба $0 ≤ k ≤ 10^{9}$) байна.

Гаралт

Хоёр дахь төрлийн даалгавар бүрийн хариултыг нэг мөрөнд хэвлэ.

Орчуулсан: Г.Мэндбаяр

Жишээ тэстүүд

Оролт
5 5
1 2 3 4 2
2 1 5
1 2 2 8
2 1 5
1 1 3 10
2 2 2
Гаралт
8
16
1

Тэмдэглэл

Эхний даалгаварт бид $1, 2, 3, 4, 2$ дарааллын бүх Кештакуудыг буюу: $0, 1, 2, 3, 4, 5, 6, 7$ хүссэн.

Гурав дахь даалгаварт бид $1, 10, 3, 4, 2$ дарааллын бүх Кештакуудыг буюу: $0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15$ хүссэн.

Тав дахь даалгавар дээр бид $0$ дарааллын бүх Кештакуудыг буюу $0$-г хүссэн.

Сэтгэгдлүүдийг ачааллаж байна...