use std::iter::{once, repeat}; use fio::*; fn transpose(a: Vec>) -> Vec> { let h = a.len(); let w = a[0].len(); let mut ret = vec![vec![0; h]; w]; for r in 0..h { for c in 0..w { ret[c][r] = a[r][c]; } } ret } fn merge_vert( a1: (usize, Vec>), a2: (usize, Vec>), ) -> (usize, Vec>) { assert_eq!(a1.1[0].len(), a2.1[0].len()); let mut w = a1.1; w.extend( a2.1.into_iter() .map(|r| r.into_iter().map(|x| x + a1.0).collect()), ); (a1.0 + a2.0, w) } fn merge_horz( a1: (usize, Vec>), a2: (usize, Vec>), ) -> (usize, Vec>) { assert_eq!(a1.1.len(), a2.1.len()); let w: Vec> = a1.1.into_iter() .zip(a2.1.into_iter()) .map(|(mut r1, r2)| { r1.extend(r2.into_iter().map(|x| x + a1.0)); r1 }) .collect(); (a1.0 + a2.0, w) } fn get_c(n: usize, m: usize) -> Option<(usize, Vec>)> { if n > m { return get_c(m, n).map(|(k, ret)| (k, transpose(ret))); } if n <= 2 { return None; } if n == 3 { if m % 2 == 1 { return None; } if m == 4 { return Some(( 2, vec![vec![1, 1, 1, 2], vec![1, 2, 1, 2], vec![1, 2, 2, 2]], )); } if m == 6 { return Some(( 3, vec![ vec![1, 2, 2, 2, 2, 3], vec![1, 2, 1, 3, 2, 3], vec![1, 1, 1, 3, 3, 3], ], )); } let a1 = get_c(n, m - 4).unwrap(); let a2 = get_c(n, 4).unwrap(); return Some(merge_horz(a1, a2)); } if n == 4 { return Some(( 2, vec![ vec![1; m], repeat(2).take(m - 1).chain(once(1)).collect(), once(2).chain(repeat(1).take(m - 1)).collect(), vec![2; m], ], )); } let (v, mut a) = get_c(n - 1, m - 2).unwrap(); for x in a.iter_mut() { x.insert(0, v + 1); x.push(v + 1); } a.push(vec![v + 1; m]); Some((v + 1, a)) } fn get_t(n: usize, m: usize) -> Option<(usize, Vec>)> { if n > m { return get_t(m, n).map(|(k, ret)| (k, transpose(ret))); } if n <= 2 { return None; } if n == 3 { if m < 6 { return None; } return Some(( 4, vec![ once(1) .chain(repeat(2).take(m - 2)) .chain(once(4)) .collect(), repeat(1) .take(m - 4) .chain(once(2)) .chain(once(3)) .chain(repeat(4).take(2)) .collect(), once(1) .chain(repeat(3).take(m - 2)) .chain(once(4)) .collect(), ], )); } if n == 4 { return Some(( 4, vec![ repeat(1).take(m - 1).chain(once(2)).collect(), once(3) .chain(once(1)) .chain(repeat(2).take(m - 2)) .collect(), repeat(3) .take(m - 2) .chain(once(4)) .chain(once(2)) .collect(), once(3).chain(repeat(4).take(m - 1)).collect(), ], )); } if n == 5 { return Some(( 5, vec![ repeat(1).take(m - 1).chain(once(4)).collect(), once(2) .chain(once(1)) .chain(repeat(4).take(m - 2)) .collect(), repeat(2) .take(m - 2) .chain(once(5)) .chain(once(4)) .collect(), once(2) .chain(once(3)) .chain(repeat(5).take(m - 3)) .chain(once(4)) .collect(), repeat(3) .take(m - 2) .chain(once(5)) .chain(once(4)) .collect(), ], )); } let a1 = get_t(n - 3, m).unwrap(); let a2 = get_t(3, m).unwrap(); Some(merge_vert(a1, a2)) } fn get_ct(n: usize, m: usize) -> Option<(usize, Vec>)> { if n > m { return get_ct(m, n).map(|(k, ret)| (k, transpose(ret))); } if n <= 2 { return None; } if n == 3 { return Some(( 2, vec![ repeat(1).take(m - 1).chain(once(2)).collect(), once(1).chain(repeat(2).take(m - 1)).collect(), repeat(1).take(m - 1).chain(once(2)).collect(), ], )); } if n == 4 { return Some(( 3, vec![ vec![3; m], repeat(1) .take(m - 2) .chain(once(3)) .chain(once(2)) .collect(), once(1).chain(repeat(2).take(m - 1)).collect(), repeat(1).take(m - 1).chain(once(2)).collect(), ], )); } if n == 5 { return Some(( 4, vec![ vec![3; m], repeat(1) .take(m - 2) .chain(once(3)) .chain(once(2)) .collect(), once(1).chain(repeat(2).take(m - 1)).collect(), repeat(1) .take(m - 2) .chain(once(4)) .chain(once(2)) .collect(), vec![4; m], ], )); } let a1 = get_ct(n - 3, m).unwrap(); let a2 = get_ct(3, m).unwrap(); Some(merge_vert(a1, a2)) } fn main() { let [h, w] = read_tuple::(); for f in [get_c, get_t, get_ct] { if let Some((k, ret)) = f(h, w) { println!("{}", k); for r in ret { for c in r { print!("{} ", c); } println!(); } } else { println!("-1"); } } } mod fio { use std::{ cell::RefCell, convert::TryInto, fmt::Debug, io::{BufRead, BufWriter, StdinLock, StdoutLock, stdin, stdout}, str::FromStr, }; thread_local! { pub static STDIN: RefCell> = RefCell::new(stdin().lock()); pub static STDOUT: RefCell>> = RefCell::new(BufWriter::new(stdout().lock())); } #[allow(dead_code)] pub fn read() -> T where ::Err: Debug, { read_line().parse().unwrap() } #[allow(dead_code)] pub fn read_vec() -> Vec where ::Err: Debug, { read_line() .split_whitespace() .map(|x| x.parse().unwrap()) .collect() } #[allow(dead_code)] pub fn read_tuple() -> [T; N] where T: FromStr + Debug, ::Err: Debug, { read_vec::().try_into().unwrap() } /// whitespace at the end of the line is ignored pub fn read_line() -> String { let mut s = String::new(); STDIN.with(|cell| { cell.borrow_mut().read_line(&mut s).unwrap(); }); String::from_str(s.trim_end()).unwrap() } } #[macro_export] macro_rules! print { ($($t:tt)*) => { fio::STDOUT.with(|cell|{ use std::io::Write; write!(cell.borrow_mut(), $($t)*).unwrap() })}; } #[macro_export] macro_rules! println { ($($t:tt)*) => { fio::STDOUT.with(|cell| { use std::io::Write; writeln!(cell.borrow_mut(), $($t)*).unwrap() }) }; } #[macro_export] macro_rules! flush { () => { fio::STDOUT.with(|cell| { use std::io::Write; cell.borrow_mut().flush().unwrap() }); }; }