Có một cỗ máy biến đổi xâu chuyên xử lý các xâu $\texttt{01}$, bên trong được thiết lập sẵn một tập hợp hữu hạn $\mathcal{R}$ gồm một số quy tắc. Mỗi quy tắc có dạng $(u, v)$, trong đó $u, v$ là các xâu $\texttt{01}$ khác rỗng có cùng độ dài, biểu thị rằng trong một bước thao tác, có thể chọn một xâu con $u$ của xâu hiện tại và thay thế nó bằng $v$. Mỗi lần đưa vào máy một cặp xâu $\texttt{01}$ khác rỗng có cùng độ dài $(s, t)$, máy sẽ xuất ra số bước thao tác ít nhất cần thiết để biến đổi $s$ thành $t$, hoặc báo vô nghiệm.

Bạn nhớ lại rằng mình từng đưa vào cỗ máy này $n$ cặp xâu $\texttt{01}$ khác rỗng có cùng độ dài $(s_1, t_1), (s_2, t_2), \dots, (s_n, t_n)$. Trùng hợp là trong trí nhớ của bạn, mỗi truy vấn không những đều có nghiệm mà còn thỏa mãn số bước thao tác ít nhất $d_i \leqslant 2$.

Để kiểm tra xem trí nhớ của bạn có bị sai lệch hay không, hãy xác định xem: có tồn tại một tập quy tắc $\mathcal{R}$ sao cho kết quả thực tế của máy đối với $n$ bộ dữ liệu đầu vào này hoàn toàn khớp với trí nhớ của bạn hay không?

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên dương $T$, biểu thị số lượng bộ dữ liệu kiểm tra.

Đối với mỗi bộ dữ liệu kiểm tra, dòng đầu tiên chứa một số nguyên dương $n$, biểu thị số lượng bản ghi truy vấn. Trong $n$ dòng tiếp theo, dòng thứ $i$ chứa hai xâu $\texttt{01}$ khác rỗng có cùng độ dài $s_i, t_i$ và một số nguyên $d_i$ ($0 \leqslant d_i \leqslant 2$), lần lượt biểu thị xâu ban đầu, xâu đích và số bước thao tác ít nhất mà máy đưa ra ở lần nhập thứ $i$.

Dữ liệu ra

Đối với mỗi bộ dữ liệu kiểm tra, in ra một xâu trên một dòng. Nếu tồn tại tập quy tắc $\mathcal{R}$ thỏa mãn điều kiện thì in ra YES; ngược lại in ra NO.

Bạn có thể in ra YES và NO ở bất kỳ dạng chữ hoa hay chữ thường nào, ví dụ yes, Yes hoặc YES đều được coi là cùng một đáp án.

Ví dụ

Dữ liệu vào 1

3
3
010 010 0
001 010 1
001 100 2
2
10 01 1
100 010 2
1
0 1 2

Dữ liệu ra 1

YES
NO
NO

Ghi chú

• Bộ dữ liệu kiểm tra thứ $1$: Có thể xây dựng tập hợp chỉ chứa một quy tắc $\mathcal{R} = \{(\texttt{01}, \texttt{10})\}$:
  • Đối với truy vấn thứ $1$, $s_1 = t_1 = \texttt{010}$, không cần bất kỳ thao tác nào cũng hoàn thành biến đổi, số bước thao tác ít nhất là $0$.
  • Đối với truy vấn thứ $2$, thay thế hậu tố $\texttt{01}$ của $\texttt{001}$ bằng $\texttt{10}$, ta thu được $\texttt{010}$ chỉ trong $1$ bước.
  • Đối với truy vấn thứ $3$, do $\texttt{001}$ và $\texttt{100}$ khác nhau ở cả vị trí thứ $1$ lẫn vị trí thứ $3$, chỉ dựa vào quy tắc độ dài $2$ thì không thể hoàn thành biến đổi trong $1$ bước; nhưng có thể thay thế hậu tố $\texttt{01}$ của xâu ban đầu $\texttt{001}$ bằng $\texttt{10}$ trước để thu được xâu trung gian $\texttt{010}$, sau đó thay thế tiền tố $\texttt{01}$ của xâu trung gian $\texttt{010}$ bằng $\texttt{10}$ để thu được xâu đích $\texttt{100}$, vì vậy số bước thao tác ít nhất là $2$.
• Bộ dữ liệu kiểm tra thứ $2$: Để biến đổi $\texttt{10}$ thành $\texttt{01}$ trong $1$ bước, tập quy tắc $\mathcal{R}$ bắt buộc phải chứa quy tắc $(\texttt{10}, \texttt{01})$. Tuy nhiên, một khi chứa quy tắc này, truy vấn thứ $2$ chỉ cần thay thế tiền tố $\texttt{10}$ của $\texttt{100}$ bằng $\texttt{01}$ là có thể thu được $\texttt{010}$ trong $1$ bước, mâu thuẫn với $d_2 = 2$ trong trí nhớ.
• Bộ dữ liệu kiểm tra thứ $3$: Tất cả các xâu trong quá trình biến đổi đều phải là các xâu $\texttt{01}$ có cùng độ dài. Các xâu $\texttt{01}$ có độ dài $1$ chỉ có hai loại là $\texttt{0}$ và $\texttt{1}$; nếu có thể biến đổi từ $\texttt{0}$ thành $\texttt{1}$ thì chắc chắn phải tồn tại quy tắc $(\texttt{0}, \texttt{1})$ và chỉ cần $1$ bước để hoàn thành, không thể đòi hỏi ít nhất $2$ bước.

Giới hạn

Đối với tất cả dữ liệu kiểm tra, đảm bảo $T \geqslant 1$, $n \geqslant 1$, $0 \leqslant d_i \leqslant 2$, $1 \leqslant |s_i| = |t_i|$, và $s_i, t_i$ đều là các xâu chỉ chứa các ký tự $\texttt{0}$ và $\texttt{1}$.

Đặt $L = \sum_{i=1}^{n} |s_i|$ là tổng độ dài của tất cả các xâu ban đầu trong một bộ dữ liệu kiểm tra, và $\sum L$ là tổng của $L$ trên tất cả các bộ dữ liệu kiểm tra trong một test, đảm bảo $\sum L \leqslant 3\times 10^6$.

Bài toán này bật quan hệ phụ thuộc nhiệm vụ con hợp lý.

• Tính chất đặc biệt A: Đảm bảo với mọi $1 \leqslant i \leqslant n$, đều có $|s_i| \geqslant 50$.