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;
struct Point {
  long long x, y;
  Point() {}
  Point(long long a, long long b) : x(a), y(b) {}
  Point operator-(Point b) { return Point(x - b.x, y - b.y); }
};
inline long double cross(Point x, Point y) {
  return (long double)x.x * y.y - (long double)x.y * y.x;
}
inline long long calc(Point x, long long k) { return x.x * k + x.y; }
int SIZE, n;
int addv[505], minn[505];
int vala[200005], valb[200005];
int id[505][505];
int size1[505], size2[505], pt1[505], pt2[505];
Point hull1[505][505], hull2[505][505];
void rebuild(int x) {
  int l = (x - 1) * SIZE + 1, r = min(n, x * SIZE), len = r - l + 1;
  Point *p = hull1[x], *q = hull2[x];
  int top1 = 0, top2 = 0;
  minn[x] = 0x7f7f7f7f;
  for (int i = 1; i <= len; i++) {
    int u = id[x][i];
    vala[u] += addv[x];
    if (vala[u] >= 0) {
      Point t(valb[u], (long long)vala[u] * valb[u]);
      while (top1 > 1 && cross(t - p[top1], p[top1] - p[top1 - 1]) <= 0) top1--;
      p[++top1] = t;
    } else {
      minn[x] = min(minn[x], -vala[u]);
      Point t(valb[u], -(long long)vala[u] * valb[u]);
      while (top2 > 1 && cross(t - q[top2], q[top2] - q[top2 - 1]) <= 0) top2--;
      q[++top2] = t;
    }
  }
  size1[x] = top1;
  pt1[x] = 1;
  size2[x] = top2;
  pt2[x] = top2;
  addv[x] = 0;
}
long long querybl(int x) {
  int t = addv[x];
  while (pt1[x] < size1[x] &&
         calc(hull1[x][pt1[x]], t) < calc(hull1[x][pt1[x] + 1], t))
    pt1[x]++;
  while (pt2[x] > 1 &&
         calc(hull2[x][pt2[x]], -t) < calc(hull2[x][pt2[x] - 1], -t))
    pt2[x]--;
  long long ans = 0;
  if (size1[x]) ans = max(ans, calc(hull1[x][pt1[x]], t));
  if (size2[x]) ans = max(ans, calc(hull2[x][pt2[x]], -t));
  return ans;
}
void update(int l, int r, int v) {
  int lb = (l - 1) / SIZE + 1, rb = (r - 1) / SIZE + 1;
  if (lb == rb) {
    for (int i = l; i <= r; i++) vala[i] += v;
    rebuild(lb);
  } else {
    int t = min(lb * SIZE, n);
    for (int i = l; i <= t; i++) vala[i] += v;
    rebuild(lb);
    t = (rb - 1) * SIZE + 1;
    for (int i = t; i <= r; i++) vala[i] += v;
    rebuild(rb);
    for (int i = lb + 1; i < rb; i++) {
      addv[i] += v;
      if (minn[i] < addv[i]) rebuild(i);
    }
  }
}
long long query(int l, int r) {
  int lb = (l - 1) / SIZE + 1, rb = (r - 1) / SIZE + 1;
  long long ans = 0;
  if (lb == rb) {
    for (int i = l; i <= r; i++)
      ans = max(ans, (long long)abs(vala[i] + addv[lb]) * valb[i]);
  } else {
    int t = min(lb * SIZE, n);
    for (int i = l; i <= t; i++)
      ans = max(ans, (long long)abs(vala[i] + addv[lb]) * valb[i]);
    t = (rb - 1) * SIZE + 1;
    for (int i = t; i <= r; i++)
      ans = max(ans, (long long)abs(vala[i] + addv[rb]) * valb[i]);
    for (int i = lb + 1; i < rb; i++) ans = max(ans, querybl(i));
  }
  return ans;
}
vector<int> e[200005];
int dfn[200005], end2[200005], dfs_cnt;
int p[200005];
void dfs(int x) {
  dfn[x] = ++dfs_cnt;
  for (int i = 0; i < e[x].size(); i++) dfs(e[x][i]);
  end2[x] = dfs_cnt;
}
bool cmp(int x, int y) { return valb[x] < valb[y]; }
int main() {
  int m;
  scanf("%d%d", &n, &m);
  SIZE = max(1, (int)sqrt(n));
  for (int i = 2; i <= n; i++) {
    scanf("%d", &p[i]);
    e[p[i]].push_back(i);
  }
  dfs(1);
  for (int i = 1; i <= n; i++) {
    int x;
    scanf("%d", &x);
    vala[dfn[i]] = vala[dfn[p[i]]] + x;
  }
  for (int i = 1; i <= n; i++) {
    int x;
    scanf("%d", &x);
    valb[dfn[i]] = valb[dfn[p[i]]] + x;
  }
  for (int i = 1; i <= n; i++) valb[i] = abs(valb[i]);
  for (int i = 1; i <= n; i++) {
    int t = (i - 1) / SIZE + 1;
    id[t][++id[t][0]] = i;
  }
  for (int i = 1; (i - 1) * SIZE < n; i++) {
    sort(id[i] + 1, id[i] + id[i][0] + 1, cmp);
    rebuild(i);
  }
  for (int i = 1; i <= m; i++) {
    int kind;
    scanf("%d", &kind);
    if (kind == 1) {
      int x, y;
      scanf("%d%d", &x, &y);
      update(dfn[x], end2[x], y);
    } else {
      int x;
      scanf("%d", &x);
      printf("%lld\n", query(dfn[x], end2[x]));
    }
  }
  return 0;
}