Танд зөвхөн '(', ')', '[', ']', '{', '}' тэмдэгтүүдээс бүрдсэн S тэмдэгт мөр өгөгдөнө.

Та S тэмдэгт мөр нь зөв хаалттай эсэхийг шалгана.

Тэмдэгт мөрийг зөв гэж үзэх нөхцөл:

1. Нээсэн хаалт бүр өөрийн тохирох хаалттай хаагдсан байна

   • ( → )
   • [ → ]
   • { → }

2. Хаалтууд зөв дарааллаар хаагдсан байна

   • (жишээ: ([{}]) зөв, харин ([)] буруу)

Оролт:

Нэг мөрөнд S тэмдэгт мөр өгөгдөнө.

Гаралт:

Тухайн тэмдэгт мөр дэх бүх хаалт зөв зөв байрлалтай бол YES үгүй бол NO гэж хэвлэ.

Хязгаарлалт

• \(1 ≤ |S| ≤ 10^5\)

Дэд бодлого

Жишээ

Оролт-1:

()((()()))((()))

Гаралт-1:

YES

Оролт-2:

()()((())

Гаралт-2:

NO

Оролт-3:

()([])([(({}))]

Гаралт-3:

NO

Оролт-4:

()([])[{}(({()}))]

Гаралт-4:

YES