Problem: You are given a rooted tree on n vertices. The vertices are numbered from 1 to n; the root is the vertex number 1.

Each vertex has two integers associated with it: a_i and b_i. We denote the set of all ancestors of v (including v itself) by R(v). The awesomeness of a vertex v is defined as 

$$$\left| ∑_{w ∈ R(v)} a_w\right| ⋅ \left|∑_{w ∈ R(v)} b_w\right|,$$$

where |x| denotes the absolute value of x. 

Process q queries of one of the following forms: 

  * 1 v x — increase a_v by a positive integer x. 
  * 2 v — report the maximum awesomeness in the subtree of vertex v. 

Input

The first line contains two integers n and q (1 ≤ n ≤ 2⋅ 10^5, 1 ≤ q ≤ 10^5) — the number of vertices in the tree and the number of queries, respectively.

The second line contains n - 1 integers p_2, p_3, ..., p_n (1 ≤ p_i < i), where p_i means that there is an edge between vertices i and p_i.

The third line contains n integers a_1, a_2, ..., a_n (-5000 ≤ a_i ≤ 5000), the initial values of a_i for each vertex.

The fourth line contains n integers b_1, b_2, ..., b_n (-5000 ≤ b_i ≤ 5000), the values of b_i for each vertex.

Each of the next q lines describes a query. It has one of the following forms: 

  * 1 v x (1 ≤ v ≤ n, 1≤ x ≤ 5000). 
  * 2 v (1 ≤ v ≤ n). 

Output

For each query of the second type, print a single line with the maximum awesomeness in the respective subtree.

Example

Input

5 6
1 1 2 2
10 -3 -7 -3 -10
10 3 9 3 6
2 1
2 2
1 2 6
2 1
1 2 5
2 1


Output

100
91
169
240

Note

The initial awesomeness of the vertices is [100, 91, 57, 64, 57]. The most awesome vertex in the subtree of vertex 1 (the first query) is 1, and the most awesome vertex in the subtree of vertex 2 (the second query) is 2. 

After the first update (the third query), the awesomeness changes to [100, 169, 57, 160, 57] and thus the most awesome vertex in the whole tree (the fourth query) is now 2.

