D. Хуурцаг программчлах

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

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

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

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

Программ бүр нь "$<$" ба "$>$" тэмдэгтүүд болон цифрүүдийн хоосон биш дараалал байх программчлалын хэл байв. Уг программчлалын хэлний орчуулагч хэрхэн ажилладаг болохыг тайлбарлая. Ямар нэг программ гэдэг нь 2 хэсгээс тогтох зааварлагч сумын (instruction pointer (IP)) орчуулагдсан хөдөлгөөн юм. Уг 2 хэсэг нь доор дүрслэгдэв:

  • Одоогийн тэмдэгтийг заагч (Current character pointer, CP);
  • Чиглэл заагч (Direction pointer, DP) энэ нь зүүн эсвэл баруун тийш заана;

Анхандаа CP нь уг дарааллын хамгийн зүүн талын тэмдэгтийн заах ба DP нь баруун тийш заана.

Бид CP нь уг дарааллаас гадна заах эхний мөч хүртэл дараах алхмуудыг давтан хийнэ.

  • Хэрэв CP нь цифр зааж байвал орчуулагч нь тухайн цифрийг хэвлэх бөгөөд CP нь DP-ын чиглэлийн дагуу нэг алхам нүүнэ. Үүний дараа дарааллын уг хэвлэгдсэн цифрийн утгыг 1-ээр багасгах юм. Хэрэв хэвлэгдсэн цифр нь $0$ байсан бол үүнээс 1-ийг хасах боломжгүй ба түүнчлэн уг дарааллаас энэ $0$-ыг авч хаях бөгөөд дарааллын урт нь нэгээр багасна.
  • Хэрэв CP нь "$<$" эсвэл "$>$"-ыг зааж байвал DP-ын чиглэл нь харгалзан "зүүн" эсвэл "баруун" болж өөрчлөгдөнө. Дараа нь CP нь DP-ын чиглэлийн дагуу нэг алхам нүүнэ. Хэрэв CP-ын зааж буй шинэ тэмдэгт нь $<$" эсвэл "$>$" байвал өмнө нь зааж байсан тэмдэгтийг уг дарааллаас авч хаяна.

Хэрэв ямар нэгэн мөчид CP нь дарааллын гадна зааж байвал уг хасалтууд нь эцэс болох юм.

Уг хэлний программ бүр нь хэсэг алхмын дараа зогсох нь илэрхий юм.

Бидэнд "$<$", "$>$" болон цифрүүдийн $s_{1}, s_{2}, ..., s_{n}$ дараалал байв. Та $q$ ширхэг асуултад хариулах ёстой. Асуулт бүр нь танд $l$ болон $r$-г өгөх ба хэрэв $s_{l}, s_{l + 1}, ..., s_{r}$ дарааллыг уг хэлний бие даасан программ болгон ажиллуулахад цифр тус бүрээс хэдэн ширхэг хэвлэгдэхийг олох юм.

Оролт

Эхний мөрөнд $s$ дарааллын урт болон асуултуудын тоог илэрхийлэх 2 бүхэл тоо $n$ болон $q$ $(1 ≤ n, q ≤ 10^{5})$ өгөгдөнө.

2-дахь мөрөнд зүүнээс баруун хүртэл бичигдсэн "$<$", "$>$" болон ($0..9$) цифрүүдийн $s$ дараалал өгөгдөнө. $s$-ын тэмдэгтүүд зайгаар тусгаарлагдаагүй байхыг анхаарна уу.

Дараагийн $q$ мөрийн мөр болгонд $i$-дахь асуултыг илэрхийлэх 2 бүхэл тоо $l_{i}$ болон $r_{i}$ $(1 ≤ l_{i} ≤ r_{i} ≤ n)$ өгөгдөнө.

Гаралт

Асуулт болгоны хувьд зайгаар тусгаарлагдсан $10$ ширхэг бүхэл тоо $x_{0}, x_{1}, ..., x_{9}$-уудыг хэвлэх ба энд $x_{i}$ нь харгалзах программ ажиллаж байхад программын орчуулагч нь $i$ цифрийг хэвлэх тоотой тэнцүү байна. Хариултуудыг асуултууд нь оролтод өгөгдсөн дарааллаар хэвлэнэ үү.

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

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

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