Cho số nguyên dương ~n~ và xâu ~S~ có ~2n~ kí tự, được đánh số từ ~1~ đến ~2n~, mỗi kí tự là dấu ngoặc mở '(' hoặc dấu ngoặc đóng ')'. Các kí tự trong xâu được chia thành ~n~ cặp, hai kí tự thuộc cùng một cặp không nhất thiết phải liên tiếp. Mỗi cặp cần xóa đi ~1~ kí tự sao cho ~n~ kí tự còn lại tạo thành xâu ngoặc đúng.

Xâu ngoặc đúng được định nghĩa như sau:

• Xâu rỗng là một xâu ngoặc đúng.

• Nếu ~A~ là một xâu ngoặc đúng thì ~(A)~ cũng là một xâu ngoặc đúng.

• Nếu ~A~ và ~B~ là các xâu ngoặc đúng thì ~AB~ cũng là một xâu ngoặc đúng.

Yêu cầu: Hãy xác định xem có cách xóa sao cho xâu gồm ~n~ kí tự còn lại tạo thành xâu ngoặc đúng không?

Input

• Dòng đầu tiên chứa số nguyên ~t~ ~(1 \le t \le 10^5)~ là số bộ dữ liệu, mỗi bộ dữ liệu gồm:

  • Dòng đầu chứa số nguyên ~n~ ~(1 \le n \le 10^5)~.

  • Dòng thứ hai chứa xâu ~S~ có ~2n~ kí tự.

  • ~n~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~a_i~ và ~b_i~ ~(1 \le a_i < b_i \le 2n)~ cho biết vị trí hai kí tự thuộc cặp thứ ~i~. Các giá trị ~a_1,b_1,a_2,b_2,\dots,a_n,b_n~ đôi một khác nhau.

Tổng các giá trị của ~n~ trong ~t~ bộ dữ liệu không vượt quá ~10^5~.

Output

Gồm ~t~ dòng, mỗi dòng là câu trả lời tương ứng với một bộ dữ liệu. Nếu tồn tại cách xóa để tạo thành xâu ngoặc đúng thì in ra "Yes", ngược lại in ra "No".

Scoring

Sample Input 1

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

Sample Output 1

No
Yes

Notes

• Trong bộ dữ liệu đầu tiên: không có phương án xóa theo yêu cầu của đề bài để được xâu ngoặc đúng.

• Trong bộ dữ liệu thứ hai: Ta có cách thực hiện như sau để tạo thành xâu ngoặc đúng:

  • Cặp ~(1,3)~ xóa kí tự tại vị trí ~3~.

  • Cặp ~(2,7)~ xóa kí tự tại vị trí ~7~.

  • Cặp ~(5,6)~ xóa kí tự tại vị trí ~6~.

  • Cặp ~(4,8)~ xóa kí tự tại vị trí ~4~.

  Sau khi xóa xong, ~n~ kí tự còn lại là (()).