P5581 [PA 2015] Hazard

~~Gambling is harmful to your health. Please do not imitate it.~~

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.

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$.

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

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