Булат недавно усвоил важное правило: если в программе есть открывающая скобка, то где-то после должна быть и закрывающая скобка такого же типа. Всего в программе Булат использует три типа скобок: «()», «[]» и «{}». Булат выписал из своей программы все скобки в одну строку в том порядке, в котором они встречаются. Теперь он просит вас определить, правильно ли он расставил скобки в своей программе, или же он где-то допустил ошибку. Скобки считаются расставленными в строке правильно, если: 1) строка пуста или состоит лишь из пары соответствующих друг другу скобок, причем открывающая предшествует закрывающей; 2) строка с правильно расставленными скобками находится заключена между парой соответствующих друг другу скобок, причем открывающая предшествует закрывающей.
Формат входных данных:
В первой строке записана последовательность не более, чем из 1000 символов, состоящая лишь из открывающих и закрывающих скобок трех типов.
Формат результата:
Выведите слово «YES» если последовательность скобок правильная, иначе выведите «NO».
Примеры
Входные данные Результат работы
{()[]{}} YES
{(][)} NO