E. Инна ба хоёртын логик

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

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

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

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

Инна эмэгтэйчүүдийн логикын талаарх шог ярианаас залхсан, тиймээс тэр хоёртын логикыг хэрэглэж эхэлсэн.

Иннад $n$ ширхэг $a_{1}[1], a_{1}[2], ..., a_{1}[n]$ элементүүдээс бүрдсэн массив байна. Охин өөрийн хоёртын логикыг хөгжүүлэх дуртай учраас тэр $n$ үе шатнаас бүрдсэн дасгал хийдэг: эхний үед Инна $a_{1}$ массивын бүх тоонуудыг бичсэн, $i$-р $(i ≥ 2)$ үед охин $n - i + 1$ бүхэл тоонуудаас бүрдсэн $a_{i}$ массивын бүх тоонуудыг бичсэн; $a_{i}$ массивын $k$-р бүхэл тоо нь дараах байдлаар тодорхойлогдсон: $a_{i}[k] = a_{i - 1}[k] AND a_{i - 1}[k + 1]$. Энэ AND бол битийн хоёртын логик үйлдэл.

Дима Иннагийн чадварыг шалгахаар шийдсэн. Тэр Иннагаас массивыг өөрчлөхийг асуугаад, дасгалыг гүйцэтгээд одоогийн дасгалын үед бичсэн бүх элементүүдийн нийлбэрийг хэлнэ.

Асуултанд хариулахад Иннад тусал!

Оролт

Эхний мөр нь $n$, $m$ $(1 ≤ n, m ≤ 10^{5})$ хоёр бүхэл тоог агуулна. Эдгээр нь $a_{1}$ массивын хэмжээ ба Димагийн асуултуудын тоо. Дараагийн мөр нь анхны массивын элементүүд болох $n$ ширхэг $a_{1}[1], a_{1}[2], ..., a_{1}[n]$ $(0 ≤ a_{i} ≤ 10^{5})$ бүхэл тоонуудыг агуулна.

Дараагийн $m$ мөрүүд нь Димагийн асуултуудын тодорхойлолт болох хоёр бүхэл тоо агуулна. Асуулт бүр нь $p_{i}, v_{i}$ $(1 ≤ p_{i} ≤ n; 0 ≤ v_{i} ≤ 10^{5})$ хоёр бүхэл тоог агуулна. Энэ асуултанд Инна $a_{1}[p_{i}]$-г $v_{i}$-тэй тэнцүүлээд дараа нь дасгалыг гүйцэтгэх ёстой. Өөрчлөлтүүд нь асуултаас асуултад хадгалагдсан байгаа гэдгийг анхаарна уу.

Гаралт

Асуулт бүрийн хувьд Иннагийн хариултыг нэг мөрөнд хэвлэнэ

Орчуулсан: Даариймаа

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

Оролт
3 4
1 1 1
1 1
2 2
3 2
1 2
Гаралт
6
4
7
12
Сэтгэгдлүүдийг ачааллаж байна...