Cân bằng dấu ngoặc

Một dãy ngoặc được gọi là cân bằng nếu có thể chèn thêm các ký tự '+' và '1' để biến nó thành một biểu thức số học hợp lệ. Ví dụ, các dãy "(())()", "()", "(()(()))" là cân bằng, còn ")(", "(()", "(()))(" thì không.

Cho một xâu nhị phân $s$ độ dài $n$ (với $n$ chẵn). Hãy xây dựng hai dãy ngoặc cân bằng $a$ và $b$ cùng độ dài $n$ sao cho với mọi $1\le i\le n$:

• nếu $s_i=1$ thì $a_i=b_i$;
• nếu $s_i=0$ thì $a_i\ne b_i$.

Nếu không tồn tại cặp dãy như vậy, hãy thông báo.

Dữ liệu vào

• Dòng đầu chứa một số nguyên $t$ — số lượng bộ dữ liệu.
• Với mỗi bộ dữ liệu:
  • Dòng đầu chứa số nguyên $n$ ($n$ chẵn) — độ dài xâu.
  • Dòng tiếp theo chứa xâu $s$ độ dài $n$ gồm các ký tự '0' và '1'.

Dữ liệu ra

Với mỗi bộ dữ liệu:

• Nếu tồn tại hai dãy ngoặc cân bằng thỏa mãn, in ra "YES" trên một dòng, sau đó in hai dãy $a$ và $b$ trên hai dòng tiếp theo.
• Ngược lại, in ra "NO".

Nếu có nhiều đáp án, in ra bất kỳ đáp án nào.

Ràng buộc

• $1\le t\le {10}^4$
• $2\le n\le 2·{10}^5$, $n$ chẵn
• Tổng $n$ trên tất cả các bộ dữ liệu không vượt quá $2·{10}^5$.

Ví dụ