Có thể định nghĩa khái niệm dãy ngoặc đúng dưới dạng đệ quy như sau:

1. "()" là dãy ngoặc đúng

2. C là dãy ngoặc đúng nếu ~C=(A)~ hay ~C=AB~ với ~A~,~B~ là các dãy ngoặc đúng.

Ví dụ dãy ngoặc đúng: (),(()),()(),(())()

Ví dụ dãy ngoặc sai: )(,((((,()((,)))),)()(

Yêu cầu: Bạn hãy viết chương trình kiểm tra 1 dãy ngoặc có chiều dài ~n~.

Input

• Dãy ngoặc chỉ bao gồm 2 ký tự '(' và ')' có độ dài không quá ~10^6~ ký tự.

Output

• Nếu dãy ngoặc đúng thì in "Yes", ngược lại in "No"

Example

Test 1

Input 1

((()))

Output 1

Yes

Test 2

Input 2

((()))(

Output 2

No

Một dãy ngoặc đúng được định nghĩa như sau:

• Xâu rỗng là 1 dãy ngoặc đúng.
• Nếu ~A~ là 1 dãy ngoặc đúng thì ~(A)~ là 1 dãy ngoặc đúng.
• Nếu ~A~ và ~B~ là dãy ngoặc đúng thì ~AB~ là 1 dãy ngoặc đúng. Cho dãy ngoặc ~S~ độ dài ~N~ và ~Q~ truy vấn biểu diễn bởi 2 số nguyên ~l~ và ~r~: Kiểm tra dãy ngoặc con ~S[l..r]~ có là dãy ngoặc đúng hay không?

Dữ liệu vào:

• Dòng đầu tiên chứa 2 số nguyên dương ~N~ và ~Q~ (~1 ≤ N, Q ≤ 10^5~).

• Dòng thứ hai chứa dãy ngoặc ~S~.

• Trong ~Q~ dòng tiếp theo, mỗi dòng chứa một truy vấn.

Dữ liệu ra:

• Với mỗi truy vấn, in trên một dòng "YES" nếu đúng, ngược lại in "NO".

Ví dụ:

INPUT

7 3
((())()
3 4
1 5
2 7

OUTPUT

YES
NO
YES

Dữ liệu vào:

• Dòng 1. Chứa số nguyên dương ~n~ (~1 \le 10^4~)
• n dòng tiếp theo chứa ~n~ xâu ký tự chỉ bao gồm các ký tự ~'[',']', '{','}', '(',')'~ có độ dài không quá 1000 ký tự.

Dữ liệu ra:

• Gồm ~n~ dòng, mỗi dòng ghi ~1~ số ~0~ hoặc số ~1~. Nếu dãy ngoặc đúng ghi ~0~, ngược lại ghi ~1~.

Ví dụ:

Input

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

Output

1
1
0

Biểu thức ngoặc là xâu chỉ gồm các ký tự '(' hoặc ')'. Biểu thức ngoặc đúng và bậc của biểu thức ngoặc được định nghĩa một cách đệ qui như sau:

• Biểu thức rỗng là biểu thức ngoặc đúng và có bậc bằng 0,
• Nếu A là biểu thức ngoặc đúng có bậc bằng 𝑘 thì (A) cũng là một biểu thức ngoặc đúng có bậc bằng 𝑘 + 1,
• Nếu A và B là hai biểu thức ngoặc đúng và có bậc tương ứng là 𝑘1 và 𝑘2 thì AB cũng là một biểu thức ngoặc đúng có bậc bằng max(k1,k2).

Ví dụ: '()(())' là một biểu thức ngoặc đúng có bậc bằng 2 còn '(()(()))' là một biểu thức ngoặc đúng và có bậc bằng 3.

Yêu cầu: Cho S là một xâu chỉ gồm các ký tự '(', ')' , hãy kiểm tra xem S là dãy ngoặc bậc bao nhiêu.

Input:

• Dòng 1: xâu S có độ dài không vượt quá ~10^6~ chỉ gồm các ký tự '(', ')'

Output:

• Ghi số nguyên dương t là số bậc cao nhất của dãy ngoặc S.

Ví dụ:

Input 1:

()()

Output 1:

1

Input 2:

((()))

Output 2:

3

Ràng buộc

Subtask 1: ~s.length() \le 20~

Subtask 2: Không có bất cứ ràng buộc nào.

Dãy nhị phân là dãy chỉ boa gồm 2 ký tự 0 và 1. Ví dụ: 1001; 1010.

Yêu cầu: Cho số nguyên dương N, liệt kê dãy nhị phân khác nhau có độ dài N theo thứ tự từ điển.

Input

• Là số nguyên ~n~ (~n~ chẵn, ~2 ≤ n ≤ 20~)

Output

• In ra các dãy nhị phân có độ dài N theo thứ tự từ điển, mỗi dãy in trên 1 dòng.

Example

Test 1

Input 1

3

Output 1

000
001
010
011
100
101
110
111

Có thể định nghĩa khái niệm dãy ngoặc đúng dưới dạng đệ quy như sau:

1. "()" là dãy ngoặc đúng

2. C là dãy ngoặc đúng nếu ~C=(A)~ hay ~C=AB~ với ~A~,~B~ là các dãy ngoặc đúng.

Ví dụ dãy ngoặc đúng: (),(()),()(),(())()

Ví dụ dãy ngoặc sai: )(,((((,()((,)))),)()(

Yêu cầu: Bạn hãy viết chương trình liệt kê tất cả các dãy ngoặc đúng có chiều dài ~n~(~n~ chẵn)

Input

• Là số nguyên ~n~ (~n~ chẵn, ~2 ≤ n ≤ 20~)

Output

• In số ~m~ là số lượng các dãy ngoặc đúng có chiều dài ~n~

Example

Test 1

Input 1

4

Output 1

2

Test 2

Input 2

2

Output 2

1