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;
inline int read() {
  int x = 0, f = 1;
  char ch = getchar();
  for (; !isdigit(ch); ch = getchar()) {
    if (ch == '-') f = -1;
  }
  for (; isdigit(ch); ch = getchar()) {
    x = x * 10 + ch - 48;
  }
  return x * f;
}
const int mxN = 2e5;
const long long INF = 1e10;
int n, q;
struct Edge {
  int v, nxt;
} e[(mxN << 1) + 3];
int fe[mxN + 3];
int fa[mxN + 3];
int dfn[mxN + 3], idfn[mxN + 3];
long long a[mxN + 3], b[mxN + 3];
int sz[mxN + 3];
int en, dfnn;
void addedge(int u, int v) {
  en++;
  e[en].v = v;
  e[en].nxt = fe[u];
  fe[u] = en;
}
void dfs1(int u) {
  dfn[u] = ++dfnn;
  idfn[dfnn] = u;
  sz[u] = 1;
  for (int i = fe[u]; i; i = e[i].nxt) {
    int v = e[i].v;
    if (v == fa[u]) continue;
    b[v] += b[u];
    a[v] += a[u];
    dfs1(v);
    sz[u] += sz[v];
  }
}
struct SegmentTree {
  struct SgTNode {
    long long rst, tag;
    pair<long long, long long> mx;
  } sgt[(mxN << 2) + 3];
  void maketag(int u, long long x) {
    sgt[u].tag += x, sgt[u].rst -= x;
    sgt[u].mx.second += sgt[u].mx.first * x;
  }
  void pushdown(int u) {
    if (sgt[u].tag) {
      maketag(u << 1, sgt[u].tag);
      maketag(u << 1 | 1, sgt[u].tag);
      sgt[u].tag = 0ll;
    }
  }
  long long calc(pair<long long, long long> x, pair<long long, long long> y) {
    return x.first <= y.first
               ? INF
               : (y.second - x.second) / (x.first - y.first) + 1ll;
  }
  void pushup(int u) {
    sgt[u].rst = min(sgt[u << 1].rst, sgt[u << 1 | 1].rst);
    if (sgt[u << 1].mx.second > sgt[u << 1 | 1].mx.second) {
      sgt[u].mx = sgt[u << 1].mx;
      sgt[u].rst = min(sgt[u].rst, calc(sgt[u << 1 | 1].mx, sgt[u << 1].mx));
    } else {
      sgt[u].mx = sgt[u << 1 | 1].mx;
      sgt[u].rst = min(sgt[u].rst, calc(sgt[u << 1].mx, sgt[u << 1 | 1].mx));
    }
  }
  void build(int u, int le, int ri, long long a[], long long b[]) {
    if (le == ri) {
      sgt[u].rst = INF;
      sgt[u].mx = make_pair(b[idfn[le]], a[idfn[le]] * b[idfn[le]]);
      return;
    }
    int mid = (le + ri) >> 1;
    build(u << 1, le, mid, a, b);
    build(u << 1 | 1, mid + 1, ri, a, b);
    pushup(u);
  }
  void add(int u, int le, int ri, int lb, int rb, long long x) {
    if (le >= lb && ri <= rb) {
      maketag(u, x);
      return;
    }
    int mid = (le + ri) >> 1;
    pushdown(u);
    if (lb <= mid) {
      add(u << 1, le, mid, lb, rb, x);
    }
    if (rb > mid) {
      add(u << 1 | 1, mid + 1, ri, lb, rb, x);
    }
    pushup(u);
  }
  void verify(int u) {
    if (sgt[u].rst > 0) return;
    pushdown(u);
    verify(u << 1);
    verify(u << 1 | 1);
    pushup(u);
  }
  long long query(int u, int le, int ri, int lb, int rb) {
    if (le >= lb && ri <= rb) {
      return sgt[u].mx.second;
    }
    int mid = (le + ri) >> 1;
    pushdown(u);
    long long ret = -INF;
    if (lb <= mid) {
      ret = max(ret, query(u << 1, le, mid, lb, rb));
    }
    if (rb > mid) {
      ret = max(ret, query(u << 1 | 1, mid + 1, ri, lb, rb));
    }
    pushup(u);
    return ret;
  }
} sgt1, sgt2;
int main() {
  n = read(), q = read();
  for (int i = 2; i <= n; i++) {
    scanf("%d", &fa[i]);
    addedge(fa[i], i);
  }
  for (int i = 1; i <= n; i++) a[i] = read();
  for (int i = 1; i <= n; i++) b[i] = read();
  dfs1(1);
  for (int i = 1; i <= n; i++) b[i] = abs(b[i]);
  sgt1.build(1, 1, n, a, b);
  for (int i = 1; i <= n; i++) b[i] = -b[i];
  sgt2.build(1, 1, n, a, b);
  while (q--) {
    int opt = read();
    if (opt == 1) {
      int u = read();
      long long x = read();
      sgt1.add(1, 1, n, dfn[u], dfn[u] + sz[u] - 1, x);
      sgt2.add(1, 1, n, dfn[u], dfn[u] + sz[u] - 1, x);
    } else {
      int u = read();
      long long ans1 = sgt1.query(1, 1, n, dfn[u], dfn[u] + sz[u] - 1),
                ans2 = sgt2.query(1, 1, n, dfn[u], dfn[u] + sz[u] - 1);
      printf("%I64d\n", max(ans1, ans2));
    }
    sgt1.verify(1);
    sgt2.verify(1);
  }
  return 0;
}