Description

There are $n$ people taking turns playing a slot machine game. Initially, person $i$ has $a_i$ dollars.

The slot machine can be modeled as a sequence of length $m$ containing only $1$ and $-1$. If you draw $1$, you win $1$ dollar; if you draw $-1$, you lose $1$ dollar.

In round $1$, person $1$ draws the $1$-st element of the sequence. In round $2$, person $2$ draws the $2$-nd element. In round $3$, person $3$ draws the $3$-rd element, and so on. That is, after person $i$ finishes drawing, it is person $i+1$'s turn to draw. In particular, after person $n$ finishes drawing, it becomes person $1$'s turn.

After the $i$-th element of the sequence is drawn, the next element drawn will be the $(i+1)$-th element. In particular, after the $m$-th element is drawn, the next element drawn will be the $1$-st element.

If in some round a person loses all of their money, the gambling game ends. Find in which round the game ends, or determine that the game will continue forever.

Input Format

The first line contains a positive integer $n$, the number of players.

The second line contains $n$ positive integers $a_1,a_2,\ldots,a_n$, where $a_i$ is the initial amount of money held by player $i$.

The third line contains a positive integer $m$, the length of the sequence.

The fourth line contains a string of length $m$ consisting only of W and P, representing the sequence, where W means $1$ and P means $-1$.

Output Format

If the game will continue forever, output -1. Otherwise, output the round in which the game ends.

4
2 3 2 1
3
WPP

12

Hint

For $100\%$ of the testdata, $1 \le n \le 10^6$, $1 \le a_i \le 10^6$, $1 \le m \le 10^6$.

Translated by ChatGPT 5