던전

Albert는 혼자 할 수 있는 던전 게임을 고안했다. 이 게임은 1차원상에서 진행되며, $0$번 방부터 $N$번 방까지 순서대로 "용사"를 움직이며 진행한다. $0$번 방에는 용사가 있으며, 용사의 처음 체력을 $X$라 하자. (이 값은 Albert가 추후에 정하는 값이다.)

$1$번 방부터 $N$번 방까지 각 방에는 몬스터가 하나씩 있고, 몬스터는 마법 주문서를 하나씩 지키고 있다. $i$번째 방의 몬스터와 싸우면 용사의 체력이 $D_i > 0$만큼 깎이고, 체력이 0 이하가 되면 용사는 패배한다. 몬스터를 물리친 뒤에는 그 방의 주문서를 사용해 체력을 올릴 수 있다. 주문서는 덧셈 주문서 또는 곱셈 주문서이며, 양의 정수 $R_i$가 적혀 있다. 문자열 $S$가 입력으로 주어지고, $S_i$가 $i$번째 주문서의 종류를 나타낸다.

• $i$번째 주문서가 덧셈 주문서이면 $S_i$는 '+'이고, 사용하면 용사의 체력이 $R_i$만큼 오른다.
• $i$번째 주문서가 곱셈 주문서이면 $S_i$는 '*'이고, 사용하면 용사의 체력이 $R_i$배가 된다.

Albert의 목표는 처음 체력이 $X$인 용사가 $0$번 방에서 출발해 각 방을 순서대로 지나 $N$번 방의 몬스터까지 모두 물리치는 것이다. $i$번째 방에서 몬스터를 물리치고 얻은 주문서는 반드시 즉시 사용해야 한다.

예를 들어 $N = 4$, $D = [5, 10, 15, 20]$, $S =$ '+*++', $R = [2, 3, 4, 5]$인 경우를 보자.

• 처음 체력이 $X = 10$이면 1번 방에서 체력이 5가 되고, +2 주문서로 7이 된다. 2번 방에서 체력이 $-3$이 되어 용사가 패배한다.
• 처음 체력이 $X = 22$이면 1번 방에서 17이 되고 19가 된다. 2번 방에서 9가 되고, 3배로 올라 27이 된다. 3번 방에서 12가 되고 16이 된다. 4번 방에서 $-4$가 되어 용사가 패배한다.
• 처음 체력이 $X = 30$이면 1번 방에서 25가 되고 27이 된다. 2번 방에서 17이 되고 51이 된다. 3번 방에서 36이 되고 40이 된다. 4번 방에서 20이 되고 25가 된다. 모든 몬스터를 물리친다.

이 예시에서 처음 체력이 24 미만이면 모든 몬스터를 물리칠 수 없고, 24 이상이면 물리칠 수 있다.

첫 줄에 테스트 케이스의 수 $T$가 주어진다.

각 테스트 케이스의 첫 줄에는 $N$이 주어진다. 둘째 줄에는 공백으로 구분된 $N$개의 양의 정수 $D_1, D_2, \dots, D_N$이 주어진다. 셋째 줄에는 공백 없이 길이 $N$인 문자열 $S$가 주어지며, 각 문자는 '+' 또는 '*'이다. 넷째 줄에는 공백으로 구분된 $N$개의 양의 정수 $R_1, R_2, \dots, R_N$이 주어진다.

각 테스트 케이스의 정답을 한 줄에 하나씩 출력한다.

• $1 \le T \le 10$
• $1 \le N \le 10^5$
• $1 \le i \le N$인 모든 $i$에 대하여:
  • $1 \le R_i, D_i \le 10^8$
  • $S_i$는 '+' 또는 '*'이다.
• 각 테스트 케이스의 정답은 $2^{63}-1$ 이하이다.