// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>
using namespace std;
#define nl '\n'
#define pb push_back
#define sz(x) int(x.size())
template<class T> using V = vector<T>;
using vi = V<int>;
void solve() {
int N; cin >> N;
string S; cin >> S;
vi L(N), R(N), ans(N);
V<array<int, 2>> A; set<array<int, 2>> F; vi rem; set<int> pos;
for(int i = 0; i < N; i++) {
cin >> L[i] >> R[i]; --L[i], --R[i];
if (S[L[i]] == '(' && S[R[i]] == '(') {
rem.pb(L[i]); ans[i] = 0;
}
if (S[L[i]] == ')' && S[R[i]] == ')') {
pos.insert(R[i]); ans[i] = 1;
}
if (S[L[i]] == '(' && S[R[i]] == ')') {
pos.insert(R[i]);
A.pb({L[i], i});
ans[i] = 1;
}
if (S[L[i]] == ')' && S[R[i]] == '(') {
pos.insert(L[i]);
A.pb({L[i], i});
ans[i] = 0;
}
}
auto pair = [&](int x) {
auto it = pos.lower_bound(x);
if (it == end(pos)) return 0;
pos.erase(it); return 1;
};
for(auto& x : rem) {
if (!pair(x)) {
cout << -1 << nl;
return;
}
}
sort(begin(A), end(A));
int p = -1;
while(sz(pos)) {
int lim = *begin(pos);
while(p + 1 < sz(A) && A[p + 1][0] <= lim) {
++p; int x = A[p][1];
F.insert({R[x], x});
}
bool ok = 1;
if (!sz(F)) ok = 0;
else {
int x = (*begin(F))[1]; F.erase(begin(F));
ans[x] ^= 1;
if (!pair(L[x])) ok = 0;
if (!pair(R[x])) ok = 0;
}
if (!ok) {
cout << -1 << nl;
return;
}
}
// cout << 1 << nl;
for(auto& x : ans) cout << x << " ";
cout << nl;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
int T; cin >> T; while(T--) {
solve();
}
exit(0-0);
}
