E. Сережа ба Квадратууд

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

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

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

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

Сережа хавтан дээр $n$ цэг зурсан, $i$ $(1 ≤ i ≤ n)$ дугаартай цэг $(i, 0)$ координаттай. Тэгээд Сережа цэг бүрийг Англи цагаан толгойн жижиг эсвэл том үсгээр тэмдэглэсэн. Сережа $x$ үсэгт дургүй ба тэр цэг тэмдэглэхдээ уг үсгийг ашиглаагүй. Сережа дараах нөхцөлүүд биелэж байвал цэгүүд гоё тэмдэглэгдэнэ гэж боджээ:

  • цэг бүр яг нэг хосд хамаарагдахаар бүх цэгүүд хосуудад хуваагдаж чадна;
  • хос цэг бүрийн хувьд бага координаттай нь Англи цагаан толгойн жижиг үсгээр харин их координаттай нь Англи цагаан толгойн ижилхэн том үсгээр тэмдэглэгдэнэ;
  • Хос цэг бүр дээр оройтой, тэдгээрийг холбосон шулуун диагонали болох квадратууд зурсан гэж үзье. Энэ үед аль ч квадратууд хоорондоо огтолцохгүй, шүргэлцхгүй;

Бяцхан Петя цэгүүдийг тэмдэглэсэн зарим жижиг болон бүх том үсгүүдийг арилгачихсан. Одоо Сережа цэгүүд гоё тэмдэглэгдсэн байсан бол арилсан үсгүүдийг сэргээх хэдэн зам байгаа бол гэж бодож байна.

Оролт

Эхний мөрөнд бүхэл тоон утга $n$ байх ба цэгүүдийн тоо байна $(1 ≤ n ≤ 10^{5})$. Хоёр дахь мөрөнд $n$ ширхэг Англи жижиг үсэг болон асуултын тэмдгээс бүрдэх дараалал байх буюу цэгүүдийг $x$-координатын өсөх дарааллаар тэмдэглэсэн үсгүүдийн дараалал юм. Асуултын тэмдгүүд үсэггүй цэгүүдийг заана (Петя тэднийг арилгасан). Оролтын тэмдэгт мөр "$x$" үсгийг агуулахгүй нь тодорхой.

Гаралт

Бодлогын хариуг $4294967296$ тоонд хуваагаад гарсан үлдэгдлийг нэг мөрөнд хэвлэ. Хэрвээ арилгасан үсгүүдийг сэргээх ямар ч зам байхгүй бол $0$ тоог хэвлэ.

C++ хэлэнд 64 битийн бүхэл тоон утгуудыг унших эсвэл бичихдээ $\%lld$ тодорхойлогчийг битгий бичээрэй. Харин $cin$, $cout$ урсгалууд эсвэл $\%I64d$ тодорхойлогчийг ашиглахыг зөвлөж байна.

Орчуулсан: Г.Мэндбаяр

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

Оролт
4
a???
Гаралт
50
Оролт
4
abc?
Гаралт
0
Оролт
6
abc???
Гаралт
1
Сэтгэгдлүүдийг ачааллаж байна...