Có một bảng gồm \(N\times N\) ô vuông, xếp thành \(N\) hàng và \(N\) cột. Ô ở hàng thứ \(i\) từ trên xuống và cột thứ \(j\) từ trái sang được gọi là ô \((i,j)\). Ban đầu, ô \((i,j)\) chứa ký tự \(A_{ij}\).

Thực hiện lần lượt \(Q\) thao tác. Ở thao tác thứ \(k\), quay vùng vuông gồm \(S_k\times S_k\) ô, có ô trên cùng bên trái là \((I_k,J_k)\), một góc \(90^\circ\) ngược chiều kim đồng hồ.

Yêu cầu

Hãy xác định và in ra bảng sau khi thực hiện tất cả các thao tác.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu chứa hai số nguyên \(N,Q\) cách nhau bởi dấu cách, lần lượt là kích thước bảng và số thao tác quay.
• \(N\) dòng tiếp theo mô tả bảng ban đầu. Dòng thứ \(i\) chứa một chuỗi dài \(N\), chỉ gồm các chữ cái tiếng Anh viết thường; ký tự thứ \(j\) của chuỗi là \(A_{ij}\).
• \(Q\) dòng tiếp theo mô tả các thao tác theo thứ tự thực hiện. Dòng thứ \(k\) chứa ba số nguyên \(I_k,J_k,S_k\) cách nhau bởi dấu cách, xác định vùng vuông được quay trong thao tác thứ \(k\).

Dữ liệu ra

In ra đầu ra chuẩn \(N\) dòng mô tả bảng cuối cùng. Dòng thứ \(i\) là một chuỗi dài \(N\), có ký tự thứ \(j\) bằng ký tự trong ô \((i,j)\) sau tất cả các thao tác.

Ràng buộc

• \(2\le N\le1\,000\).
• \(1\le Q\le2\,000\).
• \(2\le S_k\le N\) với \(1\le k\le Q\).
• \(1\le I_k\le N-S_k+1\) và \(1\le J_k\le N-S_k+1\) với \(1\le k\le Q\).
• Mỗi \(A_{ij}\) là một chữ cái tiếng Anh viết thường.
• \(N,Q,I_k,J_k,S_k\) đều là số nguyên.

Phân nhóm

• Các bộ dữ liệu chiếm \(10\%\) tổng số điểm thỏa mãn đồng thời \(N\le100\) và \(Q\le100\).

Ví dụ

4 1
abcd
efgh
ijkl
mnop
2 2 2

abcd
egkh
ifjl
mnop

abcd
efgh
ijkl
mnop

fg
jk

abcd
egkh
ifjl
mnop