#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <unordered_map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <unordered_set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <vector>

template <typename T = int>
struct Graph {
    // 辺の構造体
    struct Edge {
        int from, to;
        T cost;
        int id;

        Edge() : from(-1), to(-1), cost(-1), id(-1) {}
        Edge(int from, int to, T cost = 1, int id = -1) : from(from), to(to), cost(cost), id(id) {}

        bool operator<(const Edge &rhs) const { return cost < rhs.cost; }
        friend std::ostream& operator<<(std::ostream& os, const Edge& e) {
            return os << "(" << e.from << " -> " << e.to << "  weight: " << e.cost << ", id: " << e.id << ")";
        }
    };

    Graph() = default;
    Graph(int N) : N(N), M(0), G(N) {}

private:
    int N, M;
    std::vector<std::vector<Edge>> G;

public:
    bool is_weighted = false;
    void add_edge(const int& u, const int& v, T w = 1) {
        G[u].push_back({u, v, w, M});
        G[v].push_back({v, u, w, M++});
        if (w != 1) {
            is_weighted = true;
        }
    }
    void add_directed_edge(const int& u, const int& v, T w = 1) {
        G[u].push_back({u, v, w, M++});
        if (w != 1) {
            is_weighted = true;
        }
    }
    void read(const int& M, bool weighted = false, bool directed = false, int padding = 1) {
        for (int i = 0; i < M; i++) {
            int u, v; std::cin >> u >> v;
            u -= padding;
            v -= padding;
            T w(1);
            if (weighted) {
                is_weighted = true;
                std::cin >> w;
            }
            if (directed) {
                add_directed_edge(u, v, w);
            } else {
                add_edge(u, v, w);
            }
        }
    }
    int size() const { return N; }
    const std::vector<Edge>& operator[](int v) const { return G[v]; }
    std::vector<Edge>& operator[](int v) { return G[v]; }
    std::vector<Edge> edges() {
        std::vector<Edge> es(M);
        for (int v = 0; v < N; v++) {
            for (const auto& nv : G[v]) {
                es[nv.id] = nv;
            }
        }
        return es;
    }

    // 最短距離 ===========================================
    std::pair<std::vector<T>, std::vector<Edge>> BFS(const int& start) {
        std::vector<T> dist(N, std::numeric_limits<T>::max());
        std::queue<int> q;
        /**
         * @param prev_edges[target] : start から target までの最短経路における、target を訪れる直前に通った辺
         */
        std::vector<Edge> prev_edges(N);
        dist[start] = 0;
        q.push(start);
        while (!q.empty()) {
            int v = q.front(); q.pop();
            for (const auto& e : G[v]) {
                int nv = e.to;
                if(dist[nv] != std::numeric_limits<T>::max()) {
                    continue;
                }
                dist[nv] = dist[v] + 1;
                prev_edges[nv] = e;
                q.push(nv);
            }
        }
        return make_pair(dist, prev_edges);
    }

    std::pair<std::vector<T>, std::vector<Edge>> BFS01(const int& start) {
        std::vector<T> dist(N, std::numeric_limits<T>::max());
        std::deque<int> q;
        /**
         * @param prev_edges[target] : start から target までの最短経路における、targetを訪れる直前に通った辺
         */
        std::vector<Edge> prev_edges(N);
        dist[start] = 0;
        q.push_front(start);
        while (!q.empty()) {
            int v = q.front(); q.pop_front();
            for (const auto& e : G[v]) {
                int nv = e.to;
                if (dist[nv] <= dist[v] + e.cost) {
                    continue;
                }
                dist[nv] = dist[v] + e.cost;
                prev_edges[nv] = e;
                if (e.cost == 0) {
                    q.push_front(nv);
                } else {
                    q.push_back(nv);
                }
            }
        }
        return make_pair(dist, prev_edges);
    }

    std::pair<std::vector<T>, std::vector<Edge>> Dijkstra(int start) {
        std::vector<T> dist(N, std::numeric_limits<T>::max());
        std::priority_queue<std::pair<T, int>, std::vector<std::pair<T, int>>, std::greater<std::pair<T, int>>> q;
        /**
         * @param prev_edges[target] : start から target までの最短経路における、targetを訪れる直前に通った辺
         */
        std::vector<Edge> prev_edges(N);
        dist[start] = 0;
        q.push({dist[start], start});
        while (!q.empty()) {
            auto [dist_v, v] = q.top(); q.pop();
            if (dist_v > dist[v]) {
                continue;
            }
            for (const auto& e : G[v]) {
                int nv = e.to;
                if(dist[nv] <= dist[v] + e.cost) {
                    continue;
                }
                dist[nv] = dist[v] + e.cost;
                prev_edges[nv] = e;
                q.push({dist[nv], nv});
            }
        }
        return make_pair(dist, prev_edges);
    }

    /**
     * @brief 負辺を含むグラフで、単一始点の最短経路を求める
     * @return 負閉路を含む場合かどうかのフラグ、dist 配列
     * @remark 全辺のコストを -1 倍すると、最長経路を求める
     */
    std::pair<std::vector<T>, bool> bellman_ford(int start) {
        const T INF_ = std::numeric_limits<T>::max();
        std::vector<T> dist(N, INF_);
        dist[start] = 0;
        int cnt = 0;
        std::vector<Graph::Edge> es = edges();
        /**
         * 全ての辺を走査して緩和を行う
         * https://qiita.com/muumu/items/bae1575c3161ced28587
         * 各 while ループで、
         * 長さ 1 の最短路が決定 -> 長さ 2 の最短路が決定 -> ...
         * みたいな感じ？
         */
        while (cnt < N) {
            bool end = true;
            for (const auto& e : es) {
                if (dist[e.from] != INF_ and dist[e.from] + e.cost < dist[e.to]) {
                    dist[e.to] = dist[e.from] + e.cost;
                    end = false;
                }
            }
            if (end) {
                break;
            }
            cnt++;
        }
        return make_pair(dist, (cnt == N));
    }

