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 = 400040, bl = 1111, sz = 444;
inline long long read() {
  char ch = getchar();
  long long x = 0, f = 0;
  while (ch < '0' || ch > '9') f |= ch == '-', ch = getchar();
  while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
  return f ? -x : x;
}
struct line {
  long long k, b;
  int id;
  bool operator<(const line &l) const { return k < l.k; }
} vec[bl][sz], hull[bl][sz];
int n, q, el, head[maxn], to[maxn], nxt[maxn], in[maxn], out[maxn], dfs_cnt;
long long apre[maxn], bpre[maxn], a[maxn], b[maxn];
int sq, lft[bl], rig[bl], bel[maxn], at[bl], vl[bl], hl[bl];
long long tag[bl];
inline void add(int u, int v) {
  to[++el] = v;
  nxt[el] = head[u];
  head[u] = el;
}
inline double interx(line l1, line l2) {
  return 1.0 * (l1.b - l2.b) / (l2.k - l1.k);
}
void dfs(int u, int f) {
  apre[u] += apre[f];
  bpre[u] += bpre[f];
  in[u] = ++dfs_cnt;
  a[dfs_cnt] = apre[u];
  b[dfs_cnt] = bpre[u];
  for (int i = head[u]; i; i = nxt[i]) dfs(to[i], u);
  out[u] = dfs_cnt;
}
void move(int id) {
  while (at[id] < hl[id] &&
         interx(hull[id][at[id]], hull[id][at[id] + 1]) <= tag[id])
    at[id]++;
}
void build(int id) {
  hl[id] = 0;
  for (int i = (1); i <= (vl[id]); i++) {
    if (a[vec[id][i].id] >= 0 && vec[id][i].k < 0) continue;
    int tmp;
    bool flag = false;
    while ((tmp = hl[id]) && hull[id][tmp].k == vec[id][i].k) {
      if (hull[id][tmp].b < vec[id][i].b)
        hl[id]--;
      else {
        flag = true;
        break;
      }
    }
    if (flag) continue;
    while ((tmp = hl[id]) > 1 && interx(hull[id][tmp - 1], vec[id][i]) <=
                                     interx(hull[id][tmp - 1], hull[id][tmp]))
      hl[id]--;
    hull[id][++hl[id]] = vec[id][i];
  }
  at[id] = 1;
}
void pushdown(int id) {
  for (int i = (1); i <= (vl[id]); i++) {
    long long k = vec[id][i].k, b = vec[id][i].b;
    vec[id][i] = (line){k, b + k * tag[id], vec[id][i].id};
  }
  for (int i = (lft[id]); i <= (rig[id]); i++) a[i] += tag[id];
  tag[id] = 0;
  at[id] = 1;
}
void init() {
  sq = max(1.0, sqrt(n / 6));
  for (int i = (1); i <= (n); i++) {
    bel[i] = i / sq;
    if (bel[i] != bel[i - 1]) {
      lft[bel[i]] = i;
      if (i != 1) rig[bel[i - 1]] = i - 1;
    }
  }
  rig[bel[n]] = n;
  for (int i = (1); i <= (n); i++) b[i] = abs(b[i]);
  for (int i = (1); i <= (n); i++) {
    vec[bel[i]][++vl[bel[i]]] = (line){b[i], 1ll * a[i] * b[i], i};
    vec[bel[i]][++vl[bel[i]]] = (line){-b[i], -1ll * a[i] * b[i], i};
  }
  for (int i = (bel[1]); i <= (bel[n]); i++) {
    sort(vec[i] + 1, vec[i] + vl[i] + 1);
    build(i);
  }
}
void update_debris(int id, int l, int r, int v) {
  pushdown(id);
  for (int i = (1); i <= (vl[id]); i++) {
    int x = vec[id][i].id;
    if (x >= l && x <= r) vec[id][i].b += vec[id][i].k * v;
  }
  for (int i = (l); i <= (r); i++) a[i] += v;
  build(id);
}
void update(int l, int r, int v) {
  if (bel[l] == bel[r]) return update_debris(bel[l], l, r, v);
  update_debris(bel[l], l, rig[bel[l]], v);
  update_debris(bel[r], lft[bel[r]], r, v);
  for (int i = (bel[l] + 1); i <= (bel[r] - 1); i++) tag[i] += v;
}
long long query_debris(int id, int l, int r) {
  long long ans = 0;
  for (int i = (l); i <= (r); i++) ans = max(ans, abs(a[i] + tag[id]) * b[i]);
  return ans;
}
long long query(int l, int r) {
  if (bel[l] == bel[r]) return query_debris(bel[l], l, r);
  long long ans = max(query_debris(bel[l], l, rig[bel[l]]),
                      query_debris(bel[r], lft[bel[r]], r));
  for (int i = (bel[l] + 1); i <= (bel[r] - 1); i++) {
    move(i);
    long long k = hull[i][at[i]].k, b = hull[i][at[i]].b, x = tag[i];
    ans = max(ans, k * x + b);
  }
  return ans;
}
int main() {
  clock_t st = clock();
  n = read();
  q = read();
  for (int i = (2); i <= (n); i++) add(read(), i);
  for (int i = (1); i <= (n); i++) apre[i] = read();
  for (int i = (1); i <= (n); i++) bpre[i] = read();
  dfs(1, 0);
  init();
  while (q--) {
    int op = read(), x = read();
    if (op == 1)
      update(in[x], out[x], read());
    else
      printf("%lld\n", query(in[x], out[x]));
    if (1.0 * (clock() - st) / CLOCKS_PER_SEC > 4.98) printf("rem %d\n", q);
  }
}