#include <bits/stdc++.h>

int N, M;
int number[110000], min[110000], max[110000];

class Binary_Indexed_Tree {
    #define lowbit(x) (x & (-x))

public:
    int num[110000];

    Binary_Indexed_Tree() {
        for (int i = 1; i <= 100000; ++ i)
            num[i] = -1e9;
    }

    void Add(int position, int val) {
        while (position <= 1e5) {
            num[position] = std::max(num[position], val);
            position += lowbit(position);
        }
    }

    int Query(int position) {
        int result = -1e9;

        while (position) {
            result = std::max(result, num[position]);
            position -= lowbit(position);
        }
        return result;
    }

    void clear(int position) {
        while (position <= 1e5) {
            num[position] = -1e9;
            position += lowbit(position);
        }
    }
}tree;

int dp[110000], p[110000];

bool cmp1(int &i, int &j) {
    return max[i] < max[j];
}

bool cmp2(int &i, int &j) {
    return number[i] < number[j];
}

void CDQ(int l, int r) {
    if (l == r) {
        dp[l] = std::max(dp[l], 1);
        return;
    }
    int mid = (l + r) >> 1;
    CDQ(l, mid);
    for (int i = l; i <= r; ++ i)
        p[i] = i;
    std::sort(p + l, p + mid + 1, cmp1);
    std::sort(p + mid + 1, p + r + 1, cmp2);

	for (int i = l, j = mid + 1; j <= r; ++j) {
		while (i <= mid && max[p[i]] <= number[p[j]]) {
			tree.Add(number[p[i]], dp[p[i]]);
			++i;
		}
		dp[p[j]] = std::max(dp[p[j]], tree.Query(min[p[j]]) + 1);
	}
    for (int i = l; i <= mid; ++ i)
        tree.clear(number[i]);
    CDQ(mid + 1, r);
}

int answer;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);

    std::cin >> N >> M;
    for (int i = 1; i <= N; ++ i) {
        std::cin >> number[i];
        max[i] = min[i] = number[i];
    }
    for (int i = 1, x, y; i <= M; ++ i) {
        std::cin >> x >> y;
        min[x] = std::min(min[x], y);
        max[x] = std::max(max[x], y);
    }

    CDQ(1, N);

    for (int i = 1; i <= N; ++ i)
        answer = std::max(answer, dp[i]);
    std::cout << answer << '\n';

    return 0;
}
/*

*/

#include <bits/stdc++.h>

typedef long long ll;

ll N, Q;
bool visit[210000];
ll cnt = 1, head[210000], next[210000], to[210000], value[210000];
ll size[210000], root, max[210000], S;

void AddEdge(ll u, ll v, ll val) {
    ++ cnt;
    next[cnt] = head[u];
    head[u] = cnt;
    to[cnt] = v;
    value[cnt] = val;
}

ll fa[110000];
ll len[110000];

void GetRoot(ll now, ll fat) {
    size[now] = 1;
    max[now] = 0;

    for (ll i = head[now]; i; i = next[i]) {
        if (visit[to[i]] || fat == to[i])
            continue;
        GetRoot(to[i], now);
        size[now] += size[to[i]];
        max[now] = std::max(max[now], size[to[i]]);
    }
    max[now] = std::max(max[now], S - size[now]);
    if (max[now] < max[root])
        root = now;
}

std::unordered_map<ll, ll> part[110000];

ll min[510000][20];
ll dfn[510000], fat[510000], tot, deep[510000];
ll lg[510000];

void Dfs(ll now, ll f) {
	deep[now] = deep[f] + 1;
	fat[now] = f;
	dfn[now] = ++ tot;
	min[tot][0] = now;
	for (ll i = head[now]; i != 0; i = next[i]) {
		if (to[i] == f)
			continue;
        len[to[i]] = len[now] + value[i];
		Dfs(to[i], now);
	}
	return;
}

ll Min(ll l, ll r) {
	if (deep[l] < deep[r])
		return l;
	return r;
}