After the second update (the fifth query), the awesomeness becomes [100, 234, 57, 240, 152], hence the most awesome vertex (the sixth query) is now 4. 

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500000;
const int BSIZE = 100;
const int NBUCK = 200000 / BSIZE + 20;
int N, Q;
int par[MAXN];
int ssize[MAXN];
int sloc[MAXN];
vector<int> child[MAXN];
int nord;
int ord[MAXN];
long long a[MAXN], b[MAXN];
pair<long long, long long> pp[MAXN];
int M;
long long nadd[NBUCK];
int gind[NBUCK];
vector<int> qloc[NBUCK];
vector<int> bloc[NBUCK];
inline bool cmp(int x, int y) { return b[x] < b[y]; }
void flood(int cloc) {
  ord[nord] = cloc;
  sloc[cloc] = nord;
  nord++;
  for (int x : child[cloc]) flood(x);
}
long long ginter(int i, int j) {
  long long pv = -(a[j] * (long long)b[j] - a[i] * (long long)b[i]);
  if (pv < 0) return -1;
  return (pv / ((long long)b[j] - b[i]));
}
void gen(int ind) {
  if (ind * BSIZE >= N) return;
  qloc[ind].clear();
  for (int i = ind * BSIZE; i < min(N, (ind + 1) * BSIZE); i++) {
    a[i] += nadd[ind];
    a[i + N] += nadd[ind];
  }
  nadd[ind] = 0;
  long long mm = -8e18;
  for (int i : bloc[ind]) {
    if (a[i] * b[i] >= mm) {
      mm = a[i] * b[i];
      qloc[ind].clear();
    }
    qloc[ind].push_back(i);
    int q = qloc[ind].size();
    if (q >= 2) {
      int j = qloc[ind][q - 2];
      if (b[j] == b[i]) {
        if (a[j] > a[i])
          qloc[ind].pop_back();
        else {
          qloc[ind][q - 2] = i;
          qloc[ind].pop_back();
        }
        q--;
      }
    }
    while (q >= 3) {
      int x = qloc[ind][q - 3], y = qloc[ind][q - 2], z = qloc[ind][q - 1];
      if (ginter(x, y) >= ginter(y, z)) {
        qloc[ind][q - 2] = z;
        qloc[ind].pop_back();
        q--;
      } else
        break;
    }
  }
  gind[ind] = 0;
}
long long csolve(int ind) {
  if (ind * BSIZE >= N) return 0;
  assert(ind >= 0);
  assert(ind < NBUCK);
  if (!qloc[ind].size()) return 0;
  while (gind[ind] + 1 < qloc[ind].size()) {
    int x = qloc[ind][gind[ind]], y = qloc[ind][gind[ind] + 1];
    assert(b[x] < b[y]);
    long long cv = (a[x] + nadd[ind]) * b[x];
    long long nv = (a[y] + nadd[ind]) * b[y];
    if (nv >= cv)
      gind[ind]++;
    else
      break;
  }
  int x = qloc[ind][gind[ind]];
  return (a[x] + nadd[ind]) * b[x];
}
int main() {
  ios_base::sync_with_stdio(0);
  cin >> N >> Q;
  for (int i = 1; i < N; i++) {
    cin >> par[i];
    par[i]--;
    child[par[i]].push_back(i);
  }
  for (int i = 0; i < N; i++) ssize[i] = 1;
  for (int i = N - 1; i >= 1; i--) ssize[par[i]] += ssize[i];
  for (int i = 0; i < N; i++) {
    cin >> a[i];
    if (i) a[i] += a[par[i]];
  }
  for (int i = 0; i < N; i++) {
    cin >> b[i];
    if (i) b[i] += b[par[i]];
  }
  nord = 0;
  flood(0);
  for (int i = 0; i < N; i++) pp[i] = make_pair(a[i], b[i]);
  for (int i = 0; i < N; i++) {
    a[i] = pp[ord[i]].first;
    b[i] = pp[ord[i]].second;
    a[i + N] = a[i];
    b[i + N] = -b[i];
  }
  M = (N - 1) / BSIZE + 1;
  for (int i = 0; i < M; i++) {
    for (int j = i * BSIZE; j < i * BSIZE + BSIZE; j++)
      if (j < N) {
        bloc[i].push_back(j);
        bloc[i].push_back(j + N);
      }
    sort(bloc[i].begin(), bloc[i].end(), cmp);
    nadd[i] = 0;
    gen(i);
  }
  for (int q = 0; q < Q; q++) {
    int c;
    cin >> c;
    if (c == 1) {
      int v, x;
      cin >> v >> x;
      v--;
      int sstart = sloc[v], send = sloc[v] + ssize[v];
      int bstart = sstart / BSIZE, bend = (send - 1) / BSIZE;
      if (bstart != bend) {
        for (int i = bstart + 1; i < bend; i++) nadd[i] += x;
        for (int i = sstart; i < (bstart + 1) * BSIZE; i++) {
          a[i] += x;
          a[i + N] += x;
        }
        gen(bstart);
        for (int i = bend * BSIZE; i < send; i++) {
          a[i] += x;
          a[i + N] += x;
        }
        gen(bend);
      } else {
        for (int i = sstart; i < send; i++) {
          a[i] += x;
          a[i + N] += x;
        }
        gen(bend);
      }
    } else {
      int v;
      cin >> v;
      v--;
      long long ans = 0;
      int sstart = sloc[v], send = sloc[v] + ssize[v];
      assert(send <= N);
      int bstart = sstart / BSIZE, bend = send / BSIZE;
      if (bstart != bend) {
        for (int i = bstart + 1; i < bend; i++) ans = max(ans, csolve(i));
        for (int i = sstart; i < (bstart + 1) * BSIZE; i++)
          ans = max(ans, abs((a[i] + nadd[bstart]) * b[i]));
        for (int i = bend * BSIZE; i < send; i++)
          ans = max(ans, abs((a[i] + nadd[bend]) * b[i]));
      } else {
        for (int i = sstart; i < send; i++)
          ans = max(ans, abs((a[i] + nadd[bend]) * b[i]));
      }
      cout << ans << "\n";
    }
  }
}