alias Matrix = Array(Array(Int32)) def reorder_cols_by_col_perm(s : Matrix, x : Int32) t = s.clone t.each_index do |r| t.each_index do |c| s[ r ][ t[c][x] ] = t[r][c] end end end def reorder_rows_by_row_perm(s : Matrix, y : Int32) t = s.clone t.each_index do |r| t.each_index do |c| s[ t[y][r] ][ c ] = t[r][c] end end end def search(n : Int32, b : Matrix, k : Int32, t : Matrix, ops : Array(Int32)) : Bool return b == t if k == 0 (0...n*2).each do |op| ops[-k] = op s = t.clone if op < n reorder_cols_by_col_perm(s, op) else reorder_rows_by_row_perm(s, op-n) end return true if search(n, b, k-1, s, ops) end false end def select_col(s : Matrix, x : Int32) : Array(Int32) s.map &.[x] end def select_row(s : Matrix, y : Int32) : Array(Int32) s[y].dup end def cycle_size(perm : Array(Int32)) : Int32 t = Array.new(perm.size, 0) w = perm.dup (1..).each do |cnt| perm.each_with_index do |e, i| t[e] = w[i] end return cnt if perm == t w.replace t end end def solve(n : Int32, k : Int32, a : Matrix, b : Matrix) : Array(Int32) ops = Array.new(k, 0) search(n, b, k, a, ops) ops.map{ |op| if op < n perm = select_col(a, op) reorder_cols_by_col_perm(a, op) else perm = select_row(a, op-n) reorder_rows_by_row_perm(a, op-n) end z = op % n cycle_size(perm).pred.times.map{ z = perm[z % n] + (op // n)*n }.to_a }.reverse.flatten end def read_ints : Array(Int32) gets.not_nil!.split.map &.to_i end n,k = read_ints a = n.times.map{ read_ints.map &.pred }.to_a b = n.times.map{ read_ints.map &.pred }.to_a ans = solve(n, k, a, b) puts ans.size ans.each do |op| if op < n puts "C #{op+1}" else puts "R #{op+1-n}" end end