#[allow(unused_imports)] use std::cmp::{max, min}; #[allow(unused_imports)] use std::collections::{HashMap, HashSet}; mod util { use std::io::stdin; use std::str::FromStr; use std::fmt::Debug; #[allow(dead_code)] pub fn line() -> String { let mut line: String = String::new(); stdin().read_line(&mut line).unwrap(); line.trim().to_string() } #[allow(dead_code)] pub fn get() -> T where ::Err: Debug, { let mut line: String = String::new(); stdin().read_line(&mut line).unwrap(); line.trim().parse().unwrap() } #[allow(dead_code)] pub fn gets() -> Vec where ::Err: Debug, { let mut line: String = String::new(); stdin().read_line(&mut line).unwrap(); line.split_whitespace() .map(|t| t.parse().unwrap()) .collect() } #[allow(dead_code)] pub fn get2() -> (T, U) where ::Err: Debug, ::Err: Debug, { let mut line: String = String::new(); stdin().read_line(&mut line).unwrap(); let mut iter = line.split_whitespace(); ( iter.next().unwrap().parse().unwrap(), iter.next().unwrap().parse().unwrap(), ) } #[allow(dead_code)] pub fn get3() -> (S, T, U) where ::Err: Debug, ::Err: Debug, ::Err: Debug, { let mut line: String = String::new(); stdin().read_line(&mut line).unwrap(); let mut iter = line.split_whitespace(); ( iter.next().unwrap().parse().unwrap(), iter.next().unwrap().parse().unwrap(), iter.next().unwrap().parse().unwrap(), ) } } #[allow(unused_macros)] macro_rules! debug { ($x: expr) => { println!("{}: {:?}", stringify!($x), $x) } } const M: u64 = 1000000007; fn routes(x: usize, y: usize, cache: &mut Vec>>) -> u64 { if let Some(res) = cache[x][y] { return res; } if x == 0 || y == 0 { return 1; } let left = if x == 0 { 1 } else { routes(x - 1, y, cache) }; let down = if y == 0 { 1 } else { routes(x, y - 1, cache) }; let res = left + down; cache[x][y] = Some(res); res } fn main() { let hwkp: Vec = util::gets(); let h = hwkp[0]; let w = hwkp[1]; let k = hwkp[2]; let p = hwkp[3]; let xyn: Vec<(usize, usize, String)> = (0..k).map(|_| util::get3()).collect(); let (a, friends) = (0u64..1 << k) .filter(|b| b.count_ones() == p as u32) .map(|b| { let mut cache = vec![vec![None; w + 1]; h + 1]; cache[0][0] = Some(0); for i in 0..k { if b >> i & 1 != 1 { cache[xyn[i].0][xyn[i].1] = Some(0); } } (routes(h, w, &mut cache), b) }) .max() .unwrap(); println!("{}", a % M); for i in (0..k).filter(|&i| friends >> i & 1 == 1) { println!("{}", xyn[i].2); } }