// The main code is at the very bottom. #[allow(unused_imports)] #[macro_use] pub mod spella { pub mod byte { pub use self::byte_char::*; pub use self::byte_str::*; pub use self::byte_string::*; pub use self::from_byte_str::*; mod byte_char { use std::fmt::{self, Debug, Display, Formatter}; #[derive(Clone, Copy, Default, PartialEq, Eq, PartialOrd, Ord, Hash)] pub struct ByteChar(pub u8); impl Debug for ByteChar { fn fmt(&self, f: &mut Formatter) -> fmt::Result { write!(f, "b'{}'", self.0 as char) } } impl Display for ByteChar { fn fmt(&self, f: &mut Formatter) -> fmt::Result { write!(f, "{}", self.0 as char) } } } mod byte_str { use spella::byte::{ByteChar, ByteString}; use std::fmt::{self, Debug, Display, Formatter}; use std::ops::{Deref, DerefMut}; #[derive(PartialEq, Eq, PartialOrd, Ord, Hash)] pub struct ByteStr([ByteChar]); macro_rules! cast { (mut $x:expr, $($T:ty)=>*) => { unsafe { &mut *($x $(as *mut $T)*) } }; ($x:expr, $($T:ty)=>*) => { unsafe { &*($x $(as *const $T)*) } }; } impl ByteStr { pub fn from_bytes(s: &[u8]) -> &Self { cast!(s, [u8] => [ByteChar] => ByteStr) } pub fn from_bytes_mut(s: &mut [u8]) -> &mut Self { cast!(mut s, [u8] => [ByteChar] => ByteStr) } pub fn from_byte_chars(s: &[ByteChar]) -> &Self { cast!(s, [ByteChar] => ByteStr) } pub fn from_byte_chars_mut(s: &mut [ByteChar]) -> &mut Self { cast!(mut s, [ByteChar] => ByteStr) } pub fn as_byte_chars(&self) -> &[ByteChar] { &self.0 } pub fn as_byte_chars_mut(&mut self) -> &mut [ByteChar] { &mut self.0 } pub fn as_bytes(&self) -> &[u8] { cast!(self, ByteStr => [ByteChar] => [u8]) } pub fn as_bytes_mut(&mut self) -> &mut [u8] { cast!(mut self, ByteStr => [ByteChar] => [u8]) } } impl ToOwned for ByteStr { type Owned = ByteString; fn to_owned(&self) -> ByteString { ByteString::from(self.0.to_owned()) } } impl Debug for ByteStr { fn fmt(&self, f: &mut Formatter) -> fmt::Result { write!(f, "b\"")?; for &c in &self.0 { write!(f, "{}", c)?; } write!(f, "\"") } } impl Display for ByteStr { fn fmt(&self, f: &mut Formatter) -> fmt::Result { for &c in &self.0 { write!(f, "{}", c)?; } Ok(()) } } impl Deref for ByteStr { type Target = [ByteChar]; fn deref(&self) -> &[ByteChar] { self.as_byte_chars() } } impl DerefMut for ByteStr { fn deref_mut(&mut self) -> &mut [ByteChar] { self.as_byte_chars_mut() } } } mod byte_string { use spella::byte::{ByteChar, ByteStr}; use std::borrow::{Borrow, BorrowMut}; use std::fmt::{self, Debug, Display, Formatter}; use std::ops::{Deref, DerefMut}; #[derive(Clone, Default, PartialEq, Eq, PartialOrd, Ord, Hash)] pub struct ByteString(Vec); impl ByteString { pub fn into_byte_chars(self) -> Vec { self.0 } pub fn as_byte_str(&self) -> &ByteStr { ByteStr::from_byte_chars(&self.0) } pub fn as_mut_byte_str(&mut self) -> &mut ByteStr { ByteStr::from_byte_chars_mut(&mut self.0) } } impl From> for ByteString { fn from(s: Vec) -> ByteString { ByteString(s) } } impl Borrow for ByteString { fn borrow(&self) -> &ByteStr { self.as_byte_str() } } impl BorrowMut for ByteString { fn borrow_mut(&mut self) -> &mut ByteStr { self.as_mut_byte_str() } } impl Debug for ByteString { fn fmt(&self, f: &mut Formatter) -> fmt::Result { Debug::fmt(self.as_byte_str(), f) } } impl Display for ByteString { fn fmt(&self, f: &mut Formatter) -> fmt::Result { Display::fmt(self.as_byte_str(), f) } } impl Deref for ByteString { type Target = ByteStr; fn deref(&self) -> &ByteStr { ByteStr::from_byte_chars(&self.0) } } impl DerefMut for ByteString { fn deref_mut(&mut self) -> &mut ByteStr { ByteStr::from_byte_chars_mut(&mut self.0) } } } mod from_byte_str { use spella::byte::{ByteChar, ByteStr, ByteString}; use std::error::Error; use std::fmt::{self, Debug, Display, Formatter}; use std::str::{self, FromStr, Utf8Error}; pub trait FromByteStr: Sized { type Err; fn from_byte_str(s: &ByteStr) -> Result; } macro_rules! fn_description { () => { fn description(&self) -> &str { "description() is deprecated; use Display" } }; } #[derive(Debug)] pub struct ParseByteCharError(ParseByteCharErrorKind); #[derive(Debug)] enum ParseByteCharErrorKind { EmptyByteStr, TooManyByteChars, } impl Display for ParseByteCharError { fn fmt(&self, f: &mut Formatter) -> fmt::Result { use self::ParseByteCharErrorKind::*; f.write_str(match self.0 { EmptyByteStr => "empty `ByteStr`", TooManyByteChars => "too many `ByteChar`s", }) } } impl Error for ParseByteCharError { fn_description! {} } impl FromByteStr for ByteChar { type Err = ParseByteCharError; fn from_byte_str(s: &ByteStr) -> Result { use self::ParseByteCharErrorKind::*; match s.len() { 1 => Ok(unsafe { *s.get_unchecked(0) }), 0 => Err(ParseByteCharError(EmptyByteStr)), _ => Err(ParseByteCharError(TooManyByteChars)), } } } #[derive(Debug)] pub enum ParseByteStringError {} impl Display for ParseByteStringError { fn fmt(&self, _: &mut Formatter) -> fmt::Result { match *self {} } } impl Error for ParseByteStringError { fn_description! {} } impl FromByteStr for ByteString { type Err = ParseByteStringError; fn from_byte_str(s: &ByteStr) -> Result { Ok(ByteString::from(s.to_vec())) } } pub struct ParseFromStrError(ParseFromStrErrorKind); enum ParseFromStrErrorKind { Utf8Error(Utf8Error), FromStrError(T::Err), } impl Debug for ParseFromStrError where T::Err: Debug, { fn fmt(&self, f: &mut Formatter) -> fmt::Result { use self::ParseFromStrErrorKind::*; match self.0 { Utf8Error(ref err) => f.debug_tuple("Utf8Error").field(err).finish(), FromStrError(ref err) => f.debug_tuple("FromStrError").field(err).finish(), } } } impl Display for ParseFromStrError where T::Err: Display, { fn fmt(&self, f: &mut Formatter) -> fmt::Result { use self::ParseFromStrErrorKind::*; match self.0 { Utf8Error(ref err) => write!(f, "{}", err), FromStrError(ref err) => write!(f, "{}", err), } } } impl Error for ParseFromStrError where T::Err: Debug + Display, { fn_description! {} } impl FromByteStr for T { type Err = ParseFromStrError; fn from_byte_str(s: &ByteStr) -> Result { use self::ParseFromStrErrorKind::*; str::from_utf8(s.as_bytes()) .map_err(|e| ParseFromStrError(Utf8Error(e))) .and_then(|s| s.parse().map_err(|e| ParseFromStrError(FromStrError(e)))) } } } } pub mod io { pub use self::scanner::*; mod scanner { use spella::byte::{ByteStr, FromByteStr}; use std::io::{self, BufRead}; #[derive(Debug)] pub struct Scanner { reader: R, buf: Vec, pos: usize, } const INITIAL_CAPACITY: usize = 32; impl Scanner { pub fn new(reader: R) -> Self { Scanner { reader: reader, buf: Vec::with_capacity(INITIAL_CAPACITY), pos: 0, } } pub fn next(&mut self) -> io::Result> { self.next_byte_str().map(T::from_byte_str) } pub fn next_byte_str(&mut self) -> io::Result<&ByteStr> { if self.buf.is_empty() { self.read_line()?; } loop { match self.buf.get(self.pos) { Some(&b' ') => self.pos += 1, Some(&b'\n') => self.read_line()?, Some(_) => break, None => return Err(io::Error::from(io::ErrorKind::UnexpectedEof)), } } let start = self.pos; self.pos += 1; loop { match self.buf.get(self.pos) { Some(&b' ') | Some(&b'\n') | None => break, Some(_) => self.pos += 1, } } Ok(ByteStr::from_bytes(&self.buf[start..self.pos])) } fn read_line(&mut self) -> io::Result<()> { self.buf.clear(); self.pos = 0; self.reader.read_until(b'\n', &mut self.buf)?; Ok(()) } } } } } mod prelude { pub use spella::byte::{ByteChar, ByteStr, ByteString}; pub use std::collections::*; pub use std::io::prelude::*; pub use std::iter::FromIterator; pub use std::marker::PhantomData; pub use std::num::Wrapping; pub use std::ops::{Range, RangeFrom, RangeTo}; pub use std::{cell, cmp, f64, i32, i64, isize, iter, mem, rc, str, time, u32, u64, usize}; } use prelude::*; const CUSTOM_STACK_SIZE_MEBIBYTES: Option = None; fn main() { fn exec_solver() { let stdin = std::io::stdin(); let stdout = std::io::stdout(); #[cfg(not(debug_assertions))] let mut writer = std::io::BufWriter::new(stdout.lock()); #[cfg(debug_assertions)] let mut writer = stdout.lock(); solve(stdin.lock(), &mut writer); writer.flush().unwrap(); } if let Some(stack_size_mebibytes) = CUSTOM_STACK_SIZE_MEBIBYTES { std::thread::Builder::new() .name("exec_solver".to_owned()) .stack_size(stack_size_mebibytes * 1024 * 1024) .spawn(exec_solver) .unwrap() .join() .unwrap(); } else { exec_solver(); } } fn solve(reader: R, mut writer: W) { let mut _scanner = spella::io::Scanner::new(reader); #[allow(unused_macros)] macro_rules! scan { ($T:ty) => { _scanner.next::<$T>().unwrap().unwrap() }; ($($T:ty),+) => { ($(scan!($T)),+) }; ($($T:ty),+; $n:expr $(; $m:expr)*) => {{ (0..$n).map(|_| scan!($($T),+ $(; $m)*)).collect::>() }}; } #[allow(unused_macros)] macro_rules! scan_iter { ($($T:ty),+; $n:expr) => { (0..$n).map(|_| scan!($($T),+)) }; } #[allow(unused_macros)] macro_rules! print { ($fmt:expr) => { write!(writer, $fmt).unwrap() }; ($fmt:expr, $($arg:tt)*) => { write!(writer, $fmt, $($arg)*).unwrap() }; } #[allow(unused_macros)] macro_rules! println { ($fmt:expr) => { writeln!(writer, $fmt).unwrap() }; ($fmt:expr, $($arg:tt)*) => { writeln!(writer, $fmt, $($arg)*).unwrap() }; } #[allow(unused_macros)] macro_rules! eprint { ($fmt:expr) => { #[cfg(debug_assertions)] write!(std::io::stderr(), $fmt).unwrap() }; ($fmt:expr, $($arg:tt)*) => { #[cfg(debug_assertions)] write!(std::io::stderr(), $fmt, $($arg)*).unwrap() }; } #[allow(unused_macros)] macro_rules! eprintln { ($fmt:expr) => { #[cfg(debug_assertions)] writeln!(std::io::stderr(), $fmt).unwrap() }; ($fmt:expr, $($arg:tt)*) => { #[cfg(debug_assertions)] writeln!(std::io::stderr(), $fmt, $($arg)*).unwrap() }; } #[allow(unused_macros)] macro_rules! dbg { ($($x:expr),+) => {{ eprintln!(concat!("[{}:{}] ", $(stringify!($x), " = {:?}; "),+), file!(), line!(), $($x),+); }}; } let (h, w) = scan!(usize, usize); let mut a = scan!(u8; h; w); let q = scan!(usize); let mut cnt_0 = (0..h) .flat_map(|i| iter::repeat(i).zip(0..w)) .filter(|&(i, j)| a[i][j] == 0) .count(); let mut queue = VecDeque::new(); for (r, c, new_color) in scan_iter!(isize, isize, u8; q) { dbg!(a, cnt_0); if cnt_0 == 0 || cnt_0 == h * w { cnt_0 = if new_color == 0 { h * w } else { 0 }; continue; } let (r, c) = (r - 1, c - 1); let old_color = a[r as usize][c as usize]; if new_color == old_color { continue; } queue.clear(); macro_rules! next { ($r:expr, $c:expr) => { if 0 <= $r && $r < h as isize && 0 <= $c && $c < w as isize && a[$r as usize][$c as usize] == old_color { a[$r as usize][$c as usize] = new_color; if new_color == 0 { cnt_0 += 1; } else { cnt_0 -= 1; } queue.push_back(($r, $c)); } }; } next!(r, c); while let Some((r, c)) = queue.pop_front() { next!(r + 1, c); next!(r - 1, c); next!(r, c + 1); next!(r, c - 1); } } for i in 0..h { for j in 0..w { let x = if cnt_0 == 0 { 1 } else if cnt_0 == h * w { 0 } else { a[i][j] }; print!("{} ", x); } println!(""); } }