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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=(1<<21);
const ll INF=4e18;
/*struct Tree
{
    int mn[2*N];
    void update(int x, int a)
    {
        x+=N;
        mn[x]=a;
        while(x>0)
        {
            x/=2;
            mn[x]=min(mn[2*x], mn[2*x+1]);
        }
    }
    int query(int xa, int xb)
    {
        xa+=N; xb+=N;
        if(xa==xb) return mn[xa];
        int res=min(mn[xa], mn[xb]);
        while(xa/2!=xb/2)
        {
            if(xa%2==0) res=min(res, mn[xa+1]);
            if(xb%2==1) res=min(res, mn[xb-1]);
            xa/=2; xb/=2;
        }
        //printf("?\n");
        return res;
    }
};
Tree t;*/
int a[N], d[N], num[N];
char c[N];
vector<int> v[N];
ll result(int n, int m)
{
    for(int i=0; i<m; ++i)
    {
        d[i]=c[i*(ll)n%m];
        if(d[i]=='W') d[i]=1; else d[i]=-1;
        num[i*(ll)n%m]=i;
    }
    for(int i=1; i<m; ++i) d[i]+=d[i-1];
    for(int i=m; i<2*m; ++i) d[i]=d[i-m]+d[m-1];
    for(int i=2*m; i>0; --i) d[i]=d[i-1];
    d[0]=0;
    for(int i=0; i<2*m; ++i) if(abs(d[i])<=m) v[d[i]+m].push_back(i);
    //for(int i=0; i<2*m; ++i) t.update(i, d[i]);
    int mn=0;
    for(int i=1; i<=m; ++i) mn=min(d[i], mn);
    ll res=INF;
    for(int i=0; i<n; ++i)
    {
        //printf("i=%d\n", i);
        ll lres=0;
        //Check if bankrupt in a short time
        if(d[num[i%m]]-a[i]+m>=0&&v[d[num[i%m]]-a[i]+m].size()>0&&v[d[num[i%m]]-a[i]+m].back()>num[i%m])
        {
            lres=*lower_bound(v[d[num[i%m]]-a[i]+m].begin(), v[d[num[i%m]]-a[i]+m].end(), num[i%m])-num[i%m];
        }
        else
        {
            //printf("Here!\n");
            lres=m-num[i%m];
            //if(i==2) printf("i=%d, a[i]=%d, n=%d, m=%d, lres=%lld\n", i, a[i], n, m, lres);
            a[i]+=d[m]-d[num[i%m]];
            if(d[m]>=0) lres=INF;
            else
            {
                if(a[i]<=-mn)
                {
                    lres+=v[m-a[i]][0];
                }
                else
                {
                    lres+=m*(ll)((a[i]+mn)/(-d[m]));
                    a[i]=(a[i]+mn-d[m]*(ll)m)%(-d[m])-mn;
                    if(a[i]>-mn)
                    {
                        a[i]-=-d[m];
                        lres+=m;
                    }
                    lres+=v[m-a[i]][0];
                }
            }
        }
        if(lres!=INF) lres=max(lres-1, 0LL)*n+i+1;
        //if(lres==2) printf("i=%d, a[i]=%d, n=%d, m=%d\n", i, a[i], n, m);
        res=min(res, lres);
    }
    for(int i=0; i<n; ++i) a[i]=0;
    for(int i=0; i<=m; ++i) d[i]=num[i]=c[i]=0;
    for(int i=0; i<=2*m; ++i) v[i].clear();
    return res;
}
int ga[N];
char gc[N];
int main()
{
    //freopen("tests/big0.in", "r", stdin);
    int n, m;
    scanf("%d", &n);
    for(int i=0; i<n; ++i) scanf("%d", &ga[i]);
    scanf("%d\n%s", &m, gc);
    int gcd=__gcd(n, m);
    ll res=INF;
    for(int k=0; k<gcd; ++k)
    {
        for(int i=0; i<n/gcd; ++i) a[i]=ga[k+gcd*i];
        for(int i=0; i<m/gcd; ++i) c[i]=gc[k+gcd*i];
        ll tmp=result(n/gcd, m/gcd);
        if(tmp!=INF) res=min(res, gcd*(tmp-1)+k+1);
    }
    if(res<INF) printf("%lld\n", res);
    else printf("-1\n");
    return 0;
}