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>
const int inf = 0x3f3f3f3f, Inf = 0x7fffffff;
const long long INF = 0x7fffffffffffffff;
__inline__ __attribute__((always_inline)) unsigned int rnd() {
  static unsigned int seed = 416;
  return seed ^= seed >> 5, seed ^= seed << 17, seed ^= seed >> 13;
}
template <typename _Tp>
_Tp gcd(const _Tp &a, const _Tp &b) {
  return (!b) ? a : gcd(b, a % b);
}
template <typename _Tp>
__inline__ __attribute__((always_inline)) _Tp abs(const _Tp &a) {
  return a >= 0 ? a : -a;
}
template <typename _Tp>
__inline__ __attribute__((always_inline)) _Tp max(const _Tp &a, const _Tp &b) {
  return a < b ? b : a;
}
template <typename _Tp>
__inline__ __attribute__((always_inline)) _Tp min(const _Tp &a, const _Tp &b) {
  return a < b ? a : b;
}
template <typename _Tp>
__inline__ __attribute__((always_inline)) void chmax(_Tp &a, const _Tp &b) {
  (a < b) && (a = b);
}
template <typename _Tp>
__inline__ __attribute__((always_inline)) void chmin(_Tp &a, const _Tp &b) {
  (b < a) && (a = b);
}
template <typename _Tp>
__inline__ __attribute__((always_inline)) void read(_Tp &x) {
  char ch(getchar());
  bool f(false);
  while (ch < 48 || ch > 57) f |= ch == 45, ch = getchar();
  x = ch & 15, ch = getchar();
  while (ch >= 48 && ch <= 57)
    x = (((x << 2) + x) << 1) + (ch & 15), ch = getchar();
  if (f) x = -x;
}
template <typename _Tp, typename... Args>
__inline__ __attribute__((always_inline)) void read(_Tp &t, Args &...args) {
  read(t);
  read(args...);
}
__inline__ __attribute__((always_inline)) int read_str(char *s) {
  char ch(getchar());
  while (ch == ' ' || ch == '\r' || ch == '\n') ch = getchar();
  char *tar = s;
  *tar = ch, ch = getchar();
  while (ch != ' ' && ch != '\r' && ch != '\n' && ch != EOF)
    *(++tar) = ch, ch = getchar();
  return tar - s + 1;
}
const int N = 200005;
struct edge {
  int v, nxt;
} c[N << 1];
int A[N], B[N];
int front[N], edge_cnt;
__inline__ __attribute__((always_inline)) void addedge(int u, int v) {
  c[++edge_cnt] = (edge){v, front[u]};
  front[u] = edge_cnt;
}
long long val1[N], val2[N];
int siz[N];
int dfn[N], id, rev[N];
void dfs(int x, int fa, int a, int b) {
  dfn[x] = ++id;
  rev[id] = x;
  a += A[x], b += B[x];
  val1[id] = a, val2[id] = abs(b);
  siz[x] = 1;
  for (int i = front[x]; i; i = c[i].nxt) {
    int v = c[i].v;
    if (v != fa) {
      dfs(v, x, a, b);
      siz[x] += siz[v];
    }
  }
}
const int S = 200;
int n, q;
int _q[N], _l, _r;
int t[N], pos;
long long a[N], b[N];
__inline__ __attribute__((always_inline)) long long X(int x) { return -a[x]; }
__inline__ __attribute__((always_inline)) long long Y(int x) { return b[x]; }
__inline__ __attribute__((always_inline)) bool check(int a, int b, int c) {
  if (X(b) == X(c)) return Y(b) < Y(c);
  return (Y(b) - Y(a)) * (X(c) - X(b)) <= (Y(c) - Y(b)) * (X(b) - X(a));
}
__inline__ __attribute__((always_inline)) bool Check(int a, int b,
                                                     long long c) {
  return (Y(b) - Y(a)) >= (X(b) - X(a)) * c;
}
__inline__ __attribute__((always_inline)) bool checK(int a, int b,
                                                     long long c) {
  return (Y(b) - Y(a)) <= (X(b) - X(a)) * c;
}
int Q[N][3];
long long ans[N];
int qwq[N];
void solve1(int L, int R) {
  long long tag = 0;
  auto build = [&]() {
    _l = 1, _r = 0;
    pos = 0;
    for (int i = L; i <= R; ++i) t[++pos] = i;
    std::sort(t + 1, t + pos + 1,
              [](int a, int b) -> bool { return -val2[a] < -val2[b]; });
    for (int i = 1; i <= pos; ++i) {
      a[i] = val2[t[i]];
      b[i] = 1ll * val2[t[i]] * val1[t[i]];
      qwq[t[i]] = i;
    }
    for (int i = 1; i <= pos; ++i) {
      while (_l < _r && check(_q[_r - 1], _q[_r], i)) --_r;
      if (_l == _r + 1 || X(i) != X(_q[_r]))
        _q[++_r] = i;
      else if (Y(i) > Y(_q[_r]))
        _q[_r] = i;
    }
  };
  auto Update = [&](int l, int r, int C) {
    if (l == L && r == R) {
      tag += C;
      return;
    }
    for (int i = 1; i <= R - L + 1; ++i) b[i] += tag * a[i];
    for (int i = l; i <= r; ++i) b[qwq[i]] += 1ll * C * a[qwq[i]];
    tag = 0;
    _l = 1, _r = 0;
    for (int i = 1; i <= R - L + 1; ++i) {
      while (_l < _r && check(_q[_r - 1], _q[_r], i)) --_r;
      if (_l == _r + 1 || X(i) != X(_q[_r]))
        _q[++_r] = i;
      else if (Y(i) > Y(_q[_r]))
        _q[_r] = i;
    }
  };
  auto Query = [&](int l, int r) -> long long {
    if (l == L && r == R) {
      while (_l < _r && Check(_q[_l], _q[_l + 1], tag)) ++_l;
      return a[_q[_l]] * tag + b[_q[_l]];
    }
    long long ans = 0;
    for (int i = l; i <= r; ++i) {
      chmax(ans, 1ll * a[qwq[i]] * tag + b[qwq[i]]);
    }
    return ans;
  };
  build();
  int x, y;
  for (int i = 1; i <= q; ++i) {
    int opt = Q[i][0];
    x = Q[i][1];
    int l = dfn[x], r = dfn[x] + siz[x] - 1;
    chmax(l, L);
    chmin(r, R);
    if (l > r) continue;
    if (opt == 1) {
      y = Q[i][2];
      Update(l, r, y);
    } else {
      chmax(ans[i], Query(l, r));
    }
  }
}
void solve2(int L, int R) {
  long long tag = 0;
  auto build = [&]() {
    _l = 1, _r = 0;
    pos = 0;
    for (int i = L; i <= R; ++i) t[++pos] = i;
    std::sort(t + 1, t + pos + 1,
              [](int a, int b) -> bool { return -val2[a] < -val2[b]; });
    for (int i = 1; i <= pos; ++i) {
      a[i] = val2[t[i]];
      b[i] = 1ll * val1[t[i]] * val2[t[i]];
      qwq[t[i]] = i;
    }
    for (int i = 1; i <= pos; ++i) {
      while (_l < _r && check(_q[_r - 1], _q[_r], i)) --_r;
      if (_l == _r + 1 || X(i) != X(_q[_r]))
        _q[++_r] = i;
      else if (Y(i) > Y(_q[_r]))
        _q[_r] = i;
    }
  };
  auto Update = [&](int l, int r, int C) {
    if (l == L && r == R) {
      tag += C;
      return;
    }
    for (int i = 1; i <= R - L + 1; ++i) b[i] += tag * a[i];
    for (int i = l; i <= r; ++i) b[qwq[i]] += 1ll * C * a[qwq[i]];
    tag = 0;
    _l = 1, _r = 0;
    for (int i = 1; i <= R - L + 1; ++i) {
      while (_l < _r && check(_q[_r - 1], _q[_r], i)) --_r;
      if (_l == _r + 1 || X(i) != X(_q[_r]))
        _q[++_r] = i;
      else if (Y(i) > Y(_q[_r]))
        _q[_r] = i;
    }
  };
  auto Query = [&](int l, int r) -> long long {
    if (l == L && r == R) {
      while (_l < _r && checK(_q[_r - 1], _q[_r], tag)) --_r;
      return a[_q[_r]] * tag + b[_q[_r]];
    }
    long long ans = 0;
    for (int i = l; i <= r; ++i) {
      chmax(ans, 1ll * a[qwq[i]] * tag + b[qwq[i]]);
    }
    return ans;
  };
  build();
  int x, y;
  for (int i = 1; i <= q; ++i) {
    int opt = Q[i][0];
    x = Q[i][1];
    int l = dfn[x], r = dfn[x] + siz[x] - 1;
    chmax(l, L);
    chmin(r, R);
    if (l > r) continue;
    if (opt == 1) {
      y = Q[i][2];
      Update(l, r, y);
    } else {
      chmax(ans[i], Query(l, r));
    }
  }
}
int main() {
  read(n, q);
  int x;
  for (int i = 2; i <= n; ++i) {
    read(x);
    addedge(x, i);
  }
  for (int i = 1; i <= n; ++i) read(A[i]);
  for (int i = 1; i <= n; ++i) read(B[i]);
  dfs(1, 0, 0, 0);
  for (int i = 1; i <= q; ++i) {
    read(Q[i][0], Q[i][1]);
    if (Q[i][0] == 1) read(Q[i][2]);
  }
  for (int l = 1, r = S; l <= n; l += S, r += S) {
    chmin(r, n);
    solve2(l, r);
  }
  for (int i = 1; i <= n; ++i) val1[i] = -val1[i];
  for (int i = 1; i <= q; ++i) Q[i][2] = -Q[i][2];
  for (int l = 1, r = S; l <= n; l += S, r += S) {
    chmin(r, n);
    solve1(l, r);
  }
  for (int i = 1; i <= q; ++i) {
    if (Q[i][0] == 2) {
      printf("%lld\n", ans[i]);
    }
  }
  return 0;
}