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
122
123
124
#include <cstdio>
#include <algorithm>
#include <vector>
#include <set>
#define PII pair<int, int>
#define FT first
#define SD second
#define MP make_pair
using namespace std;
const int N=1000*1000+5;
const long long INF=9223372036854775807;

int n, m, nwd, nww, chlopcy[N], prefiks[2*N], dlugosc;
char automat[N];
long long wyniki[N], wynik;
set < PII > prefiksy;

inline void licz_prefiksy(int x)
{
	int v=(x+n)%m;
	if (automat[x]=='P')
		prefiks[0]=-1;
	else
		prefiks[0]=1;
	prefiksy.insert(MP(prefiks[0], 0));	
	for (int i=1; i<dlugosc; ++i)
	{
		if (automat[v]=='P')
			prefiks[i]=prefiks[i-1]-1;
		else
			prefiks[i]=prefiks[i-1]+1;
		prefiksy.insert(MP(prefiks[i], i));
		v=(v+n)%m;
	}
}

void licz_wynik(int i, int p=0)
{
	int minimum=(*prefiksy.begin()).FT;
	int tmp=chlopcy[i]+minimum;
	if (p>0)
		tmp+=prefiks[p-1];
	if (tmp>0)
	{
		if (prefiks[dlugosc-1]>=0)
		{
			wyniki[i]=INF;
			return;
		}
		long long k=ceil((double)(tmp)/abs(prefiks[(dlugosc-1+p)%dlugosc]));
		wyniki[i]+=k*n*dlugosc;
		chlopcy[i]+=(k*prefiks[(dlugosc-1+p)%dlugosc]);
	}
	for (auto j=prefiksy.begin(); j!=prefiksy.end();)
	{
		if (((*j).FT+prefiks[p-1])==-chlopcy[i])
		{
			wyniki[i]+=(*j).SD*n+i+1;
			break;
		}
		else
		{
			prefiksy.erase(prefiksy.begin());
			j=prefiksy.begin();
		}
	}
}

int main()
{
	scanf("%d", &n);
	for (int i=0; i<n; ++i)
		scanf("%d", &chlopcy[i]);
	scanf("%d\n", &m);
	scanf("%s", automat);
	nwd=__gcd(n, m);
	nww=n*m/nwd;
	dlugosc=m/nwd;
	if (n*m<N)
	{
		for (int i=0; i<n; ++i)
		{
			if (wyniki[i]==0)
			{
				licz_prefiksy(i);
				for (int j=i; j<n; j+=m)
					licz_wynik(j);
				prefiksy.clear();
			}
		}
	}
	else
	{
		for (int i=0; i<n; ++i)
		{
			if (wyniki[i]==0)
			{
				licz_prefiksy(i);
				licz_wynik(i);
				int j=i+m;
				int przes=j/n;
				j%=n;
				while (j!=i)
				{
					licz_wynik(j, przes);
					j+=m;
					przes+=(j/n);
					j%=n;
				}
				prefiksy.clear();
			}
		}
	}
	wynik=INF;
	for (int i=0; i<n;++i)
	{
		wynik=min(wynik, wyniki[i]);
	}
	if (wynik==INF)
		printf("-1\n");
	else
		printf("%lld\n", wynik);
	return 0;
}