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>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
using namespace std;
template <typename _T>
inline void read(_T &f) {
  f = 0;
  _T fu = 1;
  char c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') fu = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    f = (f << 3) + (f << 1) + (c & 15);
    c = getchar();
  }
  f *= fu;
}
template <typename T>
void print(T x) {
  if (x < 0) putchar('-'), x = -x;
  if (x < 10)
    putchar(x + 48);
  else
    print(x / 10), putchar(x % 10 + 48);
}
template <typename T>
void print(T x, char t) {
  print(x);
  putchar(t);
}
const long long INF = 0x7fffffffffffffff;
const int N = 2e5 + 5, sqr = 100, ct = N / sqr;
const double eps = 1e-8;
struct ele {
  int a, b, id;
  ele(int aa = 0, int bb = 0, int c = 0) : a(aa), b(bb), id(c) {}
  bool operator<(const ele A) const { return b < A.b; }
} p[ct + 5][sqr + 5], p2[ct + 5][sqr + 5], st[ct + 5][sqr + 5],
    st2[ct + 5][sqr + 5];
vector<int> adj[N];
int a[N], b[N], fa[N], tops[N], pre[N], siz[N], B[N], l[N], r[N], tag[ct + 5],
    now[ct + 5], now2[ct + 5], top[ct + 5], top2[ct + 5];
int n, m, cnt;
void dfs1(int u) {
  tops[u] = ++cnt;
  pre[cnt] = u;
  siz[u] = 1;
  for (register int i = 0; i < (int)adj[u].size(); i++) {
    int v = adj[u][i];
    a[v] += a[u];
    b[v] += b[u];
    dfs1(v);
    siz[u] += siz[v];
  }
}
double slope(ele a, ele b) {
  return (double)(1ll * a.a * a.b - 1ll * b.a * b.b) / (b.b - a.b);
}
void build(int id) {
  top[id] = 0;
  for (register int i = 1; i <= r[id] - l[id] + 1; i++) {
    p[id][i].a += tag[id];
    if (top[id] && st[id][top[id]].b == p[id][i].b) {
      if (1ll * st[id][top[id]].a * st[id][top[id]].b >=
          1ll * p[id][i].a * p[id][i].b)
        continue;
      else
        --top[id];
    }
    while (top[id] && 1ll * st[id][top[id]].a * st[id][top[id]].b <=
                          1ll * p[id][i].a * p[id][i].b)
      --top[id];
    while (top[id] >= 2 && slope(st[id][top[id] - 1], st[id][top[id]]) + eps >
                               slope(st[id][top[id]], p[id][i]))
      --top[id];
    st[id][++top[id]] = p[id][i];
  }
  now[id] = 1;
  top2[id] = 0;
  for (register int i = 1; i <= r[id] - l[id] + 1; i++) {
    p2[id][i].a += tag[id];
    if (top2[id] && st2[id][top2[id]].b == p2[id][i].b) {
      if (1ll * st2[id][top2[id]].a * st2[id][top2[id]].b >=
          1ll * p2[id][i].a * p2[id][i].b)
        continue;
      else
        --top2[id];
    }
    while (top2[id] && 1ll * st2[id][top2[id]].a * st2[id][top2[id]].b <=
                           1ll * p2[id][i].a * p2[id][i].b)
      --top2[id];
    while (top2[id] >= 2 &&
           slope(st2[id][top2[id] - 1], st2[id][top2[id]]) + eps >
               slope(st2[id][top2[id]], p2[id][i]))
      --top2[id];
    st2[id][++top2[id]] = p2[id][i];
  }
  tag[id] = 0;
  now2[id] = 1;
}
long long solve(int id) {
  while (now[id] < top[id] &&
         1ll * (st[id][now[id]].a + tag[id]) * st[id][now[id]].b <=
             1ll * (st[id][now[id] + 1].a + tag[id]) * st[id][now[id] + 1].b)
    ++now[id];
  while (now2[id] < top2[id] &&
         1ll * (st2[id][now2[id]].a + tag[id]) * st2[id][now2[id]].b <=
             1ll * (st2[id][now2[id] + 1].a + tag[id]) *
                 st2[id][now2[id] + 1].b)
    ++now2[id];
  return max(1ll * (st[id][now[id]].a + tag[id]) * st[id][now[id]].b,
             1ll * (st2[id][now2[id]].a + tag[id]) * st2[id][now2[id]].b);
}
void add(int l, int r, int x) {
  int b = B[l];
  for (register int i = 1; i <= ::r[b] - ::l[b] + 1; i++) {
    if (l <= p[b][i].id && p[b][i].id <= r) {
      p[b][i].a += x;
    }
    if (l <= p2[b][i].id && p2[b][i].id <= r) {
      p2[b][i].a += x;
    }
  }
  build(b);
}
long long qry(int l, int r) {
  long long ans = -INF, b = B[l];
  for (register int i = 1; i <= ::r[b] - ::l[b] + 1; i++) {
    if (l <= p[b][i].id && p[b][i].id <= r) {
      ans = max(ans, 1ll * (p[b][i].a + tag[b]) * p[b][i].b);
    }
    if (l <= p2[b][i].id && p2[b][i].id <= r) {
      ans = max(ans, 1ll * (p2[b][i].a + tag[b]) * p2[b][i].b);
    }
  }
  return ans;
}
long long query(int l, int r) {
  if (B[l] == B[r]) return qry(l, r);
  long long ans = max(qry(l, ::r[B[l]]), qry(::l[B[r]], r));
  for (register int i = B[l] + 1; i <= B[r] - 1; i++) ans = max(ans, solve(i));
  return ans;
}
int main() {
  read(n);
  read(m);
  for (register int i = 2; i <= n; i++) read(fa[i]), adj[fa[i]].push_back(i);
  for (register int i = 1; i <= n; i++) read(a[i]);
  for (register int i = 1; i <= n; i++) read(b[i]);
  dfs1(1);
  for (register int i = 1; i <= n; i++) {
    int u = pre[i];
    B[i] = (i - 1) / sqr + 1;
    if (!l[B[i]]) l[B[i]] = i;
    r[B[i]] = i;
    p[B[i]][i - l[B[i]] + 1] = ele(a[u], b[u], i);
    p2[B[i]][i - l[B[i]] + 1] = ele(a[u], -b[u], i);
  }
  for (register int i = 1; i <= B[n]; i++)
    sort(p[i] + 1, p[i] + r[i] - l[i] + 1 + 1),
        sort(p2[i] + 1, p2[i] + r[i] - l[i] + 1 + 1), build(i);
  while (m--) {
    int opt;
    read(opt);
    if (opt == 1) {
      int x, y;
      read(x);
      read(y);
      int L = tops[x], R = tops[x] + siz[x] - 1;
      if (B[L] == B[R])
        add(L, R, y);
      else {
        add(L, r[B[L]], y);
        add(l[B[R]], R, y);
        for (register int i = B[L] + 1; i <= B[R] - 1; i++) tag[i] += y;
      }
    }
    if (opt == 2) {
      int x;
      read(x);
      print(query(tops[x], tops[x] + siz[x] - 1), '\n');
    }
  }
  return 0;
}