A. Эрдэнэс

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

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

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

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

Малек эрдэнэс нуусан газрын зураг олжээ. Тэрээр эрдэнэсийг хайж байх явцдаа нэгэн цоожтой хаалга олсон бөгөөд энэ хаалган дээр "(", ")", "#" тэмдэгтээс бүтсэн $s$ тэмдэгт мөр байжээ. Түүний доор яаж гараар тайлахыг заасан байжээ. Их цаг хугацаа зарцуулсаны дараа тэрээр үүний зорилго нь "#" тэмдэгтийг ")" тэмдэгтээр солин зөв болгох гэдгийг олжээ.

Түүний доор хэрвээ $i$ ($1 ≤ i ≤ |s|$) болгоны хувьд эхний $i$ тэмдэгт дотор ")" тэмдэгт "(" тэмдэгтээс олонгүй байх бөгөөд нийт "(", ")" тэмдэгтүүд хоорондоо тэнцүү тооны байвал энэ тэмдэгт мөрийг зөв гэнэ гэж бичсэн байна.

Малекд туслан "#" тэмдэгт болгонд нийт хэдэн ширхэг ")" тэмдэгтийг орлуулахыг хэлж өгнө үү.

Оролт

Эхний мөрөнд $s$ ($1 ≤ |s| ≤ 10^{5}$) тэмдэгт мөр өгөгдөнө. Тэмдэгт мөрийн тэмдэгт бүр "(", ")", "#" тэмдэгтүүдийн аль нэг нь байна. $s$ тэмдэгт мөр дор хаяж нэг ширхэг "#" тэмдэгт агуулна.

Гаралт

Хэрвээ тэмдэгт мөрийг "#" тэмдэгтийг орлуулан зөв болгох боломжгүй бол "-1" гэж хэвлэнэ үү. Харин боломжтой бол "#" тэмдэгт болгонд хэдэн ширхэг ")" тэмдэгт орлуулахыг мөр болгонд хэвлэнэ үү.

Хэрвээ нэгээс олон хариулт олдвол аль нэгийг нь хэвлэнэ үү.

Орчуулсан: Энхлут

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

Оролт
(((#)((#)
Гаралт
1
2
Оролт
()((#((#(#()
Гаралт
2
2
1
Оролт
#
Гаралт
-1
Оролт
(#)
Гаралт
-1

Тэмдэглэл

$|s|$-ээр нь $s$ тэмдэгт мөрийн уртыг тэмдэглэв.

Сэтгэгдлүүдийг ачааллаж байна...