D. Иахуб ба XOR үйлдлүүд

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

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

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

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

Иахуб түүх ярих дургүй нэгэн. Тиймээс тэрээр энэ бодлого чамаас юу асууж байгааг шууд хэлж байна.

Чамд $n$ багана болон $n$ мөртэй $a$ матриц өгөгджээ. Эхлээд матрицын бүх гишүүд $0$ байв. Мөрүүд $1$, $2$, ..., $n$ гэж дугаарлагдсан ба баганууд $1$, $2$, ..., $n$ гэж дугаарлагдсан байна. $i$ дугаар мөр болон $j$ дугаар баганын огтлолд байрлах тоог $a_{i, j}$ гэж тэмдэглэе.

$x_{0} ≤ i ≤ x_{1}$, $y_{0} ≤ j ≤ y_{1}$ байх бүх $a_{i, j}$-уудаас тогтох дэд матрицыг $(x_{0}, y_{0}, x_{1}, y_{1})$ гэж тэмдэглэе.

Дараах үйлдлүүдийг гүйцэтгэдэг програм зохио:

  1. $Query(x_{0}, y_{0}, x_{1}, y_{1})$: $(x_{0}, y_{0}, x_{1}, y_{1})$ дэд матрицын бүх элементүүдийн XOR нийлбэрийг хэвлэнэ.
  2. $Update(x_{0}, y_{0}, x_{1}, y_{1}, v)$: $(x_{0}, y_{0}, x_{1}, y_{1})$ дэд матрицын бүх гишүүн бүрийг $v$-тэй XOR үйлдэл хийнэ.

Оролт

Эхний мөрөнд $n$ ($1 ≤ n ≤ 1000$) ба $m$ ($1 ≤ m ≤ 10^{5}$) гэсэн хоёр бүхэл тоо байна. $m$ нь гүйцэтгэх үйлдлийн тоог илэрхийлнэ. Дараагийн $m$ мөр бүрт үйлдлийн төрлөөс хамааран тав эсвэл зургаан бүхэл тоо байна.

Хэрэв $i$ үйлдэл "$Query$" байвал эхний тоо нь нэгийн тоо байх болно. Түүний ард $x_{0}$, $y_{0}$, $x_{1}$, $y_{1}$ гэсэн дөрвөн бүхэл тоо байна. Хэрэв $i$ дэх үйлдэл "$Update$" байвал эхний тоо нь хоёрын тоо байх болно. Түүний ард $x_{0}$, $y_{0}$, $x_{1}$, $y_{1}$, $v$ гэсэн таван бүхэл тоонууд байна.

Үйлдэл бүрийн хувьд дараах нөхцлүүд биелнэ: $1 ≤ x_{0} ≤ x_{1} ≤ n$, $1 ≤ y_{0} ≤ y_{1} ≤ n$.

"$Update$" үйлдэл дээр мөн дараах нөхцөл биелнэ: $0 ≤ v < 2^{62}$.

Гаралт

"$Query$" үйлдэл бүрийн хариуг нэг мөрөнд хэвлэ.

Орчуулсан: Бат-Од

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

Оролт
3 5
2 1 1 2 2 1
2 1 3 2 3 2
2 3 1 3 3 3
1 2 2 3 3
1 2 2 3 2
Гаралт
3
2

Тэмдэглэл

Эхний гурван үйлдлийг хийсний дараа матриц дараах байдалтай болно:

1 1 2
1 1 2
3 3 3

Дөрөв дэх үйлдэл: $1\ xor\ 2\ xor\ 3\ xor\ 3 = 3$.

Тав дахь үйлдэл: $1\ xor\ 3 = 2$.

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