358C орчуулах · Codeforces.mn

# Дима ба агуулагчууд
Димагийн төрсөн өдөр удахгүй болно! Маш чухал өдөр! Сережагийн Димад өгөх бэлэг бол Дима Инна хоёрыг төрсөн өдрөө тэмдэглэхэд нь саад болохгүй байх ба өрөөнд байхгүй байх юм. Иннагийн Димад өгөх бэлэг бол стэк, дараалал ба цуваа юм.

Инна өөрийн бэлгээрээ Димаг хэр сайн програмчлагч гэдгийг нь харуулахыг зорьсон. Үүний тулд тэр Димад коммандуудыг нэг нэгээр нь өгөх гэж байна. Энд хоёр төрлийн комманд байна:

1. Өгөгдсөн тоог агуулагчдын нэгрүү нь нэмэх. Дараалал болон стекийн хувьд та элементүүдийг зөвхөн төгсгөлрүү нь л нэмж болно. Цувааны хувьд та элементүүдийг эхлэл ба төгсгөлрүү нь нэмж болно.
  2. Хамгийн ихдээ гурван ялгаатай агуулагч бүрээс тоог гаргах. Гарсан бүх тоог Иннад хэлэх ба бүх агуулагчыг хоослох. Дараалал агуулагчаас та зөвхөн эхлэлээс нь л тоо гаргана. Стэк агуулагчаас та зөвхөн төгсгөлөөс нь л тоо гаргана. Харин цуваа агуулагчаас та эхлэл болон төгсгөлөөс тоо гаргаж болно. Та хоосон агуулагчаас тоо гаргаж чадахгүй.

Дима хоёр дахь төрлийн комманд хийх бүрт Инна Димаг хэд хэдэн удаа үнсэнэ (тэг ч байж болно). Дима Иннаг сайн мэднэ, үнсэх тоо нь уг үйлдэлд гаргаж авсан тоонуудын нийлбэр байна гэдэгт Дима итгэлтэй байна.

Өмнө хэлсэнчлэн Дима Иннаг маш сайн мэдэх ба тэр Иннагийн өгөх коммандууд болон тэдгээрийн дарааллыг мэднэ. Димад төрсөн өдөртөө зориулж боломжит хамгийн их үнсэлтийг авах стратегийг олоход туслана уу.

## Оролт
Эхний мөрөнд бүхэл тоон утга $n$ $(1 ≤ n ≤ 10^{5})$ байх ба Иннагийн коммандуудын тоо байна. Дараагийн $n$ мөрөнд Иннагийн коммандуудыг тодорхойлно. Мөр бүрт бүхэл тоон утга байна:

1. Бүхэл тоон утга $a$ $(1 ≤ a ≤ 10^{5})$ нь Инна Димад агуулагчуудын аль нэгэнд $a$ тоог нэмэх комманд өгч байна гэсэн үг.
  2. Бүхэл тоон утга $0$ нь ялгаатай агуулагчуудаас хамгийн ихдээ гурван тоо гаргах комманд өгч байна гэсэн үг.

## Гаралт
Оролтын комманд бүр Димагийн үйлдэл буюу гаралтын нэг мөртэй харгалзах ёстой.

Эхний төрлийн коммандын хувьд (нэмэх) Димагийн сонголттой харгалзах нэг үгийг хэвлэ:

* pushStack -- стэкийн төгсгөлд нэмэх; 
  * pushQueue -- дарааллын төгсгөлд нэмэх; 
  * pushFront -- цувааны эхэнд нэмэх; 
  * pushBack -- цувааны төгсгөлд нэмэх.

Хоёр дахь төрлийн коммандын хувьд эхлээд гаргах үйлдлүүдийн тоо болох нэг бүхэл тоон утга $k$ $(0 ≤ k ≤ 3)$-г хэвлэнэ, тэгээд зайгаар тусгаарлагдсан $k$ үг хэвлэнэ. Үгүүд нь:

* popStack -- стэкийн төгсгөлөөс гаргах; 
  * popQueue -- дарааллын эхлэлээс гаргах; 
  * popFront -- цувааны эхлэлээс гаргах; 
  * popBack -- цувааны төгсгөлөөс гаргах.

Хэвлэгдсэн үйлдлүүд нь хоосон агуулагчаас тоо гаргасан байж болохгүй. Мөн эдгээр нь ялгаатай агуулагчуудаас тоо гаргасан байх ёстой.

Хэвлэгдсэн үйлдлүүдийн дараалал нь хамгийн их тооны үнсэлтрүү хөтлөх ёстой. Хэрвээ хамгийн их тооны үнсэлтрүү хөтлөх үйлдлүүдийн хэд хэдэн дараалал байвал та алийг нь ч хэвлэж болно.

-- Г.Мэндбаяр

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

Оролт

Гаралт

0
pushStack
1 popStack
pushStack
pushQueue
2 popStack popQueue
pushStack
pushQueue
pushFront
3 popStack popQueue popFront

Оролт

Гаралт

pushStack
pushQueue
pushFront
3 popStack popQueue popFront