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
#include <iostream>
#include <cstdio>
#include <ctime>
#include <cassert>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;

const int N = 1000007;
int n, m, nn;
char s[N];
int a[N];
int odw[N];
vector <int> t[2 * N + 20];
int gdd[2 * N + 20];
int war[N];
long long inf = 2e18;

int main() {
	ios_base::sync_with_stdio(0);
	cin >> n;
	for(int i = 0; i < n; ++i) cin >> a[i];
	cin >> m;
	cin >> s;

	nn = n % m;
	long long wynik = inf;

	for(int ip = 0; ip < m; ++ip) {
		if(!odw[ip]) {
			int x = ip;
			int sum = 0;
			int maxi = 0;
			int czmax = 0;
			int czmin = 0;
			int it = 1;
			while(!odw[x]) {
				if(s[x] == 'W') sum--;
				else sum++;
				war[it] = sum;
				maxi = max(maxi, sum);
				czmax = max(czmax, sum);
				czmin = min(czmin, sum);
				t[sum + N].push_back(it);
				odw[x] = 1;
				it++;
				x += nn;
				if(x >= m) x -= m;
			}
			int ssum = sum;
			int len = it - 1;
			while(odw[x] != 2) {
				odw[x] = 2;
				if(s[x] == 'W') sum--;
				else sum++;
				maxi = max(maxi, sum);
				czmax = max(czmax, sum);
				czmin = min(czmin, sum);
				t[sum + N].push_back(it);
				it++;
				x += nn;
				if(x >= m) x -= m;
			}
			sum = ssum;
			it = 1;
			x = ip;
			do {
				for(int y = x; y < n; y += m) {
					int A = a[y] + war[it - 1];
					if(maxi >= A) {
						while(gdd[A + N] < t[A + N].size() && t[A + N][gdd[A + N]] < it) {
							gdd[A + N]++;
						}
						if(gdd[A + N] < t[A + N].size()) {
							long long pom = t[A + N][gdd[A + N]] - it;
							pom *= n;
							pom += y + 1;
							wynik = min(wynik, pom);
						}
					}
					else if(sum > 0) {
						int ile = A - maxi + sum - 1;
						ile /= sum;
						long long pom = ile;
						pom *= len;
						A -= sum * ile;
						assert(A >= 0);
						assert(A <= maxi);
						while(gdd[A + N] < t[A + N].size() && t[A + N][gdd[A + N]] < it) {
							gdd[A + N]++;
						}
						if(gdd[A + N] < t[A + N].size()) { 
							pom += t[A + N][gdd[A + N]] - it;
							pom *= n;
							pom += y + 1;
							wynik = min(wynik, pom);
						}
					}
				}
				it++;
				x += nn;
				if(x >= m) x -= m;
			} while(x != ip);
		
			for(int j = czmin; j <= czmax; ++j) {
				t[j + N].clear();
				gdd[j + N] = 0;
			}
			
		}
	}

	if(wynik == inf) wynik = -1;
	cout << wynik << endl;
	return 0;
}