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 = 200005;
long long A[MAXN], B[MAXN];
vector<int> adj[200005];
namespace nstree {
int lcaIter, dfsIter, logn;
vector<int> depth, lcaFir, lcaLas, lcaSeq;
vector<vector<int>> lcaTable;
vector<vector<int>> anc;
vector<int> parent, pre, endpre, siz, seq;
vector<vector<pair<int, int>>> chPost;
void dfs(int x, int p = -1) {
  depth[x] = p == -1 ? 0 : depth[p] + 1;
  if (p != -1) {
    A[x] += A[p];
    B[x] += B[p];
  }
  parent[x] = p;
  lcaFir[x] = lcaIter;
  lcaSeq[lcaIter++] = x;
  seq[dfsIter] = x;
  siz[x] = 1;
  pre[x] = dfsIter++;
  for (auto y : adj[x]) {
    if (y == p) continue;
    dfs(y, x);
    siz[x] += siz[y];
    lcaSeq[lcaIter++] = x;
    chPost[x].emplace_back(lcaLas[y], y);
  }
  lcaLas[x] = lcaIter - 1;
  endpre[x] = dfsIter - 1;
}
int getLca(int a, int b) {
  a = lcaFir[a];
  b = lcaFir[b];
  if (a > b) swap(a, b);
  int p = 31 - __builtin_clz(b - a + 1);
  int x = lcaTable[p][a];
  int y = lcaTable[p][b - (1 << p) + 1];
  return depth[x] < depth[y] ? x : y;
}
void init(int n, int root = 1) {
  depth.resize(n + 1);
  lcaFir.resize(n + 1);
  lcaLas.resize(n + 1);
  parent.resize(n + 1);
  pre.resize(n + 1);
  endpre.resize(n + 1);
  siz.resize(n + 1);
  chPost.clear();
  chPost.resize(n + 1);
  lcaSeq.resize(2 * n - 1);
  seq.resize(n);
  lcaIter = dfsIter = 0;
  logn = 31 - __builtin_clz(n);
  dfs(root);
  assert(lcaIter == 2 * n - 1);
  int lcaLog = 32 - __builtin_clz(2 * n - 1);
  lcaTable.resize(lcaLog);
  lcaTable[0] = lcaSeq;
  for (int p = 1; p < lcaLog; ++p) {
    lcaTable[p].resize(lcaIter - (1 << p) + 1);
    for (int i = 0; i <= lcaIter - (1 << p); ++i) {
      int x = lcaTable[p - 1][i];
      int y = lcaTable[p - 1][i + (1 << (p - 1))];
      lcaTable[p][i] = depth[x] < depth[y] ? x : y;
    }
  }
}
bool isAnc(int a, int b) {
  return lcaFir[a] <= lcaFir[b] && lcaLas[a] >= lcaLas[b];
}
int getChildTowards(int a, int sub) {
  auto it = lower_bound(chPost[a].begin(), chPost[a].end(),
                        make_pair(lcaLas[sub], -1));
  return it->second;
}
};  // namespace nstree
using namespace nstree;
struct FastHull {
  vector<long long> A, B, P;
  int c, qpos;
  FastHull(int n) : c(0), qpos(0), A(n), B(n), P(n) {}
  void clear() { c = qpos = 0; }
  long long monotonicQuery(long long x) {
    qpos = min(qpos, c - 1);
    while (qpos + 1 < c && P[qpos + 1] <= x) ++qpos;
    return A[qpos] * x + B[qpos];
  }
  long long query(long long x) {
    int pos = upper_bound(P.begin(), P.begin() + c, x) - P.begin() - 1;
    return A[pos] * x + B[pos];
  }
  long long divideCeil(long long p, long long q) {
    if (p >= 0) return (p + q - 1) / q;
    return -((-p) / q);
  }
  void insertLine(long long a, long long b) {
    for (; c; --c) {
      if (A[c - 1] == a) {
        if (B[c - 1] >= b) return;
        continue;
      }
      long long pt = divideCeil(B[c - 1] - b, a - A[c - 1]);
      if (pt > P[c - 1]) break;
    }
    P[c] = c ? divideCeil(B[c - 1] - b, a - A[c - 1]) : LLONG_MIN;
    A[c] = a;
    B[c] = b;
    ++c;
  }
};
long long a[MAXN], b[MAXN];
struct Bucket {
  int l, r;
  vector<int> sorted;
  FastHull maxHull, minHull;
  long long x;
  Bucket(int l, int r)
      : l(l),
        r(r),
        x(0),
        maxHull(r - l + 1),
        minHull(r - l + 1),
        sorted(r - l + 1) {
    iota(sorted.begin(), sorted.end(), l);
    sort(sorted.begin(), sorted.end(),
         [&](int i, int j) { return b[i] < b[j]; });
    rebuild();
  }
  void rebuild() {
    maxHull.clear();
    minHull.clear();
    for (int i = l; i <= r; ++i) a[i] += x;
    for (int i = 0; i <= r - l; ++i)
      maxHull.insertLine(b[sorted[i]], a[sorted[i]] * b[sorted[i]]);
    for (int i = r - l; i >= 0; --i)
      minHull.insertLine(-b[sorted[i]], -a[sorted[i]] * b[sorted[i]]);
    x = 0;
  }
};
struct Buckets {
  vector<Bucket> buckets;
  int bsiz;
  Buckets(int n, int bsiz) : bsiz(bsiz) {
    int b = (n + bsiz - 1) / bsiz;
    buckets.reserve(b);
    for (int i = 0; i < b; ++i) {
      buckets.emplace_back(i * bsiz, min(n - 1, (i + 1) * bsiz - 1));
    }
  }
  void run(int l, int r, function<void(Bucket&, int, int)> f,
           function<void(Bucket&)> g) {
    int bl = (l + bsiz - 1) / bsiz;
    int br = (r + 1) / bsiz - 1;
    for (int i = bl; i <= br; ++i) g(buckets[i]);
    if (r <= bl * bsiz - 1) {
      f(buckets[bl - 1], l, r);
    } else {
      if (l <= bl * bsiz - 1) f(buckets[bl - 1], l, bl * bsiz - 1);
      if ((br + 1) * bsiz <= r) f(buckets[br + 1], (br + 1) * bsiz, r);
    }
  }
};
int main() {
  int n, q;
  scanf("%d%d", &n, &q);
  for (int i = 2; i <= n; ++i) {
    int p;
    scanf("%d", &p);
    adj[p].push_back(i);
  }
  for (int i = 1; i <= n; ++i) scanf("%lld", &A[i]);
  for (int i = 1; i <= n; ++i) scanf("%lld", &B[i]);
  init(n);
  for (int i = 0; i < n; ++i) {
    a[i] = A[seq[i]];
    b[i] = B[seq[i]];
  }
  Buckets buckets(n, 450);
  while (q--) {
    int t, v, x;
    scanf("%d%d", &t, &v);
    if (t == 1) {
      scanf("%d", &x);
      buckets.run(
          pre[v], endpre[v],
          [&](Bucket& bucket, int l, int r) {
            for (int i = l; i <= r; ++i) {
              a[i] += x;
            }
            bucket.rebuild();
          },
          [&](Bucket& bucket) { bucket.x += x; });
    } else {
      long long ans = LLONG_MIN;
      buckets.run(
          pre[v], endpre[v],
          [&](Bucket& bucket, int l, int r) {
            for (int i = l; i <= r; ++i) {
              ans = max(ans, abs((a[i] + bucket.x) * b[i]));
            }
          },
          [&](Bucket& bucket) {
            long long mx = bucket.maxHull.query(bucket.x);
            long long mn = bucket.minHull.query(bucket.x);
            ans = max(ans, abs(mx));
            ans = max(ans, abs(mn));
          });
      printf("%lld\n", ans);
    }
  }
}