void Pretreatment() {
	Dfs(1, 1);
	lg[1] = 0;
    for (ll i = 2; i <= N; ++ i)
		lg[i] = lg[i >> 1] + 1;
	for (ll i = N; i >= 1; -- i) {
		for (ll j = 1; i + (1 << j) - 1 <= N; ++ j) {
			min[i][j] = Min(min[i][j - 1], min[i + (1 << (j - 1))][j - 1]);
		}
	}
}

ll GetLca(ll u, ll v) {
    if (u == v)
        return u;
    
    u = dfn[u], v = dfn[v];
    if (u > v) 
        std::swap(u, v);
    u ++;
    
    ll len = lg[v - u + 1];
    ll answer = Min(min[u][len], min[v - (1 << len) + 1][len]);
    return fat[answer];  
}

ll GetDis(ll x, ll y) {
    if (x == 0 || y == 0)
        return 0;
    ll lca = GetLca(x, y);
    return len[x] + len[y] - 2 * len[lca];
}

ll sum[110000];
ll ans[110000], fuck[110000];

ll GetSum(ll now) {
    ll result = ans[now];
    for (ll i = now; fa[i]; i = fa[i]) {
        result += ans[fa[i]] - fuck[i] + GetDis(now, fa[i]) * (sum[fa[i]] - sum[i]);
    }
    return result;
}

ll Root;

ll GetAnswer() {
    ll now = Root, last = Root;
    ll has;
    bool flag = false;
    while (flag == false) {
        flag = true;
        has = GetSum(now);
        for (ll i = head[now]; i; i = next[i]) {
            ll temp = GetSum(to[i]);
            if (has > temp) {
                flag = false;
                has = temp;
                now = to[i];
            }
        }
        now = part[last][now];
        last = now;
    }
    return has;
}

void Solve(ll now) {
    visit[now] = true;
    part[now][now] = now;
    for (ll i = head[now]; i; i = next[i]) {
        if (visit[to[i]])
            continue;
        S = size[to[i]];
        root = 0;
        GetRoot(to[i], now);
        part[now][to[i]] = root;
        fa[root] = now;
        Solve(root);
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);

    std::cin >> N >> Q;
    for (ll i = 1, u, v, c; i <= N - 1; ++ i) {
        std::cin >> u >> v >> c;
        AddEdge(u, v, c);
        AddEdge(v, u, c);
    }
    Pretreatment();
    root = 0;
    max[0] = N + 1;
    S = N;
    GetRoot(1, 0);
    Root = root;
    Solve(root);
    for (ll i = 1, u, e; i <= Q; ++ i) {
        std::cin >> u >> e;
        for (ll now = u; now; now = fa[now]) {
            sum[now] += e;
            ans[now] += GetDis(u, now) * e;
            if (fa[now])
                fuck[now] += GetDis(u, fa[now]) * e;
        }
        std::cout << GetAnswer() << '\n';
    }
}

#include <bits/stdc++.h>

const int MAXN = 5e5 + 1000;

int N, M;
int num[3100000];
char ch[MAXN];

class Suffix_Array {
public:
    int barrel[MAXN], temp[MAXN];
    int SA[MAXN], rank[MAXN], height[MAXN];

