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 oo = 2139063143;
const int N = 1010000;
const int P = 1000000007;
const long double eps = 1e-7;
char buf[1 << 20 | 1], *p1 = buf, *p2 = buf, obuf[1 << 20 | 1], *O = obuf;
template <typename T>
inline void sc(T &x) {
  x = 0;
  static int p;
  p = 1;
  static char c;
  c = (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2)
           ? EOF
           : *p1++);
  while (!isdigit(c)) {
    if (c == '-') p = -1;
    c = (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2)
             ? EOF
             : *p1++);
  }
  while (isdigit(c)) {
    x = (x << 1) + (x << 3) + (c - 48);
    c = (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2)
             ? EOF
             : *p1++);
  }
  x *= p;
}
template <typename T>
inline void print(T x) {
  if (x < 0) putchar('-'), x = -x;
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}
template <typename T>
inline void pr(T x) {
  print(x), putchar('\n');
}
template <typename T1, typename T2>
void chkmax(T1 &A, T2 B) {
  A = A >= B ? A : B;
}
template <typename T1, typename T2>
void chkmin(T1 &A, T2 B) {
  A = A <= B ? A : B;
}
int n, m, a[N], b[N];
vector<int> E[N];
int dfn[N], low[N], ddd[N];
void dfs(int u) {
  ddd[dfn[u] = ++dfn[0]] = u;
  for (int v : E[u]) a[v] += a[u], b[v] += b[u], dfs(v);
  low[u] = dfn[0];
}
struct LY {
  long long k, b;
  int id;
  long long get(long long x) { return k * x + b; }
} f[N];
const int M = 2010;
struct convex {
  vector<LY> id, s;
  long long d;
  bool check(LY fi, LY fj, LY fk) {
    return (long double)(fj.b - fk.b) * (fj.k - fi.k) <=
           (long double)(fi.b - fj.b) * (fk.k - fj.k);
  }
  void ins(LY i) {
    while (s.size() >= 2 && check(s[s.size() - 1 - 1], s[s.size() - 1], i))
      s.pop_back();
    s.push_back(i);
  }
  long long query() {
    int L = 0, R = s.size() - 1;
    while (L + 1 < R) {
      int mid = (L + R) >> 1;
      if (s[mid].get(d) <= s[mid + 1].get(d))
        L = mid;
      else
        R = mid;
    }
    return max(s[L].get(d), s[R].get(d));
  }
  long long query(int l, int r) {
    long long ans = -1e18;
    for (LY f : id)
      if (l <= f.id && f.id <= r) chkmax(ans, f.get(d));
    return ans;
  }
  void ins() {
    s.clear();
    for (LY f : id) ins(f);
  }
  void add(int l, int r, long long d) {
    for (LY &f : id)
      if (l <= f.id && f.id <= r) f.b += f.k * d;
    ins();
  }
  void init(int l, int r) {
    for (int i = l; i <= r; i++) id.push_back(f[i]);
    sort(id.begin(), id.end(), [](LY A, LY B) { return A.k < B.k; });
    ins();
  }
} F[M], G[M];
int L[M], R[M], bel[N];
int main() {
  sc(n), sc(m);
  for (int i = 2; i <= n; i++) {
    int f;
    sc(f);
    E[f].push_back(i);
  }
  for (int i = 1; i <= n; i++) sc(a[i]);
  for (int i = 1; i <= n; i++) sc(b[i]);
  dfs(1);
  const int blo = max(2., sqrt(n / 2));
  for (int i = 1; i <= n; i++) bel[i] = (i - 1) / blo + 1;
  for (int i = 1; i <= bel[n]; i++)
    L[i] = (i - 1) * blo + 1, R[i] = min(i * blo, n);
  for (int i = 1; i <= n; i++) {
    int u = ddd[i];
    b[u] = abs(b[u]);
    f[i].id = i, f[i].k = b[u], f[i].b = (long long)a[u] * b[u];
  }
  for (int i = 1; i <= bel[n]; i++) F[i].init(L[i], R[i]);
  for (int i = 1; i <= n; i++) f[i].b = -f[i].b;
  for (int i = 1; i <= bel[n]; i++) G[i].init(L[i], R[i]);
  while (m--) {
    int op, x, y;
    sc(op), sc(x);
    int l = dfn[x], r = low[x], lb = bel[l], rb = bel[r];
    if (op == 1) {
      sc(y);
      F[lb].add(l, r, y), G[lb].add(l, r, -y);
      if (lb != rb) F[rb].add(l, r, y), G[rb].add(l, r, -y);
      for (int i = lb + 1; i < rb; i++) F[i].d += y, G[i].d -= y;
    } else {
      long long ans = max(F[lb].query(l, r), G[lb].query(l, r));
      if (lb != rb) chkmax(ans, max(F[rb].query(l, r), G[rb].query(l, r)));
      for (int i = lb + 1; i < rb; i++)
        chkmax(ans, max(F[i].query(), G[i].query()));
      pr(ans);
    }
  }
  return 0;
}