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;
template <typename T>
inline T read() {
  register T sum = 0;
  register char cc = getchar();
  int sym = 1;
  while (cc != '-' && (cc > '9' || cc < '0')) cc = getchar();
  if (cc == '-') sym = -1, cc = getchar();
  sum = sum * 10 + cc - '0';
  cc = getchar();
  while (cc >= '0' && cc <= '9') sum = sum * 10 + cc - '0', cc = getchar();
  return sym * sum;
}
template <typename T>
inline T read(T &a) {
  a = read<T>();
  return a;
}
template <typename T, typename... Others>
inline void read(T &a, Others &...b) {
  a = read(a);
  read(b...);
}
int n, m, Block, cnt, A[200010], B[200010], a[200010], b[200010], mp[200010];
int L[1100], R[1100], bel[200010], tag[1100], dfn[200010], tfn[200010];
struct Edge {
  int v;
  Edge *next;
  Edge(int a = 0, Edge *b = NULL) {
    v = a;
    next = b;
  }
} * head[200010];
struct Node {
  long long x, y;
  long long calc(int k) const { return y - k * x; }
  long long operator*(const Node &o) const { return x * o.y - y * o.x; }
  bool operator<(const Node &o) const {
    return (x < o.x) || (x == o.x && y < o.y);
  }
  Node operator-(const Node &o) const { return (Node){x - o.x, y - o.y}; }
} cop[1100][200];
struct Bolck {
  int ty, siz[1100], pos[1100];
  long long mx[1100];
  Node node[1100][200];
  void Get(Node *p, int &siz, int &pos, long long &mx) {
    static Node sta[1100];
    int tp = 0;
    sta[++tp] = p[1];
    for (int i = 2; i <= siz; i++) {
      if (p[i].x == p[i - 1].x) continue;
      while (tp > 1 && (p[i] - sta[tp - 1]) * (sta[tp] - sta[tp - 1]) >= 0)
        tp -= 1;
      sta[++tp] = p[i];
    }
    if (ty) {
      pos = 1;
      while (pos < tp && sta[pos].y > sta[pos + 1].y) pos += 1;
    } else {
      pos = tp;
      while (pos > 1 && sta[pos].y > sta[pos - 1].y) pos -= 1;
    }
    mx = -sta[pos].y;
    siz = tp;
    for (int i = 1; i <= tp; i++) p[i] = sta[i];
  }
  void build(int k) {
    siz[k] = R[k] - L[k] + 1;
    for (int i = 1; i <= siz[k]; i++) {
      node[k][i] = cop[k][i];
      if (!ty) node[k][i].y = -node[k][i].y;
    }
    for (int i = 1, j = 1; i <= siz[k]; i = j) {
      while (j <= siz[k] && node[k][i].x == node[k][j].x) j += 1;
      if (i + 1 != j) sort(node[k] + i, node[k] + j);
    }
    Get(node[k], siz[k], pos[k], mx[k]);
  }
  bool check(int k, const Node &x, const Node &y) {
    return x.calc(k) > y.calc(k);
  }
  void move(int i, int tag) {
    if (ty) {
      while (pos[i] < siz[i] &&
             check(tag, node[i][pos[i]], node[i][pos[i] + 1]))
        pos[i] += 1;
    } else {
      while (pos[i] > 1 && check(tag, node[i][pos[i]], node[i][pos[i] - 1]))
        pos[i] -= 1;
    }
    mx[i] = -node[i][pos[i]].calc(tag);
  }
} T[2];
bool cmp(int x, int y) { return b[x] < b[y]; }
void init(int k) {
  int tot = 0;
  static int p[200010];
  for (int i = L[k]; i <= R[k]; i++) p[++tot] = i;
  sort(p + 1, p + 1 + tot, cmp);
  for (int i = 1; i <= tot; i++) {
    mp[p[i]] = i;
    cop[k][i] = {b[p[i]], -1ll * a[p[i]] * b[p[i]]};
  }
}
void down(int k) {
  if (!tag[k]) return;
  for (int i = L[k]; i <= R[k]; i++) {
    a[i] += tag[k];
    cop[k][mp[i]] = {b[i], -1ll * a[i] * b[i]};
  }
  tag[k] = 0;
}
void change(int l, int r, int c) {
  if (bel[l] == bel[r]) {
    for (int i = l; i <= r; i++) {
      a[i] += c;
      cop[bel[l]][mp[i]] = {b[i], -1ll * a[i] * b[i]};
    }
    down(bel[l]);
    T[0].build(bel[l]);
    T[1].build(bel[l]);
    return;
  }
  for (int i = l; i <= R[bel[l]]; i++) {
    a[i] += c;
    cop[bel[l]][mp[i]] = {b[i], -1ll * a[i] * b[i]};
  }
  down(bel[l]);
  T[0].build(bel[l]);
  T[1].build(bel[l]);
  for (int i = bel[l] + 1; i < bel[r]; i++) {
    tag[i] += c;
    T[0].move(i, tag[i]);
    T[1].move(i, -tag[i]);
  }
  for (int i = L[bel[r]]; i <= r; i++) {
    a[i] += c;
    cop[bel[r]][mp[i]] = {b[i], -1ll * a[i] * b[i]};
  }
  down(bel[r]);
  T[0].build(bel[r]);
  T[1].build(bel[r]);
}
long long query(int l, int r) {
  long long ans = 0;
  if (bel[l] == bel[r]) {
    down(bel[l]);
    T[0].build(bel[l]);
    T[1].build(bel[l]);
    for (int i = l; i <= r; i++) ans = max(ans, 1ll * max(a[i], -a[i]) * b[i]);
    return ans;
  }
  down(bel[l]);
  T[0].build(bel[l]);
  T[1].build(bel[l]);
  down(bel[r]);
  T[0].build(bel[r]);
  T[1].build(bel[r]);
  for (int i = l; i <= R[bel[l]]; i++)
    ans = max(ans, 1ll * max(a[i], -a[i]) * b[i]);
  for (int i = bel[l] + 1; i < bel[r]; i++)
    ans = max(ans, max(T[0].mx[i], T[1].mx[i]));
  for (int i = L[bel[r]]; i <= r; i++)
    ans = max(ans, 1ll * max(a[i], -a[i]) * b[i]);
  return ans;
}
void dfs(int k, int x, int y) {
  x += A[k], y += B[k];
  dfn[k] = ++cnt;
  a[dfn[k]] = x;
  b[dfn[k]] = abs(y);
  for (Edge *i = head[k]; i != NULL; i = i->next) dfs(i->v, x, y);
  tfn[k] = cnt;
}
int main() {
  T[0].ty = true;
  read(n, m);
  Block = max(1.0, sqrt(n / 6));
  for (int i = 2; i <= n; i++) {
    int x;
    read(x);
    head[x] = new Edge(i, head[x]);
  }
  for (int i = 1; i <= n; i++) {
    read(A[i]);
    bel[i] = (i - 1) / Block + 1;
  }
  for (int i = 1; i <= n; i++) read(B[i]);
  dfs(1, 0, 0);
  for (int i = 1; i <= bel[n]; i++) {
    L[i] = (i - 1) * Block + 1;
    R[i] = min(i * Block, n);
    init(i);
    T[0].build(i);
    T[1].build(i);
  }
  for (int i = 1; i <= m; i++) {
    int op, v;
    read(op, v);
    int l = dfn[v], r = tfn[v];
    if (op == 1) {
      int x;
      read(x);
      change(l, r, x);
    } else
      printf("%lld\n", query(l, r));
  }
  return 0;
}