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;
inline char nc() {
  static char buf[100000], *l = buf, *r = buf;
  return l == r && (r = (l = buf) + fread(buf, 1, 100000, stdin), l == r)
             ? EOF
             : *l++;
}
template <class T>
void read(T &x) {
  x = 0;
  int f = 1, ch = nc();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = nc();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 - '0' + ch;
    ch = nc();
  }
  x *= f;
}
const double eps = 1e-14;
const int inf = 1e9 + 1;
const int maxn = 2e5 + 5;
const int maxq = 1e5 + 5;
const int maxb = 1000 + 5;
int n, q;
int a[maxn], b[maxn];
int M;
int dfc;
long long v[maxn];
int p[maxn];
int L[maxb];
int R[maxb];
int st[maxn];
int en[maxn];
int bel[maxn];
int rnk[maxn];
int s1[maxb], p1[maxb];
int s2[maxb], p2[maxb];
int delt[maxb];
int head[maxn];
int mx[maxb][400];
int mn[maxb][400];
struct data {
  int op, v, x;
  long long an;
  data(int op = 0, int v = 0, int x = 0, long long an = 0)
      : op(op), v(v), x(x), an(an) {}
} ask[maxq];
struct edge {
  int to, nex;
  edge(int to = 0, int nex = 0) : to(to), nex(nex) {}
};
vector<edge> G;
inline void addedge(int u, int v) {
  G.push_back(edge(v, head[u])), head[u] = G.size() - 1;
}
inline int cmp(const int &x, const int &y) { return b[x] > b[y]; }
inline long long myabs(long long x) { return x < 0 ? -x : x; }
inline void update(int x, int d) {
  a[x] += d;
  v[x] = (long long)a[x] * b[x];
}
inline double slope(int x, int y) {
  return double(v[y] - v[x]) / (b[x] - b[y]);
}
void dfs(int u) {
  st[u] = ++dfc;
  rnk[dfc] = u;
  for (int i = head[u]; ~i; i = G[i].nex) {
    int v = G[i].to;
    a[v] += a[u];
    b[v] += b[u];
    dfs(v);
  }
  en[u] = dfc;
  if (b[u] < 0) b[u] = -b[u];
}
void rebuild(int x) {
  for (int i = L[x]; i <= R[x]; ++i) {
    update(p[i], delt[x]);
  }
  s1[x] = s2[x] = 0;
  delt[x] = 0;
  for (int i = L[x]; i <= R[x]; ++i) {
    if (s1[x] && b[mx[x][s1[x]]] == b[p[i]]) {
      if (v[mx[x][s1[x]]] < v[p[i]]) {
        --s1[x];
      } else
        continue;
    }
    while (s1[x] > 1 && slope(mx[x][s1[x] - 1], mx[x][s1[x]]) - eps <
                            slope(mx[x][s1[x]], p[i]))
      --s1[x];
    mx[x][++s1[x]] = p[i];
  }
  p1[x] = s1[x];
  for (int i = L[x]; i <= R[x]; ++i) {
    if (s2[x] && b[mn[x][s2[x]]] == b[p[i]]) {
      if (v[mn[x][s2[x]]] < v[p[i]]) {
        --s2[x];
      } else
        continue;
    }
    while (s2[x] > 1 && slope(mn[x][s2[x] - 1], mn[x][s2[x]]) + eps >
                            slope(mn[x][s2[x]], p[i]))
      --s2[x];
    mn[x][++s2[x]] = p[i];
  }
  p2[x] = 1;
}
long long query(int x) {
  while (p1[x] > 1) {
    int u = mx[x][p1[x]];
    int v = mx[x][p1[x] - 1];
    if ((long long)(a[u] + delt[x]) * b[u] < (long long)(a[v] + delt[x]) * b[v])
      --p1[x];
    else
      break;
  }
  while (p2[x] < s2[x]) {
    int u = mn[x][p2[x]];
    int v = mn[x][p2[x] + 1];
    if ((long long)(a[u] + delt[x]) * b[u] > (long long)(a[v] + delt[x]) * b[v])
      ++p2[x];
    else
      break;
  }
  int u = mx[x][p1[x]];
  int v = mn[x][p2[x]];
  return max((long long)(a[u] + delt[x]) * b[u],
             -(long long)(a[v] + delt[x]) * b[v]);
}
void init() {
  M = 300;
  for (int i = 1; i <= n; ++i) {
    bel[i] = (i - 1) / M + 1;
    if (!L[bel[i]]) L[bel[i]] = i;
    R[bel[i]] = i;
  }
  for (int i = 1; i <= n; ++i) p[i] = rnk[i];
  for (int i = 1; i <= bel[n]; ++i) {
    delt[i] = 0;
    sort(p + L[i], p + R[i] + 1, cmp);
  }
  for (int i = 1; i <= n; ++i) {
    v[i] = (long long)a[i] * b[i];
  }
  for (int i = 1; i <= bel[n]; ++i) {
    rebuild(i);
  }
}
inline void update(int l, int r, int x) {
  if (bel[l] == bel[r]) {
    for (int i = l; i <= r; ++i) {
      update(rnk[i], x);
    }
    rebuild(bel[l]);
  } else {
    for (int i = bel[l] + 1; i < bel[r]; ++i) {
      delt[i] += x;
    }
    for (int i = l; i <= R[bel[l]]; ++i) {
      update(rnk[i], x);
    }
    for (int i = r; i >= L[bel[r]]; --i) {
      update(rnk[i], x);
    }
    rebuild(bel[l]);
    rebuild(bel[r]);
  }
}
long long query(int l, int r) {
  long long an = 0;
  if (bel[l] == bel[r]) {
    for (int i = l; i <= r; ++i) {
      an = max(an, myabs((long long)(a[rnk[i]] + delt[bel[i]]) * b[rnk[i]]));
    }
  } else {
    for (int i = bel[l] + 1; i < bel[r]; ++i) {
      an = max(an, query(i));
    }
    for (int i = l; i <= R[bel[l]]; ++i) {
      an = max(an, myabs((long long)(a[rnk[i]] + delt[bel[i]]) * b[rnk[i]]));
    }
    for (int i = r; i >= L[bel[r]]; --i) {
      an = max(an, myabs((long long)(a[rnk[i]] + delt[bel[i]]) * b[rnk[i]]));
    }
  }
  return an;
}
int main() {
  read(n), read(q);
  memset(head, -1, sizeof(head));
  for (int i = 2; i <= n; ++i) {
    int p;
    read(p);
    addedge(p, i);
  }
  for (int i = 1; i <= n; ++i) {
    read(a[i]);
  }
  for (int i = 1; i <= n; ++i) {
    read(b[i]);
  }
  dfs(1);
  init();
  for (int i = 1; i <= q; ++i) {
    int op;
    read(op);
    if (op == 1) {
      int v, x;
      read(v), read(x);
      update(st[v], en[v], x);
    } else if (op == 2) {
      int v;
      read(v);
      printf("%I64d\n", query(st[v], en[v]));
    }
  }
  return 0;
}