#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ul = unsigned long;
void f_io() {
  ios_base ::sync_with_stdio(false);
  cin.tie(nullptr);
  ;
  cout.tie(nullptr);
}
ll MOD = 998244353;
const ll INF = (1e18 + 10);
ll gc(ll a, ll b) {
  if (!a || !b) {
    return max(a, b);
  }
  assert(b != 0);
  ll r = a % b;
  while (r) {
    a = b;
    b = r;
    r = a % b;
  }
  return b;
}
inline ll mult(ll a, ll b) { return (a * 1LL * b) % MOD; }
inline ll add(ll a, ll b) {
  b = (b % MOD + MOD) % MOD;
  return (a + b) % MOD;
}
ll pw(ll a, ll b) {
  if (b < 0) {
    return 1;
  }
  ll r = 1;
  while (b) {
    if (b & 1) {
      r = (a * r) % MOD;
    }
    b >>= 1;
    a = (a * a) % MOD;
  }
  return r;
}
const ll MAX = 1e6 + 7;
int n, tim = 0, latest[MAX], cnt[MAX], curn = -1, su[MAX], wh[MAX], curc = 0;
vector<int> fin[MAX];
pair<int, int> ra[MAX];
void insert(int x) {
  int p = cnt[x]++;
  if (p == 0) {
    curn++;
    wh[curn] = 1;
    ra[1].second++;
  } else {
    su[p]--;
    int x = ra[p].first;
    wh[x] = p + 1;
    ra[p].first++;
    ra[p + 1].second = ra[p].first;
  }
  tim++;
  fin[p + 1].push_back(x);
  latest[x] = tim;
}
void remove(int x) {
  int p = --cnt[x];
  ra[p + 1].second--;
  if (p) {
    su[p]++;
    ra[p].first = ra[p + 1].second;
    wh[ra[p + 1].second] = p;
  } else {
    curn--;
  }
  tim++;
  fin[p].push_back(x);
  latest[x] = tim;
}
int extract(int n) {
  while (fin[n].size()) {
    int x = fin[n].back();
    if (cnt[x] == n) {
      break;
    }
    fin[n].pop_back();
  }
  if (fin[n].size() == 0) {
    assert(0);
  }
  return fin[n].back();
}
vector<int> gr[MAX], ind[MAX];
vector<pair<int, int>> qq[MAX];
int a[MAX], sol[MAX];
vector<int> ve;
void dfs(int n) {
  insert(a[n]);
  for (int i = 0; i < qq[n].size(); ++i) {
    int l = qq[n][i].first, k = qq[n][i].second;
    int x = (l > 1 ? k + curn + 1 + su[l - 1] : k), an = -1;
    if (x - 1 <= curn) {
      an = extract(wh[curn - x + 1]);
    }
    sol[ind[n][i]] = an;
  }
  for (int x : gr[n]) {
    dfs(x);
  }
  remove(a[n]);
}
void ini(int n) {
  tim = 0;
  curn = -1;
  for (int i = 0; i <= n; ++i) {
    gr[i].clear();
    qq[i].clear();
    ind[i].clear();
    fin[i].clear();
    ra[i] = make_pair(0, 0);
    su[i] = 0;
  }
}
int main() {
  f_io();
  ll t = 1;
  cin >> t;
  while (t--) {
    ll q;
    cin >> n >> q;
    ini(n);
    for (int i = 1; i <= n; ++i) {
      cin >> a[i];
    }
    for (int i = 2; i <= n; ++i) {
      int p;
      cin >> p;
      gr[p].push_back(i);
    }
    for (int i = 0; i < q; ++i) {
      int v, l, k;
      cin >> v >> l >> k;
      ind[v].push_back(i);
      qq[v].push_back(make_pair(l, k));
    }
    dfs(1);
    for (int i = 0; i < q; ++i) {
      cout << sol[i] << " ";
    }
    cout << "\n";
  }
}

### Prompt

Please formulate a cpp solution to the following problem:

Petya has a rooted tree with an integer written on each vertex. The vertex 1 is the root. You are to answer some questions about the tree.

A tree is a connected graph without cycles. A rooted tree has a special vertex called the root. The parent of a node v is the next vertex on the shortest path from v to the root.

Each question is defined by three integers v, l, and k. To get the answer to the question, you need to perform the following steps: 

  * First, write down the sequence of all integers written on the shortest path from the vertex v to the root (including those written in the v and the root). 
  * Count the number of times each integer occurs. Remove all integers with less than l occurrences. 
  * Replace the sequence, removing all duplicates and ordering the elements by the number of occurrences in the original list in increasing order. In case of a tie, you can choose the order of these elements arbitrary. 
  * The answer to the question is the k-th number in the remaining sequence. Note that the answer is not always uniquely determined, because there could be several orderings. Also, it is possible that the length of the sequence on this step is less than k, in this case the answer is -1. 



For example, if the sequence of integers on the path from v to the root is [2, 2, 1, 7, 1, 1, 4, 4, 4, 4], l = 2 and k = 2, then the answer is 1.

Please answer all questions about the tree.