    std::vector<Edge> path(const int& start, const int& target, const std::vector<Edge>& prev_edges) {
        std::vector<Edge> path;
        for (int cur = target; cur != start; cur = prev_edges[cur].from) {
            if (prev_edges[cur].id == -1) {
                return {};
            }
            path.push_back(prev_edges[cur]);
        }
        std::reverse(path.begin(), path.end());
        return path;
    }
};

template <typename T = int>
struct Tree : Graph<T> {
private:
    using Graph<T>::Dijkstra;
    using Graph<T>::BFS;
    using Edge = typename Graph<T>::Edge;
    int root;
    int N;
    std::vector<int> parent, depth, siz;
    std::vector<T> weighted_depth;
    bool done_build;

public:
    Tree(int N, int root = 0) : Graph<T>(N), root(root), N(N), parent(N, -1), depth(N, -1), siz(N, 0), weighted_depth(N, T(0)), done_build(false) {}
    void read(bool weighted = false, bool directed = false, int padding = 1) {
        Graph<T>::read(N - 1, weighted, directed, padding);
        if (!done_build) {
            build();
            done_build = true;
        }
    }
    int get_root() const { return root; }
    int get_parent(int v) const { return parent[v]; }
    int get_depth(int v) const { return depth[v]; }
    int get_size(int v) const { return siz[v]; }
    T get_weighted_depth(int v) const { return weighted_depth[v]; }
    int size() const { return N; }

    void build() {
        if (done_build) {
            return;
        }
        done_build = true;
        auto dfs = [&](auto dfs, int v, int p, int d, T wd) -> void {
            parent[v] = p;
            depth[v] = d;
            weighted_depth[v] = wd;
            int cnt = 0;
            for (const auto& e : (*this)[v]) {
                if (e.to == p) {
                    continue;
                }
                dfs(dfs, e.to, v, d + 1, wd + e.cost);
                cnt += siz[e.to];
            }
            cnt++;
            siz[v] = cnt;
        };
        dfs(dfs, root, -1, 0, T(0));
    }

    // 木の直径 ===========================================
    std::vector<int> get_tree_diameter(int x = 0) {
        std::vector<T> dist;
        std::vector<Edge> prev_edges(N);
        if (this->is_weighted) {
            std::tie(dist, prev_edges) = Dijkstra(x);
        } else {
            std::tie(dist, prev_edges) = BFS(x);
        }
        auto get_farthest_vertex = [this](std::vector<T>& dist) {
            T max_dist = std::numeric_limits<T>::lowest();
            int to = -1;
            for (int v = 0; v < this->N; v++) {
                if (max_dist < dist[v]) {
                    max_dist = dist[v];
                    to = v;
                }
            }
            return to;
        };
        int y = get_farthest_vertex(dist);
        if (this->is_weighted) {
            std::tie(dist, prev_edges) = Dijkstra(y);
        } else {
            std::tie(dist, prev_edges) = BFS(y);
        }
        int z = get_farthest_vertex(dist);
        std::vector<int> path;
        int v = z;
        while (1) {
            path.push_back(v);
            if (v == y) {
                break;
            }
            v = prev_edges[v].from;
        }
        std::reverse(path.begin(), path.end());
        return path;
    }
};

using ll = long long;
using lll = __int128_t;
using ld = long double;
#define newl '\n'
#define REF const auto&
#define INF 1000390039
#define LLINF 1000000039000000039
#define IMAX INT_MAX
#define IMIN INT_MIN
#define LLMAX LONG_LONG_MAX
#define LLMIN LONG_LONG_MIN
#define BIT(i) (1LL << (i))
#define tbit(n, k) ((n >> k) & 1) // nの（上から）kビット目
#define bit(n, k) (n & (1LL << (k))) // nの（下から）kビット目
#define PI acosl(-1)
#define inr(l, x, r) (l <= x && x < r)
#define einr(l, x, r) (l <= x && x <= r)
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define erep(i, a, b) for(int i = (a); i <= (b); i++)
#define rrep(i, a, b) for(int i = (a); i >= (b); i--)
#define repl(i, a, b) for(long long i = (a); i < (b); i++)
#define erepl(i, a, b) for(long long i = (a); i <= (b); i++)
#define rrepl(i, a, b) for(long long i = (a); i >= (b); i--)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define for_subset(sub, bit) for (ll sub = (bit); sub >= 0; sub = (sub == 0 ? -1 : (sub - 1) & (bit)))
#define UNIQUE(v) (std::sort(all(v)), (v).erase(std::unique(all(v)), (v).end()))
#define pcnt(x) __builtin_popcount(x)
#define llpcnt(x) __builtin_popcountll(x)
// 1D
#define VC(name, type, ...) \
    vector<type> name( \
        __VA_ARGS__ \
    )
// 2D
#define VVC(name, type, a, ...) \
    vector<vector<type>> name( \
        (a), vector<type>( \
            __VA_ARGS__ \
        ) \
    )
// 3D
#define VVVC(name, type, a, b, ...) \
    vector<vector<vector<type>>> name( \
        (a), vector<vector<type>>( \
            (b), vector<type>( \
                __VA_ARGS__ \
            ) \
        ) \
    )
// 4D
#define VVVVC(name, type, a, b, c, ...) \
    vector<vector<vector<vector<type>>>> name( \
        (a), vector<vector<vector<type>>>( \
            (b), vector<vector<type>>( \
                (c), vector<type>( \
                    __VA_ARGS__ \
                ) \
            ) \
        ) \
    )
// 5D
#define VVVVVC(name, type, a, b, c, d, ...) \
    vector<vector<vector<vector<vector<type>>>>> name( \
        (a), vector<vector<vector<vector<type>>>>( \
            (b), vector<vector<vector<type>>>( \
                (c), vector<vector<type>>( \
                    (d), vector<type>( \
                        __VA_ARGS__ \
                    ) \
                ) \
            ) \
        ) \
    )
