Танд дөрвөн төрлийн нээх болон хаах хаалтуудаас $<>$, ${}$, $[]$, $()$ бүрдсэн $s$ урттай тэмдэгт мөр өгөгдсөн. Хоёр төрлийн хаалт байна: нээх ба хаах. Та дурын хаалтыг ижил төрлийн хаалтаар сольж чадна. Жишээлбэл та $<$ хаалтыг { хаалтаар сольж чадах боловч $)$ эсвэл $>$ хаалтаар сольж чадахгүй.

Зөв хаалтны дарааллын дараах тайлбарыг ихэнх хүмүүс мэддэг учир танд ойр санагдах болно.

Зөв хаалтын дарааллыг (RBS) тодорхойлцгооё. Хоосон тэмдэгт мөр RBS байна. $s_{1}$ ба $s_{2}$ нь RBS байг тэгвэл <$s_{1}$>$s_{2}$, {$s_{1}$}$s_{2}$, [$s_{1}$]$s_{2}$, ($s_{1}$)$s_{2}$ тэмдэгт мөрүүд ч мөн RBS байна.

Жишээлбэл "$[[(){}]<>]$" тэмдэгт мөр нь RBS боловч "$[)()$" болон "$][()()$" тэмдэгт мөрүүд нь RBS биш.

$s$ тэмдэгт мөрийг RBS болгохын тулд солих үйлдлийн хамгийн бага тоог ол.

Оролт

Нэг мөрөнд зөвхөн дөрвөн төрлийн нээх болон хаах хаалтуудаас бүрдэх хоосон биш тэмдэгт мөр $s$ байна. $s$ тэмдэгт мөрийн урт $10^{6}$-с ихгүй байна.

Гаралт

Хэрвээ $s$-с RBS үүсгэх боломжгүй бол $Impossible$ гэж хэвлэ.

Бусад тохиолдолд $s$-г RBS болгоход шаардлагатай солих үйлдлийн хамгийн бага тоог хэвлэ.