use fio::*; use std::cmp::Reverse; mod flow { use std::collections::VecDeque; use std::ops::{Add, AddAssign, Sub, SubAssign}; pub trait Integral: 'static + Send + Sync + Copy + Clone + Ord + Add + Sub + AddAssign + SubAssign { /// Returns 0. fn zero() -> Self; /// Returns maximum value representable in type. fn max_value() -> Self; } macro_rules! integral_impl { ($($SelfT:ty)*) => { $(impl Integral for $SelfT { fn zero() -> Self { 0 } fn max_value() -> Self { Self::MAX } })* } } integral_impl!(i8 i16 i32 i64 u8 u16 u32 u64 usize isize); struct FlowCalc<'a, Cap: Integral> { g: &'a mut Maxflow, s: usize, t: usize, lim: Cap, lev: Vec, it: Vec, q: VecDeque, } impl FlowCalc<'_, Cap> { fn bfs(&mut self) { self.lev.fill(-1); self.lev[self.s] = 0; self.q.clear(); self.q.push_back(self.s); while let Some(v) = self.q.pop_front() { for e in &self.g.g[v] { if e.cap == Cap::zero() || self.lev[e.to] != -1 { continue; } self.lev[e.to] = self.lev[v] + 1; if e.to == self.t { return; } self.q.push_back(e.to); } } } fn dfs(&mut self, v: usize, f: Cap) -> Cap { if v == self.s { return f; } let mut r = Cap::zero(); let prv_lv = self.lev[v] - 1; for i in self.it[v]..self.g.g[v].len() { self.it[v] = i; let _Edg { to: e_to, rev: e_rev, .. } = self.g.g[v][i]; if prv_lv != self.lev[e_to] || self.g.g[e_to][e_rev].cap == Cap::zero() { continue; } let d = self.dfs(e_to, self.g.g[e_to][e_rev].cap.min(f - r)); if d == Cap::zero() { continue; } self.g.g[v][i].cap += d; self.g.g[e_to][e_rev].cap -= d; r += d; if r == f { return r; } } self.it[v] = self.g.g[v].len(); r } } pub struct Maxflow { n: usize, /// i'th edge: g[.0][.1] e_pos: Vec<(usize, usize)>, g: Vec>>, } /// g[g[i][j].to][g[i][j].rev] = i #[derive(Clone, Debug)] struct _Edg { to: usize, rev: usize, cap: Cap, } #[derive(Clone, Debug)] pub struct Edge { pub from: usize, pub to: usize, pub cap: Cap, pub flow: Cap, } impl Maxflow { pub fn new(n: usize) -> Self { Self { n, e_pos: vec![], g: vec![vec![]; n], } } /// Add an edge from -> to with capacity cap. Returns an index of edge. pub fn add_edge(&mut self, from: usize, to: usize, cap: Cap) -> usize { assert!(from < self.n); assert!(to < self.n); assert!(Cap::zero() <= cap); let m = self.e_pos.len(); self.e_pos.push((from, self.g[from].len())); let rev = self.g[to].len() + if from == to { 1 } else { 0 }; self.g[from].push(_Edg { to, rev, cap }); let rev = self.g[from].len() - 1; self.g[to].push(_Edg { to: from, rev, cap: Cap::zero(), }); m } pub fn get_edge(&mut self, i: usize) -> Edge { assert!(i < self.e_pos.len()); let e = &self.g[self.e_pos[i].0][self.e_pos[i].1]; let r = &self.g[e.to][e.rev]; Edge { from: self.e_pos[i].0, to: e.to, cap: e.cap + r.cap, flow: r.cap, } } pub fn change_edge(&mut self, i: usize, new_cap: Cap, new_flow: Cap) { assert!(i < self.e_pos.len()); assert!((Cap::zero()..=new_cap).contains(&new_flow)); let e = &mut self.g[self.e_pos[i].0][self.e_pos[i].1]; e.cap = new_cap - new_flow; let (to, rev) = (e.to, e.rev); self.g[to][rev].cap = new_flow; } pub fn flow(&mut self, s: usize, t: usize) -> Cap { self.flow_with_capacity(s, t, Cap::max_value()) } pub fn flow_with_capacity(&mut self, s: usize, t: usize, limit: Cap) -> Cap { let n = self.n; assert!(s < n); assert!(t < n); assert_ne!(s, t); assert!(Cap::zero() <= limit); let mut calc = FlowCalc { g: self, s, t, lim: limit, lev: vec![0; n], it: vec![0; n], q: VecDeque::new(), }; let mut r = Cap::zero(); while r < limit { calc.bfs(); if calc.lev[t] == -1 { break; } calc.it.fill(0); r += calc.dfs(t, limit - r); } r } } } use flow::*; fn main() { let w = read::(); let n = read::(); let j = read_vec::(); let m = read::(); let c = read_vec::(); let mut g = Maxflow::::new(n + m + 2); let source = n + m; let sink = n + m + 1; for (i, v) in j.into_iter().enumerate() { g.add_edge(source, i, v); } for (i, v) in c.into_iter().enumerate() { g.add_edge(n + i, sink, v); } for i in 0..m { let qs = read_vec::(); let qs = qs.into_iter().skip(1).map(|x| x - 1).collect::>(); if let Some(lst) = qs.last() { for j in 0..qs[0] { g.add_edge(j, n + i, u16::MAX); } for w in qs.windows(2) { for j in w[0] + 1..w[1] { g.add_edge(j, n + i, u16::MAX); } } for j in lst + 1..n { g.add_edge(j, n + i, u16::MAX); } } else { for j in 0..n { g.add_edge(j, n + i, u16::MAX); } } } println!( "{}", if w == g.flow_with_capacity(source, sink, w) { "SHIROBAKO" } else { "BANSAKUTSUKITA" } ); } 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() }); }; }