#line 2 "library/KowerKoint/base.hpp" #ifdef DEBUG #define _GLIBCXX_DEBUG #endif #include using namespace std; #define REP(i, n) for(int i = 0; i < (int)(n); i++) #define FOR(i, a, b) for(ll i = a; i < (ll)(b); i++) #define ALL(a) (a).begin(),(a).end() #define END(...) { print(__VA_ARGS__); return; } using VI = vector; using VVI = vector; using VVVI = vector; using ll = long long; using VL = vector; using VVL = vector; using VVVL = vector; using ull = unsigned long long; using VUL = vector; using VVUL = vector; using VVVUL = vector; using VD = vector; using VVD = vector; using VVVD = vector; using VS = vector; using VVS = vector; using VVVS = vector; using VC = vector; using VVC = vector; using VVVC = vector; using P = pair; using VP = vector

; using VVP = vector; using VVVP = vector; using LP = pair; using VLP = vector; using VVLP = vector; using VVVLP = vector; template using PQ = priority_queue; template using GPQ = priority_queue, greater>; constexpr int INF = 1001001001; constexpr ll LINF = 1001001001001001001ll; constexpr int DX[] = {1, 0, -1, 0}; constexpr int DY[] = {0, 1, 0, -1}; template< typename T1, typename T2 > ostream &operator<<(ostream &os, const pair< T1, T2 >& p) { os << p.first << " " << p.second; return os; } template< typename T1, typename T2 > istream &operator>>(istream &is, pair< T1, T2 > &p) { is >> p.first >> p.second; return is; } template< typename T > ostream &operator<<(ostream &os, const vector< T > &v) { for(int i = 0; i < (int) v.size(); i++) { os << v[i] << (i + 1 != (int) v.size() ? " " : ""); } return os; } template< typename T > istream &operator>>(istream &is, vector< T > &v) { for(T &in : v) is >> in; return is; } void print() { cout << '\n'; } template void print(const T &t) { cout << t << '\n'; } template void print(const Head &head, const Tail &... tail) { cout << head << ' '; print(tail...); } #ifdef DEBUG void dbg() { cerr << '\n'; } template void dbg(const T &t) { cerr << t << '\n'; } template void dbg(const Head &head, const Tail &... tail) { cerr << head << ' '; dbg(tail...); } #else template void dbg(const Args &... args) {} #endif template vector> split(typename vector::const_iterator begin, typename vector::const_iterator end, T val) { vector> res; vector cur; for(auto it = begin; it != end; it++) { if(*it == val) { res.push_back(cur); cur.clear(); } else cur.push_back(*it); } res.push_back(cur); return res; } vector split(typename string::const_iterator begin, typename string::const_iterator end, char val) { vector res; string cur = ""; for(auto it = begin; it != end; it++) { if(*it == val) { res.push_back(cur); cur.clear(); } else cur.push_back(*it); } res.push_back(cur); return res; } template< typename T1, typename T2 > inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); } template< typename T1, typename T2 > inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); } template pair> compress(const vector &a) { int n = a.size(); vector x; REP(i, n) x.push_back(a[i]); sort(ALL(x)); x.erase(unique(ALL(x)), x.end()); VI res(n); REP(i, n) res[i] = lower_bound(ALL(x), a[i]) - x.begin(); return make_pair(res, x); } template auto rle(It begin, It end) { vector> res; if(begin == end) return res; auto pre = *begin; int num = 1; for(auto it = begin + 1; it != end; it++) { if(pre != *it) { res.emplace_back(pre, num); pre = *it; num = 1; } else num++; } res.emplace_back(pre, num); return res; } template vector> rle_sort(It begin, It end) { vector cloned(begin, end); sort(ALL(cloned)); auto e = rle(ALL(cloned)); sort(ALL(e), [](const auto& l, const auto& r) { return l.second < r.second; }); return e; } template pair, vector> factorial(int n) { vector res(n+1), rev(n+1); res[0] = 1; REP(i, n) res[i+1] = res[i] * (i+1); rev[n] = 1 / res[n]; for(int i = n; i > 0; i--) { rev[i-1] = rev[i] * i; } return make_pair(res, rev); } #line 3 "library/KowerKoint/operator.hpp" template T add_op(T a, T b) { return a + b; } template T sub_op(T a, T b) { return a - b; } template T zero_e() { return T(0); } template T div_op(T a, T b) { return a / b; } template T mult_op(T a, T b) { return a * b; } template T one_e() { return T(1); } template T xor_op(T a, T b) { return a ^ b; } template T and_op(T a, T b) { return a & b; } template T or_op(T a, T b) { return a | b; } ll mod3() { return 998244353LL; } ll mod7() { return 1000000007LL; } ll mod9() { return 1000000009LL; } template T max_op(T a, T b) { return max(a, b); } template T min_op(T a, T b) { return min(a, b); } template T max_e() { return numeric_limits::max(); } template T min_e() { return numeric_limits::min(); } #line 2 "library/KowerKoint/integer/extgcd.hpp" ll extgcd(ll a, ll b, ll& x, ll& y) { x = 1, y = 0; ll nx = 0, ny = 1; while(b) { ll q = a / b; tie(a, b) = LP(b, a % b); tie(x, nx) = LP(nx, x - nx*q); tie(y, ny) = LP(ny, y - ny*q); } return a; } #line 2 "library/KowerKoint/integer/pow-mod.hpp" ll inv_mod(ll n, ll m) { ll x, y; assert(extgcd(n, m, x, y) == 1); x %= m; if(x < 0) x += m; return x; } ll pow_mod(ll a, ll n, ll m) { if(n == 0) return 1LL; if(n < 0) return inv_mod(pow_mod(a, -n, m), m); ll res = 1; while(n) { if(n & 1) { res *= a; res %= m; } n >>= 1; a *= a; a %= m; } return res; } #line 4 "library/KowerKoint/integer/modint.hpp" template struct Modint { ll val; Modint(): val(0) {} Modint(ll x): val(x) { val %= mod(); if(val < 0) val += mod(); } Modint& operator+=(const Modint& r) { val += r.val; if(val >= mod()) val -= mod(); return *this; } friend Modint operator+(const Modint& l, const Modint& r) { return Modint(l) += r; } Modint& operator-=(const Modint& r) { val -= r.val; if(val < 0) val += mod(); return *this; } friend Modint operator-(const Modint& l, const Modint& r) { return Modint(l) -= r; } Modint& operator*=(const Modint& r) { val *= r.val; val %= mod(); return *this; } Modint operator*(const Modint& r) { return (Modint(*this) *= r); } friend Modint operator*(const Modint& l, const Modint& r) { return Modint(l) *= r; } Modint pow(ll n) const { return Modint(pow_mod(val, n, mod())); } Modint inv() const { return Modint(inv_mod(val, mod())); } Modint& operator/=(const Modint& r) { return (*this *= r.inv()); } friend Modint operator/(const Modint& l, const Modint& r) { return Modint(l) /= r; } Modint& operator^=(const ll n) { val = pow_mod(val, n, mod()); return *this; } Modint operator^(const ll n) { return this->pow(n); } Modint operator+() const { return *this; } Modint operator-() const { return Modint() - *this; } Modint& operator++() { val++; if(val == mod()) val = 0LL; return *this; } Modint& operator++(int) { Modint res(*this); ++*this; return res; } Modint& operator--() { if(val == 0LL) val = mod(); val--; return *this; } Modint& operator--(int) { Modint res(*this); --*this; return res; } friend bool operator==(const Modint& l, const Modint& r) { return l.val == r.val; } friend bool operator!=(const Modint& l, const Modint& r) { return l.val != r.val; } static pair, vector> factorial(int n) { vector fact(n+1), rfact(n+1); fact[0] = 1; REP(i, n) fact[i+1] = fact[i] * (i+1); rfact[n] = 1 / fact[n]; for(int i = n-1; i >= 0; i--) rfact[i] = rfact[i+1] * (i+1); return {fact, rfact}; } friend istream& operator>>(istream& is, Modint& mi) { is >> mi.val; return is; } friend ostream& operator<<(ostream& os, const Modint& mi) { os << mi.val; return os; } }; using MI3 = Modint; using V3 = vector; using VV3 = vector; using VVV3 = vector; using MI7 = Modint; using V7 = vector; using VV7 = vector; using VVV7 = vector; using MI9 = Modint; using V9 = vector; using VV9 = vector; using VVV9 = vector; #line 3 "library/KowerKoint/counting/counting.hpp" template struct Counting { vector fact, ifact; Counting() {} Counting(ll n) { expand(n); } void expand(ll n) { ll sz = (ll)fact.size(); if(sz > n) return; fact.resize(n+1); ifact.resize(n+1); fact[0] = 1; FOR(i, max(1LL, sz), n+1) fact[i] = fact[i-1] * i; ifact[n] = 1 / fact[n]; for(ll i = n-1; i >= sz; i--) ifact[i] = ifact[i+1] * (i+1); } T p(ll n, ll r) { assert(n >= r); assert(r >= 0); expand(n); return fact[n] * ifact[n-r]; } T c(ll n, ll r) { assert(n >= r); assert(r >= 0); expand(n); return fact[n] * ifact[r] * ifact[n-r]; } T h(ll n, ll r) { assert(n >= 0); assert(r >= 0); return c(n+r-1, r); } T stirling(ll n, ll k) { assert(n >= k); assert(k >= 0); if(n == 0) return 1; T res = 0; int sign = k%2? -1 : 1; expand(k); REP(i, k+1) { res += sign * ifact[i] * ifact[k-i] * T(i).pow(n); sign *= -1; } return res; } vector> stirling_table(ll n, ll k) { assert(n >= 0 && k >= 0); vector> res(n+1, vector(k+1)); res[0][0] = 1; FOR(i, 1, n+1) FOR(j, 1, k+1) { res[i][j] = res[i-1][j-1] + j * res[i-1][j]; } return res; } T bell(ll n, ll k) { assert(n >= 0 && k >= 0); expand(k); vector tmp(k+1); int sign = 1; tmp[0] = 1; FOR(i, 1, k+1) { sign *= -1; tmp[i] = tmp[i-1] + sign * ifact[i]; } T res = 0; REP(i, k+1) { res += T(i).pow(n) * ifact[i] * tmp[k-i]; } return res; } vector> partition_table(ll n, ll k) { assert(n >= 0); vector> res(n+1, vector(k+1)); REP(i, k+1) res[0][i] = 1; FOR(i, 1, n+1) FOR(j, 1, k+1) { res[i][j] = res[i][j-1] + (i v; int n, bnum; Bitset(int n_ = 0) : n(n_) { bnum = (n+63) / 64; v.resize(bnum); } int operator[](int i) { return (v[i/64] >> (i%64)) & 1; } int count() { int c = 0; for (int i = 0; i < v.size(); i++) { c += __builtin_popcountll(v[i]); } return c; } int count_range(int l, int r) { int c = 0; int l2 = (l+63) / 64; int r2 = r / 64; for(int i = l2; i < r2; i++) { c += __builtin_popcountll(v[i]); } if(l < l2 * 64) { for(int i = l % 64; i < 64; i++) c += (v[l2-1] >> i) & 1; } if(r2 * 64 < r) { for(int i = 0; i < r % 64; i++) c += (v[r2] >> i) & 1; } return c; } bool all() { return count() == n; } bool any() { return count() > 0; } bool none() { return count() == 0; } void set(int i) { v[i / 64] |= 1ull << (i % 64); } void reset(int i) { v[i / 64] &= ~(1ull << (i % 64)); } void flip(int i) { v[i / 64] ^= 1ull << (i % 64); } void resize(int n_) { n = n_; v.resize((n+63) / 64); correct(); } void all_set() { fill(v.begin(), v.end(), ~0ULL); correct(); } void all_reset() { fill(v.begin(), v.end(), 0); } void all_flip() { for (int i = 0; i < v.size(); i++) { v[i] = ~v[i]; } correct(); } Bitset& operator&=(const Bitset& b) { for(int i = 0; i < min(bnum, b.bnum); i++) { v[i] &= b.v[i]; } return *this; } Bitset operator&(const Bitset& b) const { return Bitset(*this) &= b; } Bitset& operator|=(const Bitset& b) { for(int i = 0; i < min(bnum, b.bnum); i++) { v[i] |= b.v[i]; } correct(); return *this; } Bitset operator|(const Bitset& b) const { return Bitset(*this) |= b; } Bitset& operator^=(const Bitset& b) { for(int i = 0; i < min(bnum, b.bnum); i++) { v[i] ^= b.v[i]; } correct(); return *this; } Bitset operator^(const Bitset& b) const { return Bitset(*this) ^= b; } Bitset operator~() const { Bitset b(*this); b.all_flip(); return b; } bool operator==(const Bitset& b) const { return v == b.v; } bool operator!=(const Bitset& b) const { return v != b.v; } Bitset& operator<<=(int sz) { for(int i = bnum-1; i >= 0; i--) { if(i-sz/64 >= 0) v[i] = v[i-sz/64] << (sz%64); if(i-sz/64-1 >= 0) v[i] |= v[i-sz/64-1] >> (64-sz%64); } correct(); return *this; } Bitset operator<<(int sz) const { return Bitset(*this) <<= sz; } Bitset& operator>>=(int sz) { for(int i = 0; i < bnum; i++) { if(i+sz/64 < bnum) v[i] = v[i+sz/64] >> (sz%64); if(i+sz/64+1 < bnum) v[i] |= v[i+sz/64+1] << (64-sz%64); } return *this; } Bitset operator>>(int sz) const { return Bitset(*this) >>= sz; } }; #line 3 "Contests/main.cpp" /* #include */ /* using namespace atcoder; */ /* #include "KowerKoint/expansion/ac-library/all.hpp" */ struct Component { int op_pos; Bitset cand; }; int m, ans; string expr; map number, factor, term, expression; void pre_number(int l, int r) { Bitset b(m+1); int res = 0; FOR(i, l, r) { res *= 10; res += expr[i] - '0'; } b.set(res); number[P(l, r)] = {r, b}; } void pre_expression(int, int); void pre_factor(int l, int r) { if(expr[l] == '(') { pre_expression(l+1, r-1); factor[P(l, r)] = {l, expression[P(l+1,r-1)].cand}; } else { pre_number(l, r); factor[P(l, r)] = number[P(l, r)]; } } void pre_term(int l, int r) { int p = r-1; int blace = 0; while(p >= l && expr[p] != '&' || blace != 0) { if(expr[p] == ')') blace++; if(expr[p] == '(') blace--; p--; } if(p == l-1) { pre_factor(l, r); term[P(l, r)] = {p, factor[P(l, r)].cand}; } else { Bitset b(m+1); pre_term(l, p); pre_factor(p+1, r); auto& bi = term[P(l, p)].cand; auto& bj = factor[P(p+1, r)].cand; REP(i, m+1) { if(!bi[i]) continue; REP(j, m+1) { if(!bj[j]) continue; if(i*j <= m) b.set(i*j); if(j!=0) b.set(i/j); } } term[P(l, r)] = {p, b}; } } void pre_expression(int l, int r) { int p = r-1; int blace = 0; while(p >= l && expr[p] != '$' || blace != 0) { if(expr[p] == ')') blace++; if(expr[p] == '(') blace--; p--; } if(p == l-1) { pre_term(l, r); expression[P(l, r)] = {p, term[P(l, r)].cand}; } else { Bitset b(m+1); pre_expression(l, p); pre_term(p+1, r); auto& bi = expression[P(l, p)].cand; auto& bj = term[P(p+1, r)].cand; REP(i, m+1) { if(!bi[i]) continue; REP(j, m+1) { if(!bj[j]) continue; if(i+j <= m) b.set(i+j); if(i-j>=0) b.set(i-j); } } expression[P(l, r)] = {p, b}; } } void post_expression(int, int, int); void post_factor(int l, int r, int target) { if(factor[P(l, r)].op_pos == l) post_expression(l+1, r-1, target); } void post_term(int l, int r, int target) { int p = term[P(l, r)].op_pos; if(p == l-1) post_factor(l, r, target); else { auto& bi = term[P(l, p)].cand; auto& bj = factor[P(p+1, r)].cand; REP(i, m+1) { if(!bi[i]) continue; REP(j, m+1) { if(!bj[j]) continue; if(i*j == target) { expr[p] = '*'; post_term(l, p, i); post_factor(p+1, r, j); return; } if(j!=0&&i/j==target) { expr[p] = '/'; post_term(l, p, i); post_factor(p+1, r, j); return; } } } } } void post_expression(int l, int r, int target) { int p = expression[P(l, r)].op_pos; if(p == l-1) post_term(l, r, target); else { auto& bi = expression[P(l, p)].cand; auto& bj = term[P(p+1, r)].cand; REP(i, m+1) { if(!bi[i]) continue; REP(j, m+1) { if(!bj[j]) continue; if(i+j == target) { expr[p] = '+'; post_expression(l, p, i); post_term(p+1, r, j); return; } if(i-j == target) { expr[p] = '-'; post_expression(l, p, i); post_term(p+1, r, j); return; } } } } } void solve(){ cin >> m >> ans >> expr; pre_expression(0, expr.size()); if(!expression[P(0, expr.size())].cand[ans]) print(-1); else { post_expression(0, expr.size(), ans); print(expr); } } // generated by oj-template v4.7.2 (https://github.com/online-judge-tools/template-generator) int main() { // Fasterize input/output script ios::sync_with_stdio(false); cin.tie(nullptr); cout << fixed << setprecision(100); // scanf/printf user should delete this fasterize input/output script int t = 1; //cin >> t; // comment out if solving multi testcase for(int testCase = 1;testCase <= t;++testCase){ solve(); } return 0; }