#include <stdio.h>
#include <string.h>
#define N 100000
int hh[N * 2], rr[N * 2], iq[1 + N], pq[N * 2], cnt;
int lt(int i, int j) { return rr[i] < rr[j]; }
int p2(int p) {
return (p *= 2) > cnt ? 0 : (p < cnt && lt(iq[p + 1], iq[p]) ? p + 1 : p);
}
void pq_up(int i) {
int p, q, j;
for (p = pq[i]; (q = p / 2) && lt(i, j = iq[q]); p = q)
iq[pq[j] = p] = j;
iq[pq[i] = p] = i;
}
void pq_dn(int i) {
int p, q, j;
for (p = pq[i]; (q = p2(p)) && lt(j = iq[q], i); p = q)
iq[pq[j] = p] = j;
iq[pq[i] = p] = i;
}
void pq_add(int i) {
pq[i] = ++cnt, pq_up(i);
}
int pq_remove_first() {
int i = iq[1], j = iq[cnt--];
if (j != i)
pq[j] = 1, pq_dn(j);
pq[i] = 0;
return i;
}
int main() {
int t;
scanf("%d", &t);
while (t--) {
static char cc[N * 2 + 1], tt[N];
static int dd[N * 2];
int n, h, i, l, r, d;
scanf("%d%s", &n, cc);
memset(dd, 0, n * 2 * sizeof *dd);
memset(hh, -1, n * 2 * sizeof *hh), memset(rr, -1, n * 2 * sizeof *rr);
for (h = 0; h < n; h++) {
int l, r;
scanf("%d%d", &l, &r), l--, r--;
if (cc[l] == '(' && cc[r] == '(')
tt[h] = 0, dd[l]++;
else if (cc[l] == ')' && cc[r] == ')')
tt[h] = 1, dd[r]--;
else {
hh[l] = h, rr[l] = r;
if (cc[l] == '(')
tt[h] = 1, dd[r]--;
else
tt[h] = 0, dd[l]--;
}
}
memset(pq, 0, n * 2 * sizeof *pq), cnt = 0;
for (i = 0, d = 0; i < n * 2; i++) {
if (rr[i] != -1)
pq_add(i);
d += dd[i];
if (d < 0) {
if (cnt == 0) {
d = -1;
break;
}
l = pq_remove_first(), h = hh[l], r = rr[l];
tt[h] ^= 1;
if (r <= i)
d += 2;
else
d++, dd[r]++;
}
}
if (d != 0)
printf("-1\n");
else {
for (h = 0; h < n; h++)
printf("%d ", tt[h]);
printf("\n");
}
}
return 0;
}
