// WA? fn main() { let (m, ans, mut expr) = read(); let res = Solver::solve(m, &expr); if res.0[ans].0 { let mut x = 0; for s in expr.iter_mut() { if *s == b'$' || *s == b'&' { *s = res.0[ans].1[x]; x += 1; } } let ans = expr.iter().map(|c| *c as char).collect::(); println!("{}", ans); } else { println!("-1"); } } fn read() -> (usize, usize, Vec) { let mut s = String::new(); use std::io::*; std::io::stdin().read_to_string(&mut s).unwrap(); let mut it = s.trim().split_whitespace(); let m = it.next().unwrap().parse().unwrap(); let ans = it.next().unwrap().parse().unwrap(); let expr = it.next().unwrap().bytes().collect(); (m, ans, expr) } struct Solver<'a> { m: usize, s: &'a [u8], pos: usize, } impl<'a> Solver<'a> { fn solve(m: usize, s: &'a [u8]) -> DP { let mut state = Solver { m: m, s: s, pos: 0 }; let res = state.expression(); assert!(state.pos == state.s.len()); res } fn next(&self) -> Option { self.s.get(self.pos).cloned() } fn eat(&mut self) -> Option { self.s.get(self.pos).cloned().map(|c| { self.pos += 1; c }) } fn expression(&mut self) -> DP { let mut res = self.term(); while self.next().map_or(false, |c| c == b'$') { self.eat(); let rhs = self.term(); res = res.add_sub(&rhs); } res } fn term(&mut self) -> DP { let mut res = self.factor(); while self.next().map_or(false, |c| c == b'&') { self.eat(); let rhs = self.factor(); res = res.mul_div(&rhs); } res } fn factor(&mut self) -> DP { let c = self.next().unwrap(); if c == b'(' { self.eat(); let res = self.expression(); assert_eq!(self.eat(), Some(b')')); res } else { assert!(b'0' <= c && c <= b'9'); let mut v = 0; while self.next().map_or(false, |c| b'0' <= c && c <= b'9') { v = 10 * v + (self.eat().unwrap() - b'0') as usize; assert!(v <= self.m); } DP::new(self.m, v) } } } struct DP(Vec<(bool, Vec)>); impl DP { fn zero(m: usize) -> Self { DP(vec![(false, vec![]); m + 2]) } fn new(m: usize, x: usize) -> Self { assert!(1 <= m && m <= 300); assert!(x <= m); let mut dp = vec![(false, vec![]); m + 2]; dp[x].0 = true; DP(dp) } fn add_sub(&self, rhs: &Self) -> Self { assert!(self.0.len() == rhs.0.len()); let mut res = DP::zero(self.0.len() - 1); for (l, a) in self.0.iter().enumerate().filter(|p| p.1 .0) { for (r, b) in rhs.0.iter().enumerate().filter(|p| p.1 .0) { res.fill(l + r, a, b'+', b); res.fill(l - r, a, b'-', b); } } res } fn mul_div(&self, rhs: &Self) -> Self { assert!(self.0.len() == rhs.0.len()); let mut res = DP::zero(self.0.len() - 1); for (l, a) in self.0.iter().enumerate().filter(|p| p.1 .0) { for (r, b) in rhs.0.iter().enumerate().filter(|p| p.1 .0) { res.fill(l * r, a, b'*', b); if r > 0 { res.fill(l / r, a, b'/', b); } } } res } fn fill(&mut self, x: usize, a: &(bool, Vec), c: u8, b: &(bool, Vec)) { if x < self.0.len() && !self.0[x].0 { self.0[x].0 = true; self.0[x].1 = a.1.iter() .cloned() .chain(std::iter::once(c)) .chain(b.1.iter().cloned()) .collect(); } } }