1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for (int i = (a); i <= (b); ++i)
#define REPD(i,a,b) for (int i = (a); i >= (b); --i)
#define FORI(i,n) REP(i,1,n)
#define FOR(i,n) REP(i,0,int(n)-1)
#define mp make_pair
#define pb push_back
#define sz(x) int((x).size())
#define dbg(v) cerr << #v << " = " << (v) << endl;
#define FOREACH(i,t) for (__typeof(t.begin()) i = t.begin(); i != t.end(); ++i)
#define fi first
#define se second
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef unsigned long long ll;
const ll INF = 10000000000000000000LL;
const int MAXN = 1000100;
int n,m;
int a[MAXN];
char b[MAXN];

ll gcd(ll x, ll y) {
    ll z;
    while (y!=0) {
        z = x%y;
        x = y;
        y = z;
    }
    return x;
}

ll lcm(ll x, ll y) {
    return x/gcd(x,y) * y;
}

vector<int> cycles[MAXN];
int cycleBalance[MAXN];
int pfxMin[MAXN];
int offsets[MAXN];
vector<int> pfxSum[MAXN];
vector<vector<int> > prefInd[MAXN];
int cyclesNum;
int cycleLen;

int main() {
    scanf("%d", &n);
    FOR(i,n) {
        scanf("%d", &a[i]);
    }
    scanf("%d", &m);
    scanf("%s", &b);

    cyclesNum = gcd(n,m);
    cycleLen = m/gcd(n,m);
    //compute cycles
    FOR(i, cyclesNum) {
        pfxSum[i].pb(0);
        FOR(j, cycleLen) {
            char ch=b[((unsigned long long)n*j+i)%m];
            if (ch == 'W')
                cycles[i].pb(1);
            else
                cycles[i].pb(-1);
            if (j==0)
                pfxSum[i].pb(cycles[i][j]);
            else
                pfxSum[i].pb(pfxSum[i][pfxSum[i].size()-1]+cycles[i][j]);
            if (pfxSum[i][j+1] < pfxMin[i])
                pfxMin[i] = pfxSum[i][j+1];
            offsets[(n*j+i)%m] = j;
        }
        cycleBalance[i] = pfxSum[i][pfxSum[i].size()-1];
        FOR(j,cycleLen) {
            pfxSum[i].pb(pfxSum[i][j+1]+cycleBalance[i]);
        }
        prefInd[i].resize(cycleLen*4+1);
        FOR(j,pfxSum[i].size()) {
            int val = pfxSum[i][j];
            val += 2*cycleLen;
            prefInd[i][val].pb(j);
        }
    }
    ll best = INF;
    FOR(i,n) {
        int cycle = i%cyclesNum;
        int offset = offsets[i%m];
        int findVal = pfxSum[cycle][offset]-a[i];
        bool repeat = false;
        vector<int>::iterator it;
        if (findVal+2*cycleLen <0 || findVal+2*cycleLen>4*cycleLen)
            repeat = true;
        else
            it = lower_bound(prefInd[cycle][findVal+2*cycleLen].begin(), prefInd[cycle][findVal+2*cycleLen].end(), offset);
        if (repeat || it == prefInd[cycle][findVal+2*cycleLen].end()) {
            int newa = a[i] - pfxSum[cycle][offset] + cycleBalance[cycle];
            if (cycleBalance[cycle] >= 0)
                continue;
            ll res = (i+1) + (unsigned long long)n*(unsigned long long)(cycleLen-offset);
            ll ile_miesci = ((newa+pfxMin[cycle])/(-1 * cycleBalance[cycle]));
            res += ile_miesci * (n) * (cycleLen);
            int findVal2 = (-1)*(newa-ile_miesci*(-1*cycleBalance[cycle]));
            res += prefInd[cycle][findVal2+2*cycleLen][0]*(unsigned long long)n;

            if (res < best){
                best = res;
            }
        } else {
            ll res = (i+1) + (unsigned long long)(*it-offset-1)*(unsigned long long)n;

            if (res < best){
                best = res;
            }
        }
    }
    if (best == INF)
        printf("-1\n");
    else
        printf("%lld\n", best);
    return 0;
}