// 6D
#define VVVVVVC(name, type, a, b, c, d, e, ...) \
    vector<vector<vector<vector<vector<vector<type>>>>>> name( \
        (a), vector<vector<vector<vector<vector<type>>>>>( \
            (b), vector<vector<vector<vector<type>>>>( \
                (c), vector<vector<vector<type>>>( \
                    (d), vector<vector<type>>( \
                        (e), vector<type>( \
                            __VA_ARGS__ \
                        ) \
                    ) \
                ) \
            ) \
        ) \
    )
template <typename T>
int lwb(const std::vector<T>& vec, const T& x){
    return lower_bound(all(vec), x) - vec.begin();
}
template <typename T>
int upb(const std::vector<T>& vec, const T& x){
    return upper_bound(all(vec), x) - vec.begin();
}
template <typename T>
T max(const std::vector<T>& vec){ return *max_element(all(vec)); }
template <typename T>
T min(const std::vector<T>& vec){ return *min_element(all(vec)); }
template <typename T>
T rad(const T& x){ return x * PI/180; }
template <typename T>
using maxpq = std::priority_queue<T>;
template <typename T>
using minpq = std::priority_queue<T, std::vector<T>, std::greater<T>>;
// 最大値・最小値の更新
template <typename T1, typename T2>
bool chmax(T1 &a, const T2& b){
    if (a < b) { a = b; return 1; }
    return 0;
}
template <typename T1, typename T2>
bool chmin(T1 &a, const T2& b){
    if (a > b) { a = b; return 1; }
    return 0;
}
/**
 * @brief (dx, dy) を基準として、(x, y) の偏角を求める。
 * @remark 弧度法で、[0, 2π) の範囲で返す
 * @remark cw=true なら時計回り
 */
ld calc_arg(ld x, ld y, ld dx = 1, ld dy = 0, bool cw = false) {
    assert(x != 0 or y != 0);
    assert(dx != 0 or dy != 0);
    
    ld c = dx * y - dy * x; // 外積
    ld d = dx * x + dy * y; // 内積
    ld theta = atan2l(cw ? -c : c, d);
    if (theta < 0) {
        theta += 2.0L * PI;
    }
    return theta;
}
__int128 cross(__int128 x1, __int128 y1, __int128 x2, __int128 y2) { return x1 * y2 - y1 * x2; };
bool is_clockwise(__int128 x1, __int128 y1, __int128 x2, __int128 y2) { return cross(x1, y1, x2, y2) < 0; }
bool is_counter_clockwise(__int128 x1, __int128 y1, __int128 x2, __int128 y2) { return cross(x1, y1, x2, y2) > 0; }
bool is_collinear(__int128 x1, __int128 y1, __int128 x2, __int128 y2) { return cross(x1, y1, x2, y2) == 0; }
/**
 * @brief 弧度法 -> 度数法
 */
ld rad_to_deg(ld rad) {
    return rad * 180.0L / PI;
}
/**
 * @brief 度数法 -> 弧度法
 */
ld deg_to_rad(ld deg) {
    return deg * PI / 180.0L;
}

const int di4[4] = {0, -1, 0, 1};
const int dj4[4] = {1, 0, -1, 0};
const int di8[8] = {0, -1, -1, -1, 0, 1, 1, 1};
const int dj8[8] = {1, 1, 0, -1, -1, -1, 0, 1};

bool out_of_grid(const int& i, const int& j, const int& h, const int& w){
    if(i < 0 || j < 0 || i >= h || j >= w) return true;
    return false;
}

namespace math {

    ll pow(ll N, ll e) {
        ll res = 1;
        while (e) {
            if (e & 1) {
                res *= N;
            }
            N *= N;
            e >>= 1;
        }
        return res;
    }

    template <typename T>
    T floor (const T& x, const T& m) {
        T r = (x % m + m) % m;
        return (x - r) / m;
    }

    template <typename T>
    T ceil (const T& x, const T& m) {
        return floor(x + m - 1, m);
    }

    /**
     * @brief floor(sqrt(N)) を求める
     */
    template <typename T>
    T sqrt_floor(T N) {
        assert(N >= 0);
        ll R = sqrt(N);
        // R*R>N なら大きすぎるので減らす
        while (R * R > N) {
            R--;
        }
        // 二乗して N を超えないギリギリまで増やす
        while ((R + 1) * (R + 1) <= N) {
            R++;
        }
        return R;
    }

    /**
     * @brief ceil(sqrt(N)) を求める
     */
    template <typename T>
    T sqrt_ceil(T N) {
        ll R = sqrt_floor(N);
        if (R * R == N) {
            return R;
        }
        return R + 1;
    }

    int log2_floor(ll N) {
        int res = -1;
        while (N != 0) {
            res++;
            N /= 2;
        }
        return res;
    }

} // namespace math

template <typename T, typename F>
T bisect(T& ok, T& ng, const F& f) {
    while (std::abs(ok - ng) > 1) {
        T mid = (ok - ng) / 2 + ng;
        (f(mid) ? ok : ng) = mid;
    }
    return ok;
}

template <typename T, typename F>
T bisect_real(T& ok, T& ng, const F& f, int itr = 80) {
    while (itr--) {
        T mid = (ok + ng) / 2;
        (f(mid) ? ok : ng) = mid;
    }
    return ok;
}

#include <fstream>

std::ofstream debug_outfile;
std::ostream* debug_out = &std::cout;

void Initialize_DebugOutput(){
    debug_outfile.open("debug.txt");
    debug_out = &debug_outfile;
}

#ifdef LOCAL

namespace debug {

    template <typename T>
    void debug_print(const T& t){
        *debug_out << t;
    }

    template <typename T, typename... Args>
    void debug_print(const T& t, const Args&... args){
        *debug_out << t << ", ";
        debug_print(args...);
    }

    // pair
    template <typename T1, typename T2>
    void debug_print(const std::pair<T1, T2>& p){
        *debug_out << "{" << p.first << ", " << p.second << "}";
    }

    // tuple
    template <typename Tuple, std::size_t... Is>
    void print_tuple(const Tuple& t, std::index_sequence<Is...>){
        ((*debug_out << (Is == 0 ? "" : ", ") << std::get<Is>(t)), ...);
    }

