Problem statement

"Giữa tàn tích của một đế chế đã bị lãng quên, vẫn sừng sững một công trình như lâu đài, thách thức thời gian qua bao thiên niên kỷ. Bước vào đại sảnh, thứ đập vào mắt là vẻ nguy nga: những cột thạch anh cao vút như chống trời, vòm đá khắc bích họa về lễ nghi và đời sống của một nền văn minh đã biến mất không dấu vết — tựa Atlantis. Kỳ lạ hơn hết là sàn nhà: một lưới lục giác đa sắc, lát kín bởi vô số gạch lục giác rực rỡ."

Đó là đoạn kết trong cuốn sách kể về các kỳ quan của thế giới cổ đại. Bị cuốn hút, nhóm thám hiểm trẻ quyết định lên đường tìm cho được nơi ấy. Trải qua biết bao đèo dốc, suối rừng, cuối cùng họ cũng đến: giữa đống tro tàn, tòa đại sảnh vẫn đứng chờ khách lạ. Họ hăm hở bước vào — mọi thứ giống hệt những dòng sách đã tả.

Rồi một cơ quan bất ngờ kích hoạt. Cửa lớn đóng sầm, cả nhóm sững sờ. Từ giữa phòng, một bia đá trồi lên, khắc những dòng chữ cổ. Lấy lại bình tĩnh, họ đọc được luật của một trò chơi xưa — Đại Sảnh Lục Giác:

"Sàn nhà là một lục giác lớn, lát bởi các viên gạch lục giác nhỏ nhiều màu sắc. Sau 5 phút, bia sẽ hiện ra một chuỗi ký hiệu mô tả các biến đổi của sàn. Dọc theo các cột trụ quanh phòng có 12 cần gạt tương ứng. Hãy xác định trạng thái cuối cùng của sàn sau chuỗi biến đổi, và cho biết số lần gạt tối thiểu để khiến cho sàn nhà trở thành trạng thái cuối cùng đó. Nếu thất bại… cánh cửa sẽ không bao giờ mở lại."

Trong nỗi hoảng hốt, họ cầu cứu bạn. Bạn có thể cứu nhóm đó khỏi Đại Sảnh Lục Giác không?

• Sàn nhà là một lục giác đều lớn với bán kính $N$, tâm tại gốc.
• Mỗi viên gạch được định danh bởi bộ tọa độ $(q,r,s)$ thỏa mãn $q+r+s=0$. Sàn nhà là tập hợp các viên gạch có tọa độ thỏa mãn $\max(|q|,|r|,|s|) \leq N$. Như vậy, số lượng ô của sàn nhà là $1 + 3 \times N \times (N + 1)$. Bạn có thể xem hình vẽ dưới đây để dễ hình dung hơn:
• Mỗi viên gạch được tô bằng một màu có mã màu là $c$ với $c$ là một chữ cái in thường.
• Đây là một ví dụ với $N = 3$:

Các thao tác (12 cần gạt):

• Xoay theo chiều kim đồng hồ: R0,R1,R2,R3,R4,R5. Rk là xoay toàn bộ sàn một góc $(60 \times k)^o$ quanh gốc.
• Phản chiếu (lật) qua sáu trục đi qua tâm: F0,F1,F2,F3,F4,F5. F0 là trục dọc đi qua tâm; Fk là trục đó quay thêm một góc $(30 \times k)^o$ theo chiều kim đồng hồ quanh gốc.

Input Format

$N$ $Q$ $q_1$ $r_1$ $s_1$ $c_1$ $q_2$ $r_2$ $s_2$ $c_2$ $\dots$ $q_{1 + 3 \times N \times (N + 1)}$ $r_{1 + 3 \times N \times (N + 1)}$ $s_{1 + 3 \times N \times (N + 1)}$ $c_{1 + 3 \times N \times (N + 1)}$ $T_1$ $T_2$ $\dots$ $T_Q$

• $N$: Bán kính của sàn nhà.
• $(q_i, r_i, s_i, c_i)$: Tọa độ và màu của viên gạch thứ $i$ của trạng thái bắt đầu.
• Đảm bảo tất cả mọi ô đều được liệt kê.
• $Q$: Số lượng thao tác mình cần thực hiện.
• $T_i$: Các thao tác mình cần thực hiện.

Output Format

$q_1$ $r_1$ $s_1$ $c_1$ $q_2$ $r_2$ $s_2$ $c_2$ $\dots$ $q_{1 + 3 \times N \times (N + 1)}$ $r_{1 + 3 \times N \times (N + 1)}$ $s_{1 + 3 \times N \times (N + 1)}$ $c_{1 + 3 \times N \times (N + 1)}$ $ans$

• $(q_i, r_i, s_i, c_i)$: Tọa độ và màu của viên gạch thứ $i$ của trạng thái sau khi thực hiện xong chuỗi các thao tác.
• Đảm bảo tất cả mọi ô đều được liệt kê.
• $ans$: Số lượng thao tác ít nhất để biến sàn nhà ban đầu thành sàn nhà sau khi thực hiện xong chuỗi các thao tác.

Sample Input

0 12
0 0 0 a
R0 R1 R2 R3 R4 R5 F0 F1 F2 F3 F4 F5

Sample Output

0 0 0 a
0

Constraints

• $0 \leq N \leq 500$.
• $1 \leq Q \leq 10^6$.
• $q_i+r_i+s_i=0$ và $\max(|q_i|,|r_i|,|s_i|) \leq N$ với mọi $1 \leq i \leq 1 + 3 \times N \times (N + 1)$.