# Stack

Stack is one of the most popular data structures used in algorithms. When using stacks, the elements added last would be the first ones to be removed. It's like a stack of plates, where the plate on top is the only one that can be removed until all the plates on top of it are taken away.

A stack can be used in many real-world situations. When opening websites in a web browser, you can click on the back button to move to the previous page. The history of pages could be stored in a stack, and as soon as you hit a back button you can be navigated to the top of the stack. If you hit back again, the top page from the stack is removed, and you are navigated to the one below it.

There are several ways of implementing a stack in a programming language like Python:

- Using
`list`

- the top element of the queue will be the last element of the list. We can add with`append`

, remove with`pop`

, and get the element with`[-1]`

.

- Using
`deque`

from`collections`

- it supports adding and removing elements from both the start and the end.

`LifoQueue`

from`queue`

- Last-in-first-out queue, which is essentially the definition of the stack data structure.

```
from queue import LifoQueue
stack = LifoQueue()
# push
stack.put(1)
stack.put(2)
stack.put(3)
# pop
print(stack.get()) # prints 3
print(stack.get()) # prints 2
# peek
print(stack.queue[-1]) # prints 1
print(stack.empty()) # check if empty -> prints False
```

```
# Using a simple list
stack = []
# push
stack.append(1)
stack.append(2)
stack.append(3)
# pop
print(stack.pop()) # prints 3
print(stack.pop()) # prints 2
# peek
print(stack[-1]) # prints 1
print(len(stack) == 0) # check if empty -> prints False
```

Challenge: Check if the sequence of brackets is valid

Given a sequence of brackets of a mathematical expression (i.e.

`(()())`

), you are asked to check if that sequence is valid. A sequence of brackets is valid if every opening bracket has a corresponding closing one and there are no extra opening or closing brackets. Input

The only line of the input contains a single line

`b`

(1 β€ |b| β€ ) containing the bracket sequence. Output

The program should print

`Yes`

in case the bracket sequence is valid, and `No`

otherwise. Examples

Input | Output |

()() | Yes |

())()( | No |

((()())()) | Yes |

Β

#### Constraints

Time limit: 1 seconds

Memory limit: 512 MB

Output limit: 1 MB