2231D

有一个数组 $a$，它的前缀和数组是 $b$，$b$ 数组的前缀最大值为数组 $c$。

用二进制字符串表示数组 $a$ 的哪些值是确定的，0 代表待定 1 代表确定，给定完整的数组 $c$，问是否存在可能的 $a$ 数组？

首先能想到，$c$ 数组一定是单调不降的，而一旦变化只能是增加。令值发生变化的下标为 $i$，则 $b_i=c_i$。

其次 $b_{i}-b_{i-1}=a_{i}$，所以对于确定的 $a_i$，对应的 $b_i$ 的差值是确定的。所以 $b_i$ 什么时候可以自由选择呢？当 $a_i$ 为不确定的时候。

我们可以按照这样的特征将序列划分为若干个段，由 0 开头，后面跟着若干个 1（可以没有 1）。

对于每个 $[L, R]$ 段，只有 $b_L$ 是可选的，一旦 $b_L$ 确定，则后面所有的 $b$ 也确定了，所以我们可以给出 $b_{k}=b_{L}+\sum_{i=L + 1}^{k}a_{i}$，令 $\Delta_{k} = \sum_{i=L + 1}^{k}a_{i}$，特别地，$\Delta_{L}=0$，满足：

所以 $b_{L}\leq \min_{k=L}^{R}(c_{k}-\Delta_{k})$，我们令 $M=\min_{k=L}^{R}(c_{k}-\Delta_{k})$。

如果 $[L, R]$ 区间内没有出现任何 $c_i$ 出现变化的节点，那么我们就可以令 $b_L=M$。

如果出现了若干个 $c_k$ 变化的点，那么此时 $b_{k}=b_{L}+\Delta_{k}=c_{k}$，此时就会算出一个固定的 $b_L$，如果有几个不同固定的 $b_L$，则无解。若最后这个固定的 $b_L>M$，也无解。

注意第一个位置属于 $c$ 变化的点，所以 $b$ 会由 $c$ 决定一次，还会由 $a$ 决定一次，如果这两个值冲突，也无解。

注意要开 long long。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

void solve() {
  int n;
  string s;
  cin >> n;
  cin >> s;
  s = ' ' + s;
  vector<ll> a(n + 2, 0);
  vector<ll> b(n + 1, 0), c(n + 1);
  bool ok = true;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  for (int i = 1; i <= n; i++) {
    cin >> c[i];
  }
  int i = 1;
  while (i <= n) {
    if (i == 1 || s[i] == '0') {
      ll delta = 0;
      ll M = 4e18;
      int idx = i;
      ll L = 0;
      bool fixed = false;
      if (i == 1 && s[i] == '1') L = a[i], fixed = true;
      while ((s[i] != '0' || idx == i) && i <= n) {
        M = min(M, c[i] - delta);
        if (c[i] > c[i - 1] || i == 1) {
          if (!fixed || L == c[i] - delta) {
            L = c[i] - delta;
            fixed = true;
          } else {
            ok = false;
            break;
          }
        }
        if (c[i] < c[i - 1] && i != 1) {
          ok = false;
          break;
        }
        i++;
        delta += a[i];
      }
      if (fixed && L > M) {
        ok = false;
      }
      if (!ok) break;
      b[idx] = (fixed ? L : M);
    } else {
      i++;
    }
  }
  if (!ok) {
    cout << "No" << '\n';
  } else {
    cout << "Yes" << '\n';
    ll sum = 0;
    for (int i = 1; i <= n; i++) {
      if (s[i] == '0') {
        a[i] = b[i] - sum;
        sum += a[i];
      } else {
        sum += a[i];
      }
      cout << a[i] << ' ';
    }
    cout << '\n';
  }
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int T;
  cin >> T;
  while (T--) solve();
  return 0;
}