#ifdef LOCAL #define _GLIBCXX_DEBUG #endif #include #include using namespace atcoder; using namespace std; using ll = long long; #define rep(i, n) for (ll i = 0; i < (ll)n; i++) #define all(v) v.begin(),v.end() const ll INF = (ll)2e18; #include using namespace std; /* Wavelet Matrix 非負の要素の配列に対して、 区間内である値未満/以上の値とか個数を求められる 参考 ウェーブレットツリーに関するものだが、基本的な考え方がわかる https://www.slideshare.net/slideshow/ss-15916040/15916040 このライブラリはdrkenさんのライブラリに様々な機能を自分で追加したものである https://github.com/drken1215/algorithm/blob/master/DataStructureSegment/wavelet_matrix.cpp WaveletMatrix wm(vec); //宣言 全てlog(max(vec))で処理できる wm.rank(l,r,num); [l,r)でnumである要素数 wm.range_freq(l,r,upper); [l,r)でupper未満である要素数 wm.range_freq(l,r,lower,upper); [l,r)で[lower,upper)である要素数 wm.k_th_smallest(l,r,k); 0-indexedでk番目に小さい[l,r)にある値 wm.k_th_largest(l,r,k) wm.k_smallest_sum(l,r,k); [l,r)で小さい方からk個の和 wm.k_largest_sum(l,r,k); [l,r)で大きい方からk個の和 wm.prev_value(l,r,val); [l,r)でval未満で最大の値 wm.next_value(l,r,val); [l,r)でval以上で最小の値 */ // Bit Vector (for 64-bit non-negative integer) struct BitVector { // block: bit vector // count: the number of 1 within each block unsigned int n, zeros; vector block; vector count; // constructor BitVector() {} BitVector(const unsigned int num) { resize(num); } void resize(const unsigned int num) { n = num; block.assign(((num + 1) >> 6) + 1, 0); count.assign(block.size(), 0); } // set val(0 or 1) onto i-th bit, get i-th bit of val(0 or 1) void set(const unsigned int i, const unsigned long long val = 1LL) { assert((i >> 6) < block.size()); block[i >> 6] |= (val << (i & 63)); } unsigned int get(const unsigned int i) const { assert((i >> 6) < block.size()); return (const unsigned int)(block[i >> 6] >> (i & 63)) & 1; } void build() { for (unsigned int i = 1; i < block.size(); i++) { count[i] = count[i - 1] + __builtin_popcountll(block[i - 1]); } zeros = rank0(n); } // the number of 1 in [0, i) unsigned int rank1(const unsigned int i) const { assert((i >> 6) < count.size()); assert((i >> 6) < block.size()); return count[i >> 6] + __builtin_popcountll(block[i >> 6] & ((1ULL << (i & 63)) - 1ULL)); } // the number of 1 in [i, j) unsigned int rank1(const unsigned int i, const unsigned int j) const { return rank1(j) - rank1(i); } // the number of 0 in [0, i) unsigned int rank0(const unsigned int i) const { return i - rank1(i); } // the number of 0 in [i, j) unsigned int rank0(const unsigned int i, const unsigned int j) const { return rank0(j) - rank0(i); } // the number of 0 in [0, n) unsigned int rank0() const { return zeros; } }; // Wavelet Matrix (must vec[i] >= 0) template struct WaveletMatrix { // inner data unsigned int n, height; vector v; vector bv; vector> sum; // constructor (sigma: the number of characters) WaveletMatrix() : n(0) {} WaveletMatrix(unsigned int n) : n(n), v(n) {} WaveletMatrix(const vector &vec) : n(vec.size()), v(vec) { build(); } void add(const T &val) { assert(val >= 0); v.push_back(val); n = v.size(); } void set(unsigned int i, const T &val) { assert(i >= 0 && i < n && val >= 0); v[i] = val; } void build() { assert(n == (int)v.size()); T mv = 1; for (int i = 0; i < n; ++i) mv = max(mv, v[i]); for (height = 1; mv != 0; mv >>= 1) ++height; vector left(n), right(n), ord(n); iota(ord.begin(), ord.end(), 0); bv.assign(height, BitVector(n)); sum.assign(height + 1, vector(n + 1, 0)); for (int h = height - 1; h >= 0; --h) { int l = 0, r = 0; for (int i = 0; i < n; ++i) { if ((v[ord[i]] >> h) & 1) { bv[h].set(i); right[r++] = ord[i]; } else { left[l++] = ord[i]; } } bv[h].build(); ord.swap(left); for (int i = 0; i < r; ++i) ord[i + l] = right[i]; for (int i = 0; i < n; ++i) sum[h][i + 1] = sum[h][i] + v[ord[i]]; } } // access v[k] T access(int i) { T res = 0; for (int h = height - 1; h >= 0; --h) { int i0 = bv[h].rank0(i); if (bv[h].get(i)) { i += bv[h].rank0() - i0; res |= T(1) << h; } else { i = i0; } } return res; } T operator [] (int i) { return access(i); } // count "i" s.t. v[i] = val, i in [l, r) int rank(int l, int r, const T &val) { assert(0 <= l && l <= r && r <= n); for (int h = height - 1; h >= 0; --h) { int l0 = bv[h].rank0(l), r0 = bv[h].rank0(r); if ((val >> h) & 1) { l += bv[h].rank0() - l0; r += bv[h].rank0() - r0; } else { l = l0; r = r0; } } return r - l; } // [l,r)で[lower,upper)である要素数、lowerは省略可 int range_freq(int l, int r, const T &upper) { assert(0 <= l && l <= r && r <= n); int res = 0; for (int h = height - 1; h >= 0; --h) { int l0 = bv[h].rank0(l), r0 = bv[h].rank0(r); if ((upper >> h) & 1) { l += bv[h].rank0() - l0; r += bv[h].rank0() - r0; res += r0 - l0; } else { l = l0; r = r0; } } return res; } // [l,r)で[lower,upper)である数の個数 int range_freq(int l, int r, const T &lower, const T &upper) { return range_freq(l, r, upper) - range_freq(l, r, lower); } // the k-th (0-indexed) smallest value in [l, r) T k_th_smallest(int l, int r, int k) { assert(0 <= l && l <= r && r <= n); T res = 0; for (int h = height - 1; h >= 0; --h) { int l0 = bv[h].rank0(l), r0 = bv[h].rank0(r); if (r0 - l0 <= k) { l += bv[h].rank0() - l0; r += bv[h].rank0() - r0; k -= r0 - l0; res |= T(1) << h; } else { l = l0; r = r0; } } return res; } // the k-th (0-indexed) largest value in [l, r) T k_th_largest(int l, int r, int k) { assert(0 <= l && l <= r && r <= n); return k_th_smallest(l, r, r - l - k - 1); } // [l, r)で小さい方からk個の和  T k_smallest_sum(int l, int r, int k) { assert(0 <= l && l <= r && r <= n); //もしkが区間幅よりも大きければ、区間幅まで小さくする k = min(k, r - l); if (l == r) return 0; T res = 0, val = 0; for (int h = height - 1; h >= 0; --h) { int l0 = bv[h].rank0(l), r0 = bv[h].rank0(r); //0のやつは全て求めるべき値に含まれている時 if (r0 - l0 <= k) { l += bv[h].rank0() - l0; r += bv[h].rank0() - r0; k -= r0 - l0; val |= T(1) << h; //sumは(l,r)の状態から左に0,右に1となるように並べ替えた後の累積和になっている //そのため、↓で現在注目しているbitが0であるものによる和を足している res += sum[h][r0] - sum[h][l0]; } else { l = l0; r = r0; } } //最終的に到達した場所(数)がk個残っている res += val * k; return res; } T k_largest_sum(int l,int r,int k){ k = min(k, r - l); //全体-小さい方から(r-l-k)個の和 return k_smallest_sum(l, r, r - l) - k_smallest_sum(l, r, r - l - k); } //[l,r)で[lower,upper)である要素の和 T range_sum_by_value(int l,int r,T lower,T upper){ int smaller_cnt = range_freq(l, r, lower); int MAX_element = k_th_largest(l, r, 0); int bigger_cnt = range_freq(l, r, upper, MAX_element + 1); // 全体の和-小さい方の和-大きい方の和 return k_largest_sum(l, r, r - l) - k_smallest_sum(l, r, smaller_cnt) - k_largest_sum(l, r, bigger_cnt); } // the max value (< val) in [l, r) T prev_value(int l, int r, T val) { assert(0 <= l && l <= r && r <= n); int num = range_freq(l, r, 0, val); if (num == 0) return T(-1); else return k_th_smallest(l, r, num - 1); } // the min value (>= val) in [l, r) T next_value(int l, int r, T val) { assert(0 <= l && l <= r && r <= n); int num = range_freq(l, r, 0, val); if (num == r - l) return T(-1); else return k_th_smallest(l, r, num); } }; int main(){ cin.tie(0); ios::sync_with_stdio(false); ll N, K; cin >> N >> K; string S; cin >> S; if(N%2==1){ cout << "No" << endl; return 0; } vector memo(N, -1); stack> st; rep(i,N){ if(S[i]=='('){ st.push({i,S[i]}); } else{ if(st.size()==0){ cout << "No" << endl; return 0; } else{ memo[i] = st.top().first; st.pop(); } } } //Sは対応が取れている vector depth(N+1, 0); rep(i,N){ if(S[i]=='('){ depth[i + 1] = depth[i] + 1; } else{ depth[i + 1] = depth[i] - 1; } } rep(i,N){ if(S[i]==')'){ depth[i+1]++; } } // for(auto x:depth){ // cout << x << ' '; // } // cout << endl; WaveletMatrix wm(depth); // cout << wm.range_freq(3, 6, 2, 3) << endl; string ans = ""; ll cnt = 0; rep(i,N){ if(S[i]==')'){ ll d = depth[i + 1]; ll tmp = wm.range_freq(memo[i] + 1, i + 1, d+1, d + 2); tmp /= 2; //cout << tmp << endl; if(tmp==0){ ans += "1+1"; cnt += 2; } else if(tmp==1){ ans += "+1"; cnt += 1; } ans += S[i]; } else{ if(i!=0&&S[i-1]==')'){ ans += "+"; } ans += S[i]; } //cout << ans << endl; } if(cnt==K&&wm.range_freq(1,N+1,1,2)==2){ cout << "No" << endl; return 0; } if(cnt<=K){ cout << "Yes" << endl; rep(i,K-cnt){ ans += "+1"; } cout << ans << endl; } else{ cout << "No" << endl; } }