C. Бүжгийн хичээл

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

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

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

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

$n$ тооны хүмүүс бүжгийн хичээлд хамрагдаж байна. Хүн бүр бүжгийн чадвараараа $a_{i}$ ялгарна. Хичээл эхлэхэд тэд зүүнээсээ баруун тийш жагсана. Хэрэв эгнээнд дор хаяж эрэгтэй, эмэгтэй нэг хос байвал бие биенийхээ хажууд зогсч байгаа эрэгтэй, эмэгтэй хоёрын бүжгийн чадвараараа хамгийн бага ялгаатай нь эхэлж бүжиглэнэ. Хэрэв ийм хэд хэдэн хос байвал зүүн талаасаа эхэлнэ. Тухайн хос бүжиглсний дараа тэр эгнээ нь хаагдана. Өөрөөр хэлбэл, эгнээнүүд дарааллан ээлжилнэ. Бүжгийн чадварын ялгааг $a_{i}$ хувьсагчийн ялгааны + утга гэж ойлгоно.

Та аль хос, бүжгийг эхлүүлж үргэлжлүүлэн ямар дарааллаар явахыг олох юм.

Оролт

Эхний мөр нь хүсүүсийн тоог харуулсан $n$ ($1 ≤ n ≤ 2*10^{5}$) гэсэн бүхэл тоо агуулна. дараагийн мөр нь $n$ тооны B болон G гэсэн тэмдэгтүүд агуулна. B нь хөвгүүд бол, G нь охидыг илэрхийлнэ. Гуравдагч мөр нь бүжгийн чадварыг илэрхийлсэн $a_{i}$ ($1 ≤ a_{i} ≤ 10^{7}$) бүхэл тоо агуулна. Хүмүүс зогссон эгнээндээ зүүнээс баруун тийш тодорхойлогдоно.

Гаралт

$k$ хосын эцсийн үр дүнг харуулсан тоог гарга. Хосыг бүрдүүлж буй хүмүүсийн тоог харуулсан тус бүр нь хоёр ципр агуулсан $k$ мөрийг гарга. Хүмүүс зүүнээсээ баруун тийш $1$ -ээс $n$ бүхэл тоогоор дугаарлагдана. Аль нэг хос бүжгийг орхих тохиолдолд хүмүүсийг дахин тоолох шаардлагагүй. Нэг хосыг бүрдүүлэх хоёр хүний дугаар өсөх дарааллаар эрэмбэлэгднэ. Бүжгийг орхисон хосуудыг дарааллаар нь гарга.

Орчуулсан: Энхгэрэл

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

Оролт
4
BGBG
4 2 4 3
Гаралт
2
3 4
1 2
Оролт
4
BBGG
4 6 1 5
Гаралт
2
2 3
1 4
Оролт
4
BGBB
1 1 2 3
Гаралт
1
1 2
Сэтгэгдлүүдийг ачааллаж байна...