#include <bits/stdc++.h>

using namespace std;

template<typename T>
struct Fenwick{
    vector<T> tree;

    Fenwick() = default;

    explicit Fenwick(const int n){
        tree.assign(n + 1, T{});
    }

    void update(const int indx, const T val){
        for(int i = indx + 1; i < tree.size(); i += i & -i) tree[i] += val;
    }

    [[nodiscard]] T query(const int indx) const{
        T ans{};
        for(int i = indx + 1; i > 0; i -= i & -i) ans += tree[i];
        return ans;
    }
};

long long get_hash(string str){
    long long hsh = 0;
    for(int i = 0; i < str.size(); i++) hsh = hsh * 26 + (str[i] - 'A');
    return hsh;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;

    cin >> n >> q;

    vector<long long> arr(n, 0ll);
    vector<long long> cmprs;

    for(int i = 0; i < n; i++){
        string str;
        cin >> str;

        arr[i] = get_hash(str);
        cmprs.push_back(arr[i]);
    }

    vector<pair<long long, long long>> queries_input(q);

    for(int i = 0; i < q; i++){
        string a, b;
        cin >> a >> b;

        queries_input[i] = {get_hash(a), get_hash(b)};
        cmprs.push_back(queries_input[i].first);
        cmprs.push_back(queries_input[i].second);
    }

    sort(cmprs.begin(), cmprs.end());
    cmprs.erase(unique(cmprs.begin(), cmprs.end()), cmprs.end());

    for(int i = 0; i < n; i++) arr[i] = lower_bound(cmprs.begin(), cmprs.end(), arr[i]) - cmprs.begin();
    for(int i = 0; i < q; i++){
        queries_input[i].first = lower_bound(cmprs.begin(), cmprs.end(), queries_input[i].first) - cmprs.begin();
        queries_input[i].second = lower_bound(cmprs.begin(), cmprs.end(), queries_input[i].second) - cmprs.begin();
    }

    int max_num = cmprs.size() + 5;

    vector<vector<pair<int, int>>> queries(max_num);

    for(int i = 0; i < q; i++){
        queries[queries_input[i].second].push_back({queries_input[i].first, i});
    }

    stack<int> min_stk, max_stk;
    vector<int> min_prev(n, -1), max_prev(n, -1);

    for(int i = 0; i < n; i++){
        while(!min_stk.empty() && arr[min_stk.top()] >= arr[i]) min_stk.pop();
        if(!min_stk.empty()) min_prev[i] = min_stk.top();
        min_stk.push(i);

        while(!max_stk.empty() && arr[max_stk.top()] <= arr[i]) max_stk.pop();
        if(!max_stk.empty()) max_prev[i] = max_stk.top();
        max_stk.push(i);
    }

    vector<vector<pair<int, int>>> segments(max_num);

    for(int i = 0; i < n; i++){
        int min_cur = i, max_cur = i, cur = i;

        while(cur != -1){
            int min_next = min_prev[min_cur], max_next = max_prev[max_cur];

            if(min_next >= max_next){
                segments[arr[max_cur]].push_back({arr[min_cur], cur - min_next});
                cur = min_cur = min_next;
            }
            else{
                segments[arr[max_cur]].push_back({arr[min_cur], cur - max_next});
                cur = max_cur = max_next;
            }
        }
    }

    Fenwick<long long> fw(max_num);
    vector<long long> ans(q, 0);

    long long total = 0;

    for(int mx = 0; mx < max_num; mx++){
        for(auto p : segments[mx]){
            int mn = p.first, cnt = p.second;
            total += cnt;
            fw.update(mn, cnt);
        }

        for(auto p : queries[mx]){
            int mn = p.first, i = p.second;
            ans[i] = total - fw.query(mn - 1);
        }
    }

    for(int i = 0; i < q; i++) cout << ans[i] << '\n';
}