Problem: Given a string of length n s = s1, s2,…, sn and m queries. Each query qk (1 ≤ k ≤ m) is one of four types, "L ++", "L-", "R ++", "R-", and l [for the kth query qk. k] and r [k] are defined below.

* L ++: l [k] = l [k-1] + 1, r [k] = r [k-1]

* L-: l [k] = l [k-1] -1, r [k] = r [k-1]

* R ++: l [k] = l [k-1], r [k] = r [k-1] +1

* R-: l [k] = l [k-1], r [k] = r [k-1] -1




However, l [0] = r [0] = 1.

At this time, how many kinds of character strings are created for m substrings sl [k], sl [k] + 1,…, sr [k] -1, sr [k] (1 ≤ k ≤ m). Answer if you can.

Constraints

* The string s consists of a lowercase alphabet

* 1 ≤ n ≤ 3 x 105

* 1 ≤ m ≤ 3 × 105

* qk (1 ≤ k ≤ m) is one of "L ++", "L-", "R ++", "R-"

* 1 ≤ l [k] ≤ r [k] ≤ n (1 ≤ k ≤ m)

Input

Input is given in the following format

> n m
> s
> q1
> q2
>…
> qm
>

Output

Output the solution of the problem on one line

Examples

Input

5 4
abcde
R++
R++
L++
L--


Output

3


Input

4 6
abab
R++
L++
R++
L++
R++
L++


Output

4


Input

10 13
aacacbabac
R++
R++
L++
R++
R++
L++
L++
R++
R++
L--
L--
R--
R--


Output

11

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define RFOR(i,a,b) for(int i=(a);i>=(b);--i)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,n,0)
#define ALL(c) (c).begin(),(c).end()
#define PB(a) push_back(a)
#define EMPB(...) emplace_back(__VA_ARGS__)
#define EMP(...) emplace(__VA_ARGS__)
#define MP(a,b) make_pair(a,b)
#define MT(...) make_tuple(__VA_ARGS__)
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
#define MINF(a) memset(a,0x3f,sizeof(a))
#define PW(n) (1LL<<(n))
#define IN(i,a,b) (a <= i && i <= b)
using namespace std;
template <class T> inline bool CHMIN(T& a, T b) { if(a>b) { a=b; return 1; } return 0; }
template <class T> inline bool CHMAX(T& a, T b) { if(a<b) { a=b; return 1; } return 0; }
template <class T> inline void SORT(T& a) { sort(ALL(a)); }
template <class T> inline void REV(T& a) { reverse(ALL(a)); }
template <class T> inline void UNI(T& a) { sort(ALL(a)); a.erase(unique(ALL(a)),a.end()); }
const int MOD = 1000000007;
const int INF = 0x3f3f3f3f3f3f3f3f;
const double EPS = 1e-10;
/* ---------------------------------------------------------------------------------------------------- */

struct RollingHash {
  const int base = 9973;
  const vector<int> mod = {999999937LL, 1000000007LL};
  string S;
  vector<int> hash[2], power[2];

  RollingHash() {}
  RollingHash(const string &cs) { init(cs); }
  void init(const string &cs) {
    S = cs;
    int n = S.size();
    for (int iter = 0; iter < 2; iter++) {
      hash[iter].assign(n+1,0);
      power[iter].assign(n+1,1);
      for (int i = 0; i < n; i++) {
        hash[iter][i+1] = (hash[iter][i]*base + S[i]) % mod[iter];
        power[iter][i+1] = power[iter][i]*base % mod[iter];
      }
    }
  }
  // get hash of S[left:right)
  inline int get(int l, int r, int id) const {
    int res = hash[id][r] - hash[id][l] * power[id][r-l] % mod[id];
    if (res < 0) res += mod[id];
    return res;
  }
};

int n,m;
string s;

signed main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(10);

  cin >> n >> m >> s;
  RollingHash rh(s);
  set<pii> st;
  int l = 0, r = 1;
  REP(i,m) {
    string q;
    cin >> q;
    if (q == "R++") r++;
    else if (q == "R--") r--;
    else if (q == "L++") l++;
    else l--;
    st.insert(pii(rh.get(l,r,0),rh.get(l,r,1)));
  }
  cout << st.size() << endl;

  return 0;
}