Зениа програм хангамжаар суралцаж эхлэж байгаа. Түүнд $2^n$ урттай $a_1, a_2, ... , a_m$ дараалал өгөгдөнө. Тэр бит үйлдэл суралцаж байгаа ба бит үйлдлийг илүү сайн ойлгохын тулд $a$ дараалалаас $v$ гэсэн утгыг гаргаж авахыг хүссэн.

$v$-г гаргаж авахын тулд хэд хэдэн үйлдлийг гүйцэтгэдэг. Эхний алхам нь Зениа $a_1$ or $a_2$, $a_3$ or $a_4$, ... , $a_{2^n-1}$ or $a_{2^n}$ шинэ дараалалийг үүсгэнэ. Өөрөөр хэлбэл $a$ дараалалын хөрш хоёр элементийн хооронд $OR$ үйлдэл хийнэ гэсэн үг. Хоёр дахь алхам нь эхний алхамаас үүссэн дараалалын хөрш хоёр элементийн хооронд $XOR$ үйлдэл хийнэ. Гуравдугаар алхам нь хоёрдугаар алхамаас үүссэн дараалалын хөрш хоёр элементийн хооронд $OR$ үйлдэл гүйцэтгэнэ. Гэх мэт $XOR$ болон $OR$ үйлдлийг ээлжлэн хийнэ. Ингээд хамгийн сүүлд ганц тоо үлдэх ба энэ нь манай $v$ тоо юм.

Дараах жишээг авч үзье. $a=(1,2,3,4)$ гэсэн дараалалын хувьд $(1,2,3,4)$ → $(1 or 2 = 3, 3 or 4 = 7)$ → $(3 xor 7 = 4)$ болно. Иймд манай $v = 4$ юм.

Зениад анхны дараалалыг өгсөн. Гэвч шууд $v$-г олоход хялбар байх учраас нэмж $m$ ширхэг хүсэлт өгсөн байна. Хүсэлт бүр $p,b$ гэсэн хоёр бүхэл тооноос тогтоно. $p, b$ нь $a_p=b$ гэсэн үг. Өөрөөр хэлбэл $a$ дараалалын $p$ дахь элементэд $b$ гэсэн утга онооно. Дараа нь хүсэлт болгоны хувьд шинээр үүссэн $a$ дараалалын $v$-г бодож гаргана.

Оролт

Эхний мөрөнд $m$ болон $n$ бүхэл тоо өгөгдөнө ($1 ≤ n ≤ 17$; $1 ≤ m ≤ 10^5$). Дараагийн мөрөнд $2^n$ урттай бүхэл тоон $a_1, a_2, ... , a_{2^n}$ дараалал өгөгдөнө ($0 ≤ a_i < 230$). Дараагийн $m$ ширхэг мөр бүрт $p, b$ ($1 ≤ p_i ≤ 2^n$; $0 ≤ b_i < 2^{30}$) хүсэлтүүд өгөгдөнө.

Гаралт

$m$ хүсэлт бүрийн хувьд харгалзах $v$-г хэвлэ.

For more information on the bit operations, you can follow this link: http://en.wikipedia.org/wiki/Bitwise_operation$