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 = 200000 + 10;
int n, q, h[maxn], ecnt, pre[maxn], a[maxn], b[maxn];
struct enode {
  int v, n;
  enode() {}
  enode(int _v, int _n) : v(_v), n(_n) {}
} e[maxn << 1];
inline void addedge(int u, int v) {
  ecnt++;
  e[ecnt] = enode(v, h[u]);
  h[u] = ecnt;
}
long long s1[maxn], s2[maxn];
int dfn[maxn], lst[maxn], tim, tid[maxn];
void dfs(int u, int fa) {
  s1[u] += a[u], s2[u] += b[u];
  tim++;
  dfn[u] = tim;
  tid[tim] = u;
  for (int i = h[u]; ~i; i = e[i].n) {
    int v = e[i].v;
    if (v == fa) continue;
    s1[v] += s1[u];
    s2[v] += s2[u];
    dfs(v, u);
  }
  lst[u] = tim;
}
int bl[maxn], sl[maxn], sr[maxn], SZ;
struct point {
  long long x, y;
  point() {}
  point(long long _x, long long _y) : x(_x), y(_y) {}
  friend point operator-(point a, point b) {
    return point(a.x - b.x, a.y - b.y);
  }
} lis[maxn];
inline bool cmp(point a, point b) {
  if (a.x != b.x) return a.x < b.x;
  return a.y < b.y;
}
inline long long cross(point a, point b) { return a.x * b.y - a.y * b.x; }
struct HULL {
  point a[150 + 5], b[150 + 5];
  int cnt1, cnt2, pos1, pos2;
  long long del;
  inline void init() { del = cnt1 = cnt2 = pos1 = pos2 = 0; }
  inline void ins1(int n) {
    sort(lis + 1, lis + n + 1, cmp);
    a[++cnt1] = lis[1];
    for (int i = 2; i <= n; i++) {
      while (cnt1 > 1 &&
             cross(lis[i] - a[cnt1 - 1], a[cnt1] - a[cnt1 - 1]) <= 0)
        cnt1--;
      a[++cnt1] = lis[i];
    }
    pos1 = 1;
  }
  inline void ins2(int n) {
    sort(lis + 1, lis + n + 1, cmp);
    b[++cnt2] = lis[1];
    for (int i = 2; i <= n; i++) {
      while (cnt2 > 1 &&
             cross(lis[i] - b[cnt2 - 1], b[cnt2] - b[cnt2 - 1]) >= 0)
        cnt2--;
      b[++cnt2] = lis[i];
    }
    pos2 = cnt2;
  }
  inline long long get_val(long long k, point a) { return a.y + k * a.x; }
  inline long long query() {
    long long k = del;
    while (pos1 < cnt1 && get_val(k, a[pos1]) <= get_val(k, a[pos1 + 1]))
      pos1++;
    while (pos2 > 1 && get_val(k, b[pos2]) >= get_val(k, b[pos2 - 1])) pos2--;
    long long now = max(get_val(k, a[pos1]), -get_val(k, b[pos2]));
    return now;
  }
} H[maxn / 150 + 10];
inline void init(int id) {
  H[id].init();
  for (int i = sl[id]; i <= sr[id]; i++) {
    int u = tid[i];
    lis[i - sl[id] + 1] = point(s2[u], s1[u] * s2[u]);
  }
  H[id].ins1(sr[id] - sl[id] + 1);
  H[id].ins2(sr[id] - sl[id] + 1);
}
inline void modify(int x, int l, int r, long long k) {
  for (int i = l; i <= r; i++) {
    int u = tid[i];
    s1[u] += k;
  }
  for (int i = sl[x]; i <= sr[x]; i++) s1[tid[i]] += H[x].del;
  init(x);
}
inline void tag(int x, long long k) { H[x].del += k; }
inline void Updata(int l, int r, long long k) {
  if (bl[l] == bl[r])
    modify(bl[l], l, r, k);
  else {
    int L = bl[l], R = bl[r];
    for (int i = L + 1; i <= R - 1; i++) tag(i, k);
    modify(bl[l], l, sr[bl[l]], k);
    modify(bl[r], sl[bl[r]], r, k);
  }
}
inline void upmax(long long &x, long long y) { x = max(x, y); }
inline long long Abs(long long x) { return (x < 0) ? (-x) : (x); }
inline long long query(int l, int r) {
  long long k = H[bl[l]].del, now = 0;
  for (int i = l; i <= r; i++) {
    int u = tid[i];
    upmax(now, Abs(s1[u] + k) * s2[u]);
  }
  return now;
}
inline void Query(int l, int r) {
  long long Ans = 0;
  if (bl[l] == bl[r])
    upmax(Ans, query(l, r));
  else {
    int L = bl[l], R = bl[r];
    for (int i = L + 1; i <= R - 1; i++) upmax(Ans, H[i].query());
    upmax(Ans, query(l, sr[bl[l]]));
    upmax(Ans, query(sl[bl[r]], r));
  }
  printf("%lld\n", Ans);
}
inline void build() {
  SZ = 150;
  for (int i = 1; i <= n; i++) {
    bl[i] = (i - 1) / SZ + 1;
    if (bl[i] != bl[i - 1]) sl[bl[i]] = i, sr[bl[i - 1]] = i - 1;
  }
  sr[bl[n]] = n;
  for (int i = 1; i <= bl[n]; i++) init(i);
}
int main() {
  scanf("%d%d", &n, &q);
  ecnt = 0;
  memset(h, -1, sizeof(h));
  for (int i = 2; i <= n; i++) {
    scanf("%d", &pre[i]);
    addedge(i, pre[i]);
    addedge(pre[i], i);
  }
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  for (int i = 1; i <= n; i++) scanf("%d", &b[i]);
  tim = 0;
  dfs(1, 0);
  for (int i = 1; i <= n; i++)
    if (s2[i] < 0) s2[i] = -s2[i];
  build();
  for (int i = 1; i <= q; i++) {
    int op, u, x;
    scanf("%d%d", &op, &u);
    if (op == 1) {
      scanf("%d", &x);
      Updata(dfn[u], lst[u], x);
    }
    if (op == 2) Query(dfn[u], lst[u]);
  }
  return 0;
}