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<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<cassert>
#include<iostream>
#include<algorithm>
#include<queue>
#include<stack>
#include<bitset>
#include<set>
#include<map>
#define REP(i,n) for(int i=0;i<(n);i++)
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define FORD(i,a,b) for(int i=(a);i>=(b);i--)
#define foreach(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();i++)
#define all(c) (c).begin(),(c).end()
#define scanf(...) scanf(__VA_ARGS__)?:0
#define eprintf(...) fprintf(stderr,__VA_ARGS__),fflush(stderr)
#define e1 first
#define e2 second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define inf 1000000009
#define infLL 1000000000000000023ll
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ll,int> pli;
typedef pair<int,ll> pil;
inline int ceil2(int a){return 1<<((sizeof(int)<<3)-__builtin_clz(a));}
int n,m,c,dc,skok,size,a[1000001],sc[1000001];
ll wynik=infLL;
pii knc[1000001],kmc[1000001]; // first - ktory cykl | second - miejsce na cyklu
char s[1000001];
void add(int *tree,int a,int x)
{
	a+=size>>1;
	while (a) tree[a]=min(tree[a],x),a>>=1;
}
int min(int *tree,int a,int b,int nr=1,int z1=0,int z2=(size>>1)-1)
{
	if (a==z1 && b==z2) return tree[nr];
	int sr=(z1+z2)>>1,ret=inf;
	if (a<=sr) ret=min(ret,min(tree,a,min(b,sr),nr<<1,z1,sr));
	if (b>sr) ret=min(ret,min(tree,max(a,sr+1),b,(nr<<1)+1,sr+1,z2));
	return ret;
}
int wh(int *tree,int a,int b,int val,int nr=1,int z1=0,int z2=(size>>1)-1)
{
	if (z1==z2)
	{
		if (tree[nr]<=val) return a;
		return -1;
	}
	int sr=(z1+z2)>>1;
	if (b<=sr) return wh(tree,a,b,val,nr<<1,z1,sr);
	if (a>sr) return wh(tree,a,b,val,(nr<<1)+1,sr+1,z2);
	int lewo=min(tree,a,sr,nr<<1,z1,sr);
	if (lewo<=val) return wh(tree,a,sr,val,nr<<1,z1,sr);
	return wh(tree,sr+1,b,val,(nr<<1)+1,sr+1,z2);
}
void _start(int a,int x)
{
	kmc[a].e2=x;
	int nast=(a+n)%m;
	if (nast>=c) _start(nast,x+1);
}
int main()
{
	scanf("%d",&n);
	REP(i,n) scanf("%d",&a[i]);
	scanf("%d\n",&m);
	gets(s);
	REP(i,m) s[i]=s[i]=='W'?1:-1;
	c=__gcd(n,m); dc=m/c; skok=n%m;
	REP(i,m) kmc[i].e1=i%c;
	REP(i,c) _start(i,0);
	REP(i,n) knc[i]=kmc[i%m];
	size=ceil2(dc-1)<<1;
	int x[c][dc],spc[c][dc],tree[c][size];
	pii pref[c][dc],suf[c][dc];
	REP(i,m) x[kmc[i].e1][kmc[i].e2]=i;
	REP(i,c) REP(j,size) tree[i][j]=inf;
	REP(i,c) REP(j,dc) sc[i]+=s[x[i][j]],spc[i][j]=(j?spc[i][j-1]:0)+s[x[i][j]],add(tree[i],j,spc[i][j]);
	REP(i,c) REP(j,dc)
		if (!j || spc[i][j]<pref[i][j-1].e1) pref[i][j]=mp(spc[i][j],j);
		else pref[i][j]=pref[i][j-1];
	REP(i,c) FORD(j,dc-1,0)
		if (j==dc-1 || spc[i][j]<=suf[i][j+1].e1) suf[i][j]=mp(spc[i][j],j);
		else suf[i][j]=suf[i][j+1];
	REP(i,n)
	{
		int cykl=knc[i].e1,gdzie=knc[i].e2;
		pii minpcykl=mp(suf[cykl][gdzie].e1-(gdzie?spc[cykl][gdzie-1]:0),suf[cykl][gdzie].e2);
		pii minlcykl=gdzie?mp(sc[cykl]-(gdzie?spc[cykl][gdzie-1]:0)+pref[cykl][gdzie-1].e1,pref[cykl][gdzie-1].e2):mp(inf,inf);
		pii mincykl=minpcykl.e1==minlcykl.e1?minpcykl:min(minpcykl,minlcykl);
		if (a[i]+mincykl.e1>0 && sc[cykl]>=0) continue;
		int przejscia=sc[cykl]<0?(a[i]+mincykl.e1-1)/-sc[cykl]+1:0;
		if (przejscia<0 || a[i]+mincykl.e1<=0) przejscia=0;
		a[i]+=przejscia*sc[cykl];
		if (minpcykl.e1<=-a[i])
		{
			int ktory=wh(tree[cykl],gdzie,dc-1,-a[i]+(gdzie?spc[cykl][gdzie-1]:0));
			wynik=min(wynik,(ll)n*((ll)przejscia*dc+ktory-gdzie)+i);
		}
		else
		{
			int ktory=wh(tree[cykl],0,gdzie-1,-a[i]-sc[cykl]+spc[cykl][gdzie-1]);
			wynik=min(wynik,(ll)n*((ll)przejscia*dc+dc+ktory-gdzie)+i);
		}
	}
	assert(wynik>=0);
	if (wynik==infLL) puts("-1");
	else printf("%lld\n",wynik+1);
}