E. Хаалгатай бэлтгэл

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

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

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

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

Хурандаа Шефард Ахмад Плайсд зориулж бэлтгэл хийх гэж байна. Хурандаад нэг мөрөнд цувран байрласан хязгааргүй тооны хаалттай хаалга агуулсан олон өнцөгт байна. Эхлээд Ахмад Плайс эхний хаалганы урд зогсоно. Ахмад дараах хоёр командыг биелүүлэх боломжтой байна:

  • эхний хаалттай хаалгыг онгойлгох ба дараагийн хаалттай хаалганы урд очиж зогсох (энэ командыг '$($' гэж тэмдэглэнэ),
  • онгорхой байгаа хаалгануудын хамгийн сүүлийн хаалганы урд зогсоод уг хаалгаа хаах (энэ командыг '$)$' гэж тэмдэглэнэ).

Хэд хэдэн командуудын дараалал нь дараах нөхцөлүүдийг хангаж байвал хүчинтэй байна:

  • '$)$' команд гүйцэтгэхдэх үед ядаж нэг онгорхой хаалга байх (тухайлбал хамгийн эхний комманд '$)$' байж болохгүй),
  • дарааллын бүх командыг гүйцэтгэсний дараа бүх хаалга хаагдсан байх ёстой (ахмад эхний хаалганы урд зогсоно).

Хурандаа Шефард нүд бүр нь команд ('$($' эсвэл '$)$') агуулсан $n$ мөр $m$ баганатай тэгш өнцөгт хүснэгт бүхий загвар хүлээн авсан. Хурандаа ахмадад зориулж бэлтгэлийн төлөвлөгөө сонгох ёстой ба энэ нь хүснэгтээс сонгосон тэгш өнцөгт байна. Уг тэгш өнцөгтийн мөр бүр нь ахмадад зориулсан бие даасан бэлтгэл байна. Хэрвээ сонгосон тэгш өнцөгтийн мөр бүр нь командуудын хүчинтэй дараалал байвал уг төлөвлөгөө нь хүчинтэй байна.

Та өгөгдсөн хүснэгтийн хувьд хүчинтэй бэлтгэлийн төлөвлөгөө сонгох замуудын тоог олох хэрэгтэй. Сонгогдсон тэгш өнцөгт нь үргэлжилсэн байх буюу ямар ч нүх агуулахгүй. Агуулга нь адилхан ч булангуудын байрлал нь ялгаатай бол уг төлөвлөгөөнүүд нь ялгаатайд тооцогдоно.

Оролт

Эхний мөрөнд хоёр бүхэл тоон утга $n$ ба $m$ ($1 ≤ n, m ≤ 50000$) байх буюу харгалзан загварын мөр болон баганын тоо байна. Дараагийн $n$ мөр бүрт $m$ тэмдэгт ('$($' эсвэл '$)$') бүхий тэмдэгт мөр байх ба энэ нь командуудын загвар юм. Загварын нийт элементүүдийн тоо нь $10^{6}$-с хэтрэхгүй байна.

Гаралт

Загварт байгаа хүчинтэй бэлтгэлийн төлөвлөгөөнд харгалзах тэгш өнцөгтүүдийн тоог илэрхийлэх нэг бүхэл тоог хэвлэ. Адилхан агуулгатай боловч булангууд нь ялгаатай координатад байгаа хоёр тэгш өнцөгт хоёулаа тоологдоно.

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

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

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