    void SuffixArray() {
        int m = 26, n = N;
        for (int i = 1; i <= m; ++ i)
            barrel[i] = 0;
        for (int i = 1; i <= n; ++ i)
            barrel[rank[i] = ch[i] - 'a' + 1] ++;
        for (int i = 2; i <= m; ++ i)
            barrel[i] += barrel[i - 1];
        for (int i = n; i >= 1; -- i)
            SA[barrel[rank[i]] --] = i;

        for (int w = 1, tot = 0; w <= n; m = tot, tot = 0, w <<= 1) {
            for (int i = 1; i <= n; ++ i)
                if (i + w > n)
                    temp[++ tot] = i;
            for (int i = 1; i <= n; ++ i)
                if (SA[i] > w)
                    temp[++ tot] = SA[i] - w;

            for (int i = 1; i <= m; ++ i)
                barrel[i] = 0;
            for (int i = 1; i <= n; ++ i)
                barrel[rank[temp[i]]] ++;
            for (int i = 2; i <= m; ++ i)
                barrel[i] += barrel[i - 1];
            for (int i = n; i >= 1; -- i)
                SA[barrel[rank[temp[i]]] --] = temp[i];

            tot = 0;
            std::swap(temp, rank);
            for (int i = 1; i <= n; ++ i)
                rank[SA[i]] = (temp[SA[i]] == temp[SA[i - 1]] && temp[SA[i] + w] == temp[SA[i - 1] + w]) ? tot : ++ tot;
            if (tot == n)
                return;
        }
    }

    void GetHeight() {
        int n = N;
        for (int i = 1, k = 0; i <= n; ++ i) {
            if (rank[i] == 1)
                continue;
            if (k)
                k --;
            while (ch[i + k] == ch[SA[rank[i] - 1] + k])
                k ++;
            height[rank[i]] = k;
        }
    }
}SA;

namespace ST {
    int lg[MAXN];
    int ST[MAXN][20];

    void Pretreatment() {
        lg[1] = 0;
        for (int i = 1; i <= N; ++ i) {
            if (i >= 2)
                lg[i] = lg[i >> 1] + 1;
            ST[i][0] = SA.height[i];
        }
        for (int i = N; i >= 1; -- i) {
            for (int j = 1; i + (1 << j) - 1 <= N; ++ j) {
                ST[i][j] = std::min(ST[i][j - 1], ST[i + (1 << (j - 1))][j - 1]);
            }
        }
    }

    int GetAnswer(int l, int r) {
        if (l > r)
            return 0;
        int len = lg[r - l + 1];
        return std::min(ST[l][len], ST[r - (1 << len) + 1][len]);
    }
}

long long answer;

class Disjoint {
public:
    int fat[3100000];
    int size[3100000];

    void Pretreatment(int n) {
        for (int i = 1; i <= n; ++ i) {
            fat[i] = i;
            size[i] = 1;
        }
    }

    int Find(int x) {
        if (fat[x] != x)
            x = Find(fat[x]);
        return fat[x];
    }

    void Union(int x, int y, int val) {
        if (x == y)
            return;
        x = Find(x);
        y = Find(y);
        if (x != y) {
            fat[x] = y;
            answer += 1ll * size[x] * size[y] * val;
            size[y] += size[x];
        }
    }
}set;

class Sort {
public:
    int x, y, val;
}ask[MAXN * 6];

bool cmp1(const int &a, const int &b) {
    return SA.rank[a] < SA.rank[b];
}

bool cmp2(const Sort &a, const Sort &b) {
    return a.val > b.val;
}

std::map<int, int> map;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);

    std::cin >> N >> M;
    std::cin >> (ch + 1);
    N = strlen(ch + 1);
    SA.SuffixArray();
    SA.GetHeight();
    ST::Pretreatment();
    for (int i = 1, n; i <= M; ++ i) {
        std::cin >> n;
        set.Pretreatment(n);
        int cnt = 0;
        map.clear();
        for (int j = 1, x; j <= n; ++ j)  {
            std::cin >> x;
            if (!map[x])
                num[++ cnt] = x;
            map[x] ++;
        }
        std::sort(num + 1, num + 1 + cnt, cmp1);
        for (int j = 1; j <= cnt - 1; ++ j) {
            int left = num[j];
            int right = num[j + 1];
            ask[j] = {j, j + 1, ST::GetAnswer(SA.rank[left] + 1, SA.rank[right])};
        }
        std::sort(ask + 1, ask + 1 + cnt - 1, cmp2);
        answer = 0;
        for (int j = 1; j <= cnt - 1; ++ j) {
            set.Union(ask[j].x, ask[j].y, ask[j].val);
        }
        std::cout << answer << '\n';
    }
    return 0;
}