Input

Each test contains multiple test cases. The first line contains the number of test cases t (1 ≤ t ≤ 10^6). Description of the test cases follows.

The first line of each test case contains two integers n, q (1 ≤ n, q ≤ 10^6) — the number of vertices in the tree and the number of questions.

The second line contains n integers a_1, a_2, …, a_n (1 ≤ a_i ≤ n), where a_i is the number written on the i-th vertex.

The third line contains n-1 integers p_2, p_3, …, p_n (1 ≤ p_i ≤ n), where p_i is the parent of node i. It's guaranteed that the values p define a correct tree.

Each of the next q lines contains three integers v, l, k (1 ≤ v, l, k ≤ n) — descriptions of questions.

It is guaranteed that the sum of n and the sum of q over all test cases do not exceed 10^6.

Output

For each question of each test case print the answer to the question. In case of multiple answers, print any.

Example

Input


2
3 3
1 1 1
1 2
3 1 1
3 1 2
3 2 1
5 5
1 2 1 1 2
1 1 2 2
3 1 1
2 1 2
4 1 1
4 2 1
4 2 2


Output


1 -1 1 
1 1 2 1 -1 

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ul = unsigned long;
void f_io() {
  ios_base ::sync_with_stdio(false);
  cin.tie(nullptr);
  ;
  cout.tie(nullptr);
}
ll MOD = 998244353;
const ll INF = (1e18 + 10);
ll gc(ll a, ll b) {
  if (!a || !b) {
    return max(a, b);
  }
  assert(b != 0);
  ll r = a % b;
  while (r) {
    a = b;
    b = r;
    r = a % b;
  }
  return b;
}
inline ll mult(ll a, ll b) { return (a * 1LL * b) % MOD; }
inline ll add(ll a, ll b) {
  b = (b % MOD + MOD) % MOD;
  return (a + b) % MOD;
}
ll pw(ll a, ll b) {
  if (b < 0) {
    return 1;
  }
  ll r = 1;
  while (b) {
    if (b & 1) {
      r = (a * r) % MOD;
    }
    b >>= 1;
    a = (a * a) % MOD;
  }
  return r;
}
const ll MAX = 1e6 + 7;
int n, tim = 0, latest[MAX], cnt[MAX], curn = -1, su[MAX], wh[MAX], curc = 0;
vector<int> fin[MAX];
pair<int, int> ra[MAX];
void insert(int x) {
  int p = cnt[x]++;
  if (p == 0) {
    curn++;
    wh[curn] = 1;
    ra[1].second++;
  } else {
    su[p]--;
    int x = ra[p].first;
    wh[x] = p + 1;
    ra[p].first++;
    ra[p + 1].second = ra[p].first;
  }
  tim++;
  fin[p + 1].push_back(x);
  latest[x] = tim;
}
void remove(int x) {
  int p = --cnt[x];
  ra[p + 1].second--;
  if (p) {
    su[p]++;
    ra[p].first = ra[p + 1].second;
    wh[ra[p + 1].second] = p;
  } else {
    curn--;
  }
  tim++;
  fin[p].push_back(x);
  latest[x] = tim;
}
int extract(int n) {
  while (fin[n].size()) {
    int x = fin[n].back();
    if (cnt[x] == n) {
      break;
    }
    fin[n].pop_back();
  }
  if (fin[n].size() == 0) {
    assert(0);
  }
  return fin[n].back();
}
vector<int> gr[MAX], ind[MAX];
vector<pair<int, int>> qq[MAX];
int a[MAX], sol[MAX];
vector<int> ve;
void dfs(int n) {
  insert(a[n]);
  for (int i = 0; i < qq[n].size(); ++i) {
    int l = qq[n][i].first, k = qq[n][i].second;
    int x = (l > 1 ? k + curn + 1 + su[l - 1] : k), an = -1;
    if (x - 1 <= curn) {
      an = extract(wh[curn - x + 1]);
    }
    sol[ind[n][i]] = an;
  }
  for (int x : gr[n]) {
    dfs(x);
  }
  remove(a[n]);
}
void ini(int n) {
  tim = 0;
  curn = -1;
  for (int i = 0; i <= n; ++i) {
    gr[i].clear();
    qq[i].clear();
    ind[i].clear();
    fin[i].clear();
    ra[i] = make_pair(0, 0);
    su[i] = 0;
  }
}
int main() {
  f_io();
  ll t = 1;
  cin >> t;
  while (t--) {
    ll q;
    cin >> n >> q;
    ini(n);
    for (int i = 1; i <= n; ++i) {
      cin >> a[i];
    }
    for (int i = 2; i <= n; ++i) {
      int p;
      cin >> p;
      gr[p].push_back(i);
    }
    for (int i = 0; i < q; ++i) {
      int v, l, k;
      cin >> v >> l >> k;
      ind[v].push_back(i);
      qq[v].push_back(make_pair(l, k));
    }
    dfs(1);
    for (int i = 0; i < q; ++i) {
      cout << sol[i] << " ";
    }
    cout << "\n";
  }
}

```