Bessie gần đây đã học hóa. Hiện tại, cô có hai loại hóa chất có hai màu khác nhau \(1,2\) và không thể hòa trộn với nhau. Cô có hai ống nghiệm có sức chứa vô hạn được đổ đầy bởi \(N\) (\(1 \leq N \leq 10^5\)) đơn vị của hai chất nói trên. Do hai loại chất lỏng không hòa trộn, khi hai loại chất lắng xuống, chúng chia thành các lớp màu riêng biệt trong hai ống nghiệm và có thể được mô tả bới hai xâu \(f\) và \(s\), trong đó \(f_1, f_2, \ldots, f_N\) mô tả chất lỏng trong ống nghiệm thứ nhất và \(s_1, s_2, \ldots, s_N\) mô tả chất lỏng trong ống nghiệm thứ hai từ dưới lên. Dữ liệu đảm bảo có ít nhất một đơn vị của cả hai chất tồn tại trong 2 ống nghiệm.

Bessie muốn tách hai loại chất lỏng này ra sao cho mỗi ống nghiệm chỉ có duy nhất một loại chất lỏng. Cô tìm thấy một ống nghiệm thứ \(3\) trong nhà kho và sử dụng nó để giúp tách hai chất lỏng ra. Mỗi khi Bessie thực hiện một lần "rót", cô sẽ đổ toàn bộ phần chất lỏng cùng màu phía trên cùng của một ống nghiệm vào một ống nghiệm khác.

Hãy giúp Bessie tính toán số lần đổ ít nhất để tách hai chất lỏng và cách đổ chi tiết. Lưu ý rằng sau khi kết thúc, ống nghiệm thứ \(3\) cần phải rỗng và \(2\) ống nghiệm ban đầu phải chứa \(2\) màu khác nhau.

Bessie có \(T\) (\(1 \leq T \leq 10\)) câu hỏi và có yêu cầu \(P\) cho mỗi câu hỏi như sau:

Giả sử \(M\) là số lần rót ít nhất để tách hai loại chất lỏng:

• Nếu \(P = 1\), Bessie chỉ cần bạn cho biết \(M\).
• Nếu \(P = 2\), Bessie cần bạn cho biết một số nguyên \(A\) sao cho \(M \leq A \leq M+5\), sau đó là \(A\) dòng mô tả cách rót chi tiết (kể cả khi không tối ưu). Mỗi dòng phải mô tả ống rót và ống được rót (\(1\), \(2\) hoặc \(3\)). Ống nguồn phải không trống trước khi di chuyển và không được đổ chất lỏng của một ống nghiệm vào chính nó.
• Nếu \(P = 3\), Bessie cần bạn cho biết \(M\) và một cách rót chi tiết.

Input:

• Dòng đầu tiên chứa \(T\), là số lượng các test case.
• Dòng đầu tiên của mỗi test case chứa hai số nguyên \(N\) và \(P\) mô tả lượng chất lỏng ban đầu của mỗi ống nghiệm và loại câu hỏi Bessie đặt cho bạn.
• Hai tiếp theo của mỗi test case lần lượt gồm \(f_1, f_2, \ldots, f_N\) và \(s_1, s_2, \ldots, f_N\). Cả hai dòng điều chỉ gồm kí tự "\(1\)" và "\(2\)", mô tả hai ống nghiệm theo chiều từ đáy lên.

Output:

• Gồm \(T\) dòng, mỗi dòng là câu trả lời cho từng câu hỏi của Bessie.

Scoring:

• Subtask 1: \(P=1\)
• Subtask 2: \(P=2\)
• Subtask 3: Không có ràng buộc gì thêm.

Ngoài ra, dữ liệu đảm bảo \(T=10\) cho tất cả các input ngoài test mẫu.

6
4 1
1221
2211
4 2
1221
2211
4 3
1221
2211
6 3
222222
111112
4 3
1121
1222
4 2
1121
1222

4
4
1 2
1 3
2 1
3 2
4
1 2
1 3
2 1
3 2
1
2 1
5
2 3
1 2
1 3
1 2
3 1
6
2 3
1 2
1 3
1 2
2 1
3 2