    template <typename... Args>
    void debug_print(const std::tuple<Args...>& t){
        *debug_out << "{";
        print_tuple(t, std::index_sequence_for<Args...>{});
        *debug_out << "}";
    }

    // map
    template <typename Key, typename Value>
    void debug_print(const std::map<Key, Value>& m){
        *debug_out << "{\n";
        for(auto it = m.begin(); it != m.end(); it++){
            if(it != m.begin()) *debug_out << ",\n";
            debug_print(*it);
        }
        *debug_out << "\n}";
    }

    // set
    template <typename T>
    void debug_print(const std::set<T>& s){
        *debug_out << "{";
        for(auto it = s.begin(); it != s.end(); it++){
            if(it != s.begin()) *debug_out << ", ";
            *debug_out << *it;
        }
        *debug_out << "}";
    }

    // 1D vector
    template <typename T>
    void debug_print(const std::vector<T>& vec){
        *debug_out << "[";
        bool f = std::is_integral<T>::value || std::is_floating_point<T>::value || std::is_same<T, char>::value;
        for(size_t i = 0; i < vec.size(); i++){
            if(!f){
                *debug_out << '\n';
            }
            debug_print(vec[i]);
            if(i != vec.size() - 1) *debug_out << ", ";
        }
        if(!f){
            *debug_out << '\n';
        }
        *debug_out << "]";
    }

    // 2D vector
    template <typename T>
    void debug_print(const std::vector<std::vector<T>>& vec){
        *debug_out << "[\n";
        for(const auto& row : vec){
            *debug_out << "  ";
            debug_print(row);
            *debug_out << "\n";
        }
        *debug_out << "]";
    }

} // namespace debug

#define debug(...) do{ \
    *debug_out << #__VA_ARGS__ << " = "; \
    debug::debug_print(__VA_ARGS__); \
    *debug_out << '\n'; \
} while(0)
#else
#define debug(...) do {} while(0)
#endif

namespace input {

    template <typename T>
    void read(T& t) {
        std::cin >> t;
    }

    template <typename T, typename... Args>
    void read(T& t, Args&... args) {
        std::cin >> t;
        read(args...);
    }

} // namespace input

#define READ(type, ...) \
    type __VA_ARGS__; \
    input::read(__VA_ARGS__)
#define INT(...) READ(int, __VA_ARGS__)
#define LL(...) READ(long long, __VA_ARGS__)
#define DOUBLE(...) READ(double, __VA_ARGS__)
#define LD(...) READ(long double, __VA_ARGS__)
#define STRING(...) READ(std::string, __VA_ARGS__)
#define CHAR(...) READ(char, __VA_ARGS__)
#define VI(vec, type, a) std::vector<type> vec(a); for(int i = 0; i < a; i++) std::cin >> vec[i]
#define VI2(vec1, vec2, type, a, b) std::vector<type> vec1(a), vec2(b); for (int i = 0; i < a; i++) std::cin >> vec1[i]; for (int i = 0; i < b; i++) std::cin >> vec2[i]
#define VI3(vec1, vec2, vec3, type, a, b, c) std::vector<type> vec1(a), vec2(b), vec3(c); for (int i = 0; i < a; i++) std::cin >> vec1[i]; for (int i = 0; i < b; i++) std::cin >> vec2[i]; for (int i = 0; i < c; i++) std::cin >> vec3[i]
#define VI4(vec1, vec2, vec3, vec4, type, a, b, c, d) std::vector<type> vec1(a), vec2(b), vec3(c), vec4(d); for (int i = 0; i < a; i++) std::cin >> vec1[i]; for (int i = 0; i < b; i++) std::cin >> vec2[i]; for (int i = 0; i < c; i++) std::cin >> vec3[i]; for (int i = 0; i < d; i++) std::cin >> vec4[i]
#define VI5(vec1, vec2, vec3, vec4, vec5, type, a, b, c, d, e) std::vector<type> vec1(a), vec2(b), vec3(c), vec4(d), vec5(e); for (int i = 0; i < a; i++) std::cin >> vec1[i]; for (int i = 0; i < b; i++) std::cin >> vec2[i]; for (int i = 0; i < c; i++) std::cin >> vec3[i]; for (int i = 0; i < d; i++) std::cin >> vec4[i]; for (int i = 0; i < e; i++) std::cin >> vec5[i]
#define VI2_(vec1, vec2, type, a) std::vector<type> vec1(a), vec2(a); for (int i = 0; i < a; i++) std::cin >> vec1[i] >> vec2[i]
#define VI3_(vec1, vec2, vec3, type, a) std::vector<type> vec1(a), vec2(a), vec3(a); for (int i = 0; i < a; i++) std::cin >> vec1[i] >> vec2[i] >> vec3[i]
#define VI4_(vec1, vec2, vec3, vec4, type, a) std::vector<type> vec1(a), vec2(a), vec3(a), vec4(a); for (int i = 0; i < a; i++) std::cin >> vec1[i] >> vec2[i] >> vec3[i] >> vec4[i]
#define VI5_(vec1, vec2, vec3, vec4, vec5, type, a) std::vector<type> vec1(a), vec2(a), vec3(a), vec4(a), vec5(a); for (int i = 0; i < a; i++) std::cin >> vec1[i] >> vec2[i] >> vec3[i] >> vec4[i] >> vec5[i]
#define VVI(vec, type, a, b) std::vector<std::vector<type>> vec(a, std::vector<type>(b)); for (int i = 0; i < a; i++) for (int j = 0; j < b; j++) std::cin >> vec[i][j]
#define VVVI(vec, type, a, b, c) std::vector<std::vector<std::vector<type>>> vec(a, std::vector<std::vector<type>>(b, std::vector<type>(c))); for (int i = 0; i < a; i++) for (int j = 0; j < b; j++) for (int k = 0; k < c; k++) std::cin >> vec[i][j][k]

