D. Васили-ын Мулти олонлог

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

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

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

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

Бодлогын зохиолч Васили-ын талаарх түүхүүд бичихээс залхсан учраас энэ удаад энгийн нэгэн бодлогын өгүүлбэр бичив.

Танд $q$ ширхэг асуулт болон Мулти олонлог $A$ өгөгдөх бөгөөд анхандаа уг Мулти олонлог нь зөвхөн $0$ гэсэн бүхэл тоог агуулж байв. Нийтдээ 3-н төрлийн асуултууд байна:

  1. "+ x" -- Мулти олонлог $A$ дээр бүхэл тоо $x$-г нэмж оруулна.
  2. "- x" -- Мулти олонлог $A$-аас бүхэл тоо $x$-ын нэг удаа хасна (хэрэв уг олонлогт 2 ширхэг $x$ бүхэл тоо байсан бол уг үйлдлийн дараа нэг $x$ нь олонлогтоо үлдэх юм). Мөн уг үйлдлийг хийхээс өмнө Мулти олонлог $A$ дотор дор хаяж нэг ширхэг $x$ бүхэл тоо оршин байна.
  3. "? x" -- танд $x$ бүхэл тоо өгөгдөх ба та -ын утгыг тооцоолох хэрэгтэй, өөрөөр хэлбэл бүхэл тоо $x$ болон Мулти олонлог $A$ доторх ямар нэгэн бүхэл тоо $y$-ын битийн онцгой OR (өөрөөр хэлбэл XOR) үйлдлийн хамгийн их утгыг олох юм.

Мулти олонлог гэдэг нь тэнцүү элементүүдийг агуулж болдог олонлогийг хэлнэ.

Оролт

Оролтын эхний мөрөнд бүхэл тоо $q$ ($1 ≤ q ≤ 200 000$) өгөгдөх ба энэ нь Васили-ын гүйцэтгэх ёстой асуултуудын тоог илэрхийлнэ.

Дараагийн $q$ ширхэг мөрийн мөр болгонд '+', '-' эсвэл '?' гэсэн 3 тэмдэгтийн аль нэг тэмдэгт мөн бүхэл тоо $x_{i}$ ($1 ≤ x_{i} ≤ 10^{9}$) өгөгдөнө. Мөн дор хаяж нэг ширхэг 3-р төрлийн асуулт өгөгдөх юм.

Бүхэл тоо $0$ нь $A$ олонлог дотор үргэлж байхыг анхаарна уу.

Гаралт

'?' гэсэн хэлбэртэй өгөгдсөн (өөрөөр хэлбэл 3-р төрлийн асуулт) асуулт бүрийн хувьд бүхэл тоо $x_{i}$ болон Мулти олонлог $A$ доторх ямар нэгэн бүхэл тооны битийн онцгой OR (өөрөөр хэлбэл XOR) үйлдлийн хамгийн их утгыг хэвлэнэ үү.

Орчуулсан: Баатархүү

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

Оролт
10
+ 8
+ 9
+ 11
+ 6
+ 1
? 3
- 8
? 3
? 8
? 11
Гаралт
11
10
14
13

Тэмдэглэл

Эхний 5-н асуултыг гүйцэтгэсний дараагаар Мулти олонлог $A$ нь $0$, $8$, $9$, $11$, $6$ болон $1$ гэсэн бүхэл тоонуудыг агуулна.

Түүнчлэн 6-дахь асуултын хариулт нь , , , болон гэсэн бүхэл тоонуудаас их бүхэл тоо нь буюу байх юм.

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