Cho một chuỗi \(s\) là một biểu thức toán học hợp lệ, hãy viết chương trình tính giá trị biểu thức đó.

Ghi chú: Không được sử dụng hàm có sẵn, như eval().

Input

• chuỗi \(s\)

Output

• Kết quả biểu thức \(s\)

Constraints:

• \(1 \le s.length \le 3 \times 10^5\)
• s chỉ chứa số, '+', '-', '(', ')', và ' '.
• '+' không sử dụng trong trường hợp (i.e., "+1" và "+(2 + 3)").
• '-' có thể dụng trong trường hợp (i.e., "-1" và "-(2 + 3)").

Example

Sample input 1

"1 + 1  "

Sample output 1

2

Sample input 2

" 2-1 + 2 "

Sample output 2

3

Sample input 3

(1+(4+5+2)-3)+(6+8)

Sample output 3

23