template <int siz, int base, bool store_matches = false> // 文字列の種類数
struct AhoCorasick {
    struct Node {
        /**
         * @param accept なんらかの文字列の終端となっているか
         * @param cnt このノードで終わる（追加された）文字列集合の要素数
         * @param idxes このノードで終わる（追加された）文字列集合の要素の添え字
         */
        std::array<int, siz> nxt;
        std::array<bool, siz> is_child;
        int par;
        bool accept;
        int failure_link;
        int cnt;
        std::vector<int> idxes;
        Node() : par(-1), accept(false), failure_link(0), cnt(0), idxes() {
            for (int i = 0; i < siz; i++) {
                nxt[i] = -1;
                is_child[i] = false;
            }
        }
    };
    std::vector<Node> nodes;
    std::vector<int> ID;
    /**
     * @param M 文字列集合数
     */
    AhoCorasick(int M) : ID(M, -1) {
        nodes.emplace_back(Node());
    }
    /**
     * @brief idx 番目の文字列 S を追加する
     */
    void add(const std::string& S, int idx) {
        int pos = 0;
        for (char ch : S) {
            if (nodes[pos].nxt[ch - base] == -1) {
                nodes[pos].nxt[ch - base] = (int)nodes.size();
                nodes[pos].is_child[ch - base] = true;
                nodes.emplace_back(Node());
                nodes.back().par = pos;
            }
            pos = nodes[pos].nxt[ch - base];
        }
        nodes[pos].accept = true;
        nodes[pos].cnt++;
        if (store_matches) {
            nodes[pos].idxes.push_back(idx);
        }
        ID[idx] = pos;
    };
    /**
     * @brief idx 番目の文字列に対応する頂点番号を返す
     */
    int getID(int idx) {
        return ID[idx];
    }
    void build() {
        std::queue<int> q;
        for (int i = 0; i < siz; i++) {
            int c = nodes[0].nxt[i];
            if (c != -1) { // 根の子は全て failure_link=0
                q.emplace(c);
            } else {
                nodes[0].nxt[i] = 0;
            }
        }
        // 各状態の failure_link を、BFS 順で埋めていく
        while (!q.empty()) {
            /**
             * 親の failure_link を見る（ノードを X、それに対応する文字列を S とする）
             * -> もしそこから文字 i が生えているなら、文字列 S+i に対応するノードが c の failure_link になる
             * -> そうでないなら、X の failure_link を見る
             */
            int v = q.front(); q.pop();
            int f = nodes[v].failure_link;
            nodes[v].cnt += nodes[f].cnt;
            if (store_matches) {
                for (int i : nodes[f].idxes) {
                    nodes[v].idxes.push_back(i);
                }
            }
            for (int i = 0; i < siz; i++) {
                int c = nodes[v].nxt[i];
                bool child = nodes[v].is_child[i];
                if (c != -1 && child) { // 遷移先がある（ただし、子が存在するという意味で）
                    // 親 v の failure_link から i に対応する文字進んだ状態が、子 c の failure_link
                    nodes[c].failure_link = nodes[f].nxt[i];
                    q.emplace(c);
                } else { // 遷移先がない（子が存在しない）
                    // 親 v から、i に対応する文字の遷移で遷移先がないなら、
                    // 次行くべきなのは、親 v の failure_link から i に対応する文字進んだ状態
                    nodes[v].nxt[i] = nodes[f].nxt[i];
                }
            }
        }
    }
};

void FAST();

//const ll mod = ; using mint = atcoder::modint; atcoder::modint::set_mod(mod);
//const ll mod = 998244353; using mint = atcoder::modint998244353;
//const ll mod = 1000000007; using mint = atcoder::modint1000000007;

using namespace std;

