E. Азтай хүсэлт

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

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

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

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

Пэтя азын тоонд их дуртай. Азын тоо нь зөвхөн $4$ ба $7$ гэсэн цифрүүдээс бүрдсэн эерэг бүхэл тоонууд юм. Жишээ нь $47$, $744$, $4$ нар нь азын тоо ба $5$, $17$, $467$ нар нь биш юм.

Пэтя гэртээ $n$ урттай $s$ тэмдэгт мөр авч иржээ. Тэмдэгт мөр дан азтай цифрүүдээс тогтоно. Цифрүүд зүүнээс баруун тийш $1$-ээс эхлэн дугаарлагджээ. Одоо Пэтя дараахь хэлбэрийн хүсэлтүүдийг гүйцэтгэнэ:

  • "switch l r" - цифрүүдийг солих ($l$-ээс $r$ хүртэлх дугаартай бүх цифрүүдийг эсрэгээр нь солино: $4$ байсан бол $7$ болгоно, харин $7$ байсан бол $4$-өөр солино.
  • "count" - $s$ тэмдэгт мөрийн үл буурах хамгийн урт дэд дарааллын уртыг олж хэвлэнэ.

$s$ тэмдэгт мөрийн дэд дараалал гэдэг нь $s$ тэмдэгт мөрийн зарим тэмдэгтүүдийг (эсвэл алийг нь ч биш) арилгах замаар үүсэж болох тэмдэгтийн дараалал юм. Тэмдэгт мөрийн гишүүн цифр бүр өмнөх цифрээсээ багагүй байвал тухайн тэмдэгт мөрийг үл буурах гэнэ.

Пэтяд хүсэлтүүдийг гүйцэтгэхэд нь туслаарай.

Оролт

Эхний мөрөнд тэмдэгт мөрийн урт болох хүсэлтийн тоог илэрхийлэх $n$ ба $m$ ($1 ≤ n ≤ 10^{6}, 1 ≤ m ≤ 3 \cdot 10^{5}$) тоонууд байна. Хоёр дахь мөрөнд Пэтягийн авч ирсэн тэмдэгт мөр болох $n$ ширхэг азтай цифр хоорондоо зайгүйгээр өгөгдөнө. Дараагийн $m$ мөрөнд хүсэлтүүд дээр дурдсан хэлбэрээр өгөгдөнө.

Гаралт

"count" хүсэлт ирэх бүрт хариуг нэг мөрөнд хэвлэ.

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

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

Оролт
2 3
47
count
switch 1 2
count
Гаралт
2
1
Оролт
3 5
747
count
switch 1 1
count
switch 1 3
count
Гаралт
2
3
2

Тэмдэглэл

Эхний жишээнд $s$ тэмдэгт мөр дээр үйлдэл хийгдэх бүрт тус бүр дараах байдалтай болно (Олдсон хамгийн урт дэд дараалал тодоор бичигдсэн):

  1. 47
  2. 74
  3. 74

Хоёр дахь жишээнд:

  1. 747
  2. 447
  3. 447
  4. 774
  5. 774
Сэтгэгдлүүдийг ачааллаж байна...