/**
 * ```````````````````` ``````````````````````````.(ltOOOtz1?11<??JHfWpWXk\` ...(J+aAAWHHHa+JgkXvrrrrrrO=zOOw=~`` .JWUXXWUuuuXXXWpppppppppppppppppppppWSu
 * ``````````````````` `````````````````````````` (zttwvw1?????1(uXUHpbkdHXWWyWUUWWkkkXXVVVVVVVVWHHkmwvrvwv^  .(dWXXXfWSuuXXWppppppppppppppppppbbbppWHuuV
 * `````````````````` ```````````````````````````._OtrrXvOzzzuwZZwXXkMHWWWkkkkXyVVVyVVVWHWVVVVVVVWWyyyWHm....(XuXXXppfXuXWpppppppppppWWUYY""<!_`. .JSXXHY
 * `````````` `` ``` `` ` `` ``````` ````` ```````?-?OrOz4dWkZyyXWHWUUUUUWWWpWpHWkVVVVVVVVWHWVVVVVVWyyXkwXwuXWHHQWfpfWXppppppppbWUHMmgggggaAAwVTH8XXY!`.`
 * ````` `` ```` `   ``` ` `` `  `` `` ` ``` ``````` !?CzzdWHWkVKykXzzwXqkkHHHHHHHHHHHHHHWkfWHVyVVVVVVyVyWWWWkzzuUHHWppfpppWKY^_`````````` _.(wkV=~``. (d
 * `````` `` `` ``  ` ```` `` ``` ``` ``````` ` `````` ..?<1wWWWWyXkUWHVVVVVVVVVyyyyyyVfVffWWfVVVyVVVVfVVyyyyyyXXXZXUHkppWHh+J--.....(+dkWHW01-......+M@@
 * `` ``````` ```  `` `  `` `` ``` ` `` `  ````` .._<!```.vdWWWKWSwuXVfffVfVVffWWWQkHHHkkkfVkvWVVfWWWWfffVVyyyyyyyyAOXuHN@@@#MMHbWkHHHHbppppppppbHHHMMHHg
 * ```` `` ` ```  `  ` ``  `  `   ` ` ` `` `.._!```````.?(XWWWwUuuuXffpppWkHHHHWWpfpppHHHMNWfWdVVffVVfWHHkkfVVyyyyXkXXyXZWHbWWHHMHppppppppppppppppppppbbp
 * ```` ``` `` `  `` `  ` ` ` `` ` ` ` `` .!  ``````` (iJHHdfpkZZZZWpWkHHpppfpfppVVyVpppffpWfffffffffffffppHHWffVyVWHkXXVWkMM@#kWpppppppppppppfpppppppppp
 * ``` `` ````` ```````` ` ` `  `  ` ` ._``   `  ` ..7jzwWpppppWZZXHMHpppppfpfpfWVyWkHHppppfppfpHH@HkpppfpffVWHkffVyyyzUHkVWXMM@@@#HWWHHHMNkppppppppppppp
 * ````` `` `` `  `   `  ` `` ``` ` ` _``  ` ``.._!.(OwXUXyWpppWkHWXWWWpppppfppfWkHWVVyyVffppfpfppWHMNkffVVVVffWHpfffyzzWVHkyHWM@@#MSQMkbMMNkWppppppppppp
 * `` `` ```  ` ` ` `   `        ` ` ~` `` .._```.(1uUOrrzXXWWHWZ0T1dZypppffpfWHHpfVyWyVyVyfpVWfpfffpHMNpVVWpfpppHkfWuuuXyyyWWWWMMByWMMMHWZZZXHHppppppppp
 * `` `` ``  `` ` ` `  `  ` `        ..._~   ...((uZllttrrwQWUUZ=(dZZZZWpppfpWHpWWpfXXVVfffVfpVVyVVffpfHNpffffpffpWHWZZXXVyVyyWWWHXdBWZZZZZZZZZXppppppWWW
 * ``` `` `    ` `   ` `  `  `` .._<_-_::<~.~-<_(v?1=lltzAVXrw>(zwXZZZZXWWWkHpWWHfpXwfpffpfffffVffffpfppWNpppfpfpppWNWXXpfffyyyWNKHyOOZuuuZZZZZWWppWWWkHH
 * `` ````  ` ` `  `  `  ` ` .<!_<<::<<~<<<~<~_J>;>>?1lzd0ttv~(=lzOwXZZZQWHWWWHHffWOfpffpfppfffpfppffffppWNpfffpffppWMWWWpppffVHHyyykOltZUUUWHWH@@#HHpppp
 * ``` `    `` `  ` `   `  .>~_((<!`      -__(v(;;>>??u6<+lv-z1zzzzlOwX9CjSZXHUXpfSdffpfffffpffpfffpfpffffWHfppfpfpfWZHkppppppHWVyyyyZlllzzuuuuWMHppppppp
 * ` ```` `  ` ` ` `  `   J-J<!        `.!-_(!(:;;>>?dC?=z2(llttw0rzZ!~~(XuuWSuXWWzffffffffffpffffffffpfffpHfppfpWUZZZZMMHkppWHkffVyyZll=wvzzzuUMHppppppW
 * `` `` ` `  ` `  `  ` `.1^       `   _ ._J!(::;>>?v1??zZ(==llO0tZ^....(OOXHuuuu0dWpWfpfppfffpfpfppfWfffpfWHfpHSuZuuZXXHHHHHHNHpppfWwl=lOOOzzzwdkHWppWMH
 * ```` ` ``` ` ` ` `   `.! ` ` ``   .! ~(z!(::;;>>v1??dz1=??=zyzv~.....JtdzOwXuuIwXRuUWWWUUWffWWffffkfffffWHuuuWkZuZXfppHHHHHWHWpWHfZOztXyyyVfWkMHWHHpWp
 * ``` ``` ` `` `  `  `  . `   `    .` (?(~(::;;>>zz??dz0=???z=Zv_......wO%zz1lOXzwXkuuuuuuuuuuXkuuuXXXffpWuXkuuZWkuXffffpHfpppWMHpWQmQQQHHgHHQkyWMMkkWHH
 * `` `` ` ._`   `  `  `     `     (  /`.!.~<(;>>1C??dzwI??1v<_z!.`.....zd<Zlz?=z<OXKuuuuuuuuuuuWuuuuuZXWWXuXKuuuuUkXppffppHffpffHMM@@@#HHgHHHHWHWMmmHHHH
 * `  `` (???+?i--`` ` `` ` `  `  . .!  ~ __(;;>?z==j0wZ<<+C~_.-_`````.`(z.Ollz??<1dKXSuuuuuuuuuXuuuuXXwuuuuXHuuuXXWHWfpfpWWWWfpWHfHMMMH@@@#HHHMHMMMgHHQk
 *   ```(?zv?1+>>><+.  ` `  `  ` .~.!` /` (_:;>>1I=1kwOZ;<<i-..`.`.``.`.-j_(lwl=1+(IXzwXuuuuuuuuXXuuuXuwuuzzXHfVffWWUHSVwwAAQHfWHffWMM@@#MMHMMMMggggHHHyZ
 *  `` .wZ!``` ?1>;<(<<-. `  `  `_.~ `.~`.<(;>>?zI=dzwf(+x___<--.`.``.```.~_wdylll<I(kzZzwXuuXXuXRXuuXkwuwrrwTTOOwwAXWHHfffffHWHHffWMMM@@#HHHM@@#HHyyyZZZ
 * ````.Uk` ``` `_1+;;_~<_~~_....!-..<>` <~>>???==1kXf_.z}__..-1i.`.``.````.(ZXzl=z1.(ywz1zXWfffpHffWXHZzwwrtjdWfVfffffWqkffffMHfffWMMgMMMMMHHpfffffVyyyy
 * `````.O;`` ` ``  ?1<;;:_:__` .<~~~_:`.<(>??==z=duX~...~......_1-..`.`.`...(OzOll1-.(wwltOwXWfWNffffHkVVXXXXXVffffffffpHHWpWZwHfpHMNkkWffffpffffppfpfVy
 * ``` ``.X `  .......(?<<___:~~_1_ ` _ +<(??===zOdX\_...(.((m--.-1l....`..`.._?+1zlI_._1wllltOwWMpfffHkVyyZZXXZVfWXUUUUSOdHsAdWHpW@#MHHHHHHHHHWWWWffppWW
 * `` .-ztz+++(---   ``````  ```` ~ ` ~.z<(?===ldkdK~.jJd@MMMMMkW+_(l.....`..`..._-?7l_..(4lllltdMWWffqSfyZuwZ<usv0wdHpkfWffHHkfWk@@#fffffpffVyyVVVVWWH@@
 * `.X0wZzwzzvrwzv111+--.. ````````  ._.Jz<=llllwydK~(H@#Y<+gHHMMNh<(-...................._1z=llwVRwXWkXfVyXXwwXffpffffffffffWHHWW@MNffffffffVyVWWHgg@#HH
 * (0ldZzzzZOz1111zzzz++-(<<<<<~<<~((+O-dk<ttttttWyH(HH3~~(MH..JHMN/<.......`.`.............?z==dl4ttwWdVfffVWVfffffffVfffffWffMHHWMyyVVVfppkkHHHHHWpfpfp
 * wllwwuZ1?>>>+&??~`   ``_~~!!!?jSzzzwySXyzrvrrrdfH_Wf_~(HgHWHWHuWb............`............(O=d~(ZlOSzXWWfWHffffffffffffffWHVWNWWHHyyyyyffffffpfffpfppp
 * jOlwwuI??+zw=``` ` ..` ` `` _.uXuZZZZXkW2wzuzzzHH.?Wr~(HZzHWWWHHD~~.~~..................~.~(OS._I=dSlOOXUWMfffffpWffpWWfffWyyWMHWWHkyyyVfffpfppfpfpfpW
 *  jZwZuXzvzw\`  ` (z?=Oi.` `. ,zvwVXV777=?1XuuuuX@.::C~?StrWW8OHD3~.~~.~~.~.....(+7777777COOOW+--Zj3I===lOb#WWfffWHffffWWffWHyyWHHkWHWWWVffpffffpppb0o(
 * ``(zywUUXwd/` ` .1?====zO,`.. 4luW<` `````?4kuuzX&;::::O1<+1tOK<~~..~.~~~.~~.~.._<<!~((--..~..~(wC1C===ydW0ZwUWfWHfffffWWfVWyyyWKWHkWMWWHkWppfpfffppfp
 * ````.7XXI?+11+.`(Ov1zz===lOi__.4dyWe.````.JkZWWQXXk+;:::<<~+xC~~~.~~.~.~.~.~~~~~_(&HMMMNHWXJ(,~<~~(I==dwWWz1lOwXWHfpffffWffWHyyyWkyWHWHKHHkHHWkQkHpfpp
 * `````` 70?I>>>+:.I1zOrvvwv1zzO&-ZWVWWW&JUUuuuwZf_?TTTC<:::~~~~~~~~~~~.~~~.~~.~~(YCjM#^_?WMNM@e_..~v=uXWHXDv+==lOdKWVffpffXffNfVXVNVVVHkWkWffpHWppppfpp
 * ` `` ``.1d1?>>>z 1ztrrvZ!`` ?1zOwXuuuuuuuuuuzzXS.(;;;::::::~~~~~~~~~~~.~~~.~~~~~~(M@HHKXWWUMM@HC~(GZu0OWWv+====jHROwUWVffWWfWNfffWNfffWNWHpffffffpfppW
 * ```?Ozwv^J????1r`(zrrrrC``````.7vOOOZXXuuuuuzOdr.;;;;;::::::~__``_~~~~~~~~~~~~~~_d9Owqbb#HXdSM@b~(?7~(dXS+=====dWS==OOXXyVZfWMWfffMfffffNWHppppWkkH#=`
 * ``    ..J===?zC~:~?zOrvI` .<<<<.`?1ZVwzzuuuZ1wX].<:;;;:::::~:_`` ~~~~~~~~~~~~~~~(6tOdHWHIdgM<J@HC~~~~(H5+=====d8ZW==?1zOZX0XWMNfffWH@HHHHNM@@@@@#"~` (
 * `` .?6wsuuzZ=<:::::(CwrZ+````. {...JUAOltt1xtOAk.(;:;::::::::_` ~~~~~~~~~~~~~~~~?6<<+zZztdH3(JWK<~.~_Z1=?===?uKz?dv??<>?=zOzXMHKVfWM@@@@@MM@HY"````.dp
 * ~~<::;;;:;:::::::::::~??77<_` ~11==z?7!?7>TUWY(J[.<::;:::::::::<::~:~~~~~~~~::::::<:<;+OzY~(dX=~~~~-JIz=????1WZuudI>>>>>???<dWHNZyW@g@@@@M"!`````.(Hff
 * .`-<;:;;:::::::::::~~``````` `  ..._<?0UOWp=(OXwX/-<;;:::::::~:::::::::::::::::::::::<7<__?C<::~~_JZ1z1?>>>+ITuuuXP>;>;;;;;<XzXWwXWmHY=~?````. .JWVyVV
 * _+<<1++<;;;;;;;::::_- ..._~<<!~....`.(OCXV<dSXfWVWo-;;:;:::::::::~:::::::~:::::::;:;:;:;::<+++++z0ww0=?>>>+>__zrwwD;;::;:::<ZwzV+dnJ-.. `` .(dWyVyyVWV
 * +<I>>>1+1I++;;;;;;<c?>_........`.`..._~(V+VXWpbpXpHn_;;;;::;1+::::::::::::::::;;;;;;;<u&<:;;?7TWWUwttl??+v<~<<ztzOS;;:::::jCzzwCJXwwZXUWUXUZyyyVyVyWS!
 * zOOzzz<<>zzv;+++zzIOI&-_<<---...`.....(+uVWWpbbkRWHzS(;;;;;;;:<;;::::::::::;;;;;;;;;;;;+TXXUU0vrrrrttwy6<.._<<1ttdI:;;;:;+I(+zz>:;;>>?1zOwwzuZyyyWY!``
 * <<?1ztvzj1<<<<+1+>jz<>>+(<>+(?<1_~____jdWpWbkkkHNkWZ=vx;;;;;;;;;;<+11&+:;;;;;;;;;;;;;;;;+1+OWUXwwOOv7<<<((uwrz<<1d<::::;JC><:::::::;;;>?1zzOwXuXXWkka-
 * 1<<+z17<<<<(><z>OxOzzOzI????<+GjwO+_(jkWkkkkqqHWHWXHz=zS+;;;;;;;;;;;;;;;;;;;;;;;;;;;;>;><+&Mc<<<::_(J+gWZZZuzvrOjS;;;;jZ+<(::::::::::;;>>?1ud6wdHpbkkq
 * ZO<::(<>++(1+;zzdWHHmzzIl=l===znXWWyzWfHqqqmmHWXWlXXS<::?x>;;>;;;>;>;;>>;;;;;;;;;;;>>;j&UGdWWNkXWWZuXWWkXWHkkZuAD>;+JUOXIJOz++<;:::<+++xOOwV?1dXZyfpbb
 * ;j<+z;;;>+v:11jHpppppWkO1ll====vkkbpXkbHmmmmHZZXWO04Xy:::?S<>>>>>>>>>>>>>>>;>;;;>+i&ZY<;JwjWMyyyuZZZHZuuuXWXXWHkswUwrO&+OwGx<111111????1xV<;j0lOwXXyVp
 * ;j<;<?11<::;+wHffpppfpkWz1l=====RHHbqbbHHUUXWyyyWf<<HW<:::;ze&&&&&&&&&&&&&&&zZVTC<>;>;;;j3(MkyyZwyyXWyyWWkXuXkuZuXWkXvrrttttZ0y&z???1+vC;:;jC?==lOwXXy
 * <+z1++;;;++ZwdVVfffW9UWkXnC1zz=u0XHpHUY=_jkuwXUUR;;;dW2;:::jRzSzS<>>>>>>>>>>>>>>>;>>;>+J>(HkkHWSdyyWVVyyyyWRZXWkyZZwwXXwzzzOttttOTTC<;;;;<J?????=1zzOX
 * z+z;++z1z1zwvXyyVVfD==llVXs-.` _``.``..(XXXXffkXD;jdHW>;;::+Sv`Ow_<>>?>???>>>>>>>>>>++3::JHqkkHkXZdbVVVVVVW91><dkyyZZXwzwwZOOz+++;;;;;<++==?????<<::;;
 * >+I?C++CzI=zOIUWyyWr<<1z<<zXo-. ```..JwXXwfffffWWggHB3;:;;:<z_` 7..(>>>?>?????>>?1&vuJZT=dqqkkkXySwpVVVVVVK>;;;;?HyyyyyyXXzvOzz=v<~<?<<+=======?+(::::
 * uxI+++I;>Zz1<!`(4XX[``  JVwwwkUmAwzu0XzwXfpppWHgHBY<;;;;;:;;(-``` ?11&&+1???1&z7OxC>::::(dqkkkKXHZzWWyVVVWS;;>;>;?HkfVyyVVfVXXXw<___.._<1=========??++
 * dyyWSCz1??<! ```` _?! _ UdWVVVyVyWHHHHHHgNBU6zzO<;::::::;+zljl.````` _:;;;<:<jv3<::::::<+WkkkHXHSuOd+UkyWK;;;>>>;>+WHfffffffpfWWkG-_~...._?1==l=======
 * yyVVS???<~```````````_``(ZWHVfffWWWHbHHHHUXOOz<:::~~~:::<jc;Z;?<<-..(:;;+++?<;;:;;:;:;+zzMkbkWHSuuuuS?zWW>;;;;++&&swpMkpffffWpppbWWs-_~~~~.~_1llllll==
 * ZWWV1<<`````````````.````jdWkffWHgHHmmmHC>>>>>;::(!```-<<<vd><::__:<<?7<<;;:;::;;:;<+zlldHkHWHXZZZuuXz1d>>+udXfffWWfWpWMkpppfpbkkkkHWA+(_~~~~~_1llllll
 * uX6<!``` ..((<>>><(-_```` SWWfWHmm@Mmm#<>>>>>>;;::<-.. .<_(J(<<;:;:;;:;;;;;;;;;;;+zz1<<+dqHW8XXZZZZXZRdOdXfffffffffpfpfpWMkpppbkkkqqqqqWkkwz&+xzttrtzt
 * ZzlO+.(<>?????>????z<.````(ZVHHmHHHmH@>>>>>>>>>>;;;:;<?+<<<;;+;;<<;;;;;;><<>>>>>;>><<<1dHWHXzvvvvvwWZHX9TTOOOTUfffffffpfppWMHbbbkqqqqqqqqHkkXuzzvvrrrt
 * 11OOrwXx???>>>>>>>+>;!````.JdHHH@MHH@<>>>>>>>+z+>>>>;><++======>;<(uw00XXXXXA&++;;;;<jHHHHyyyXzzwXXdyHjI?++&zdXpWWpWVffffffppMNWkkkqkqqqmmmKUUUuuzzvvr
 * -<=wwrrwG+>>+<<<<<<<~ .-(<j6vWHHmqq@_(>>>>>+zOOtO+>>>>1ll====z<+JXvzzzwVC117WVVVWWHHMHWVyVyVVVWXSdHHWHWHHWHHHHHHHHHkWWWppffffppHMkkkqqqqqqmRlllz><?wuz
 * -_<?zOrrr0+v<_.``..__~(+77dzlvWXHqH!.(>>>>1IOjztttO+>>>>>>>;;;;drrvvw6>>>>>;jWVVVVXkkXXWWWWWWHpHHQHMkkHMHkpbbpbNWHffWHkWHWWfpffppbMNHqqqqqqRllllzz+dXZ
 * 一回目つまずき後悔してハイ。それで終わりでいいワケ？ もう一度立ち上がるそんな君じゃなきゃ私は寂しい
 */

void solve() {

    STRING(S);
    int N = (int)S.size();
    INT(M);
    AhoCorasick<26, 'A'> aho(M);
    rep (i, 0, M) {
        STRING(T);
        aho.add(T, i);
    }
    aho.build();

    int ans = 0, pos = 0;
    rep (i, 0, N) {
        pos = aho.nodes[pos].nxt[S[i] - 'A'];
        ans += aho.nodes[pos].cnt;
    }

    cout << ans << newl;

}

int main() {
    FAST();

    int t = 1;
    //cin >> t;
    while (t--) {
        solve();
    }

}

void FAST() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);
}