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 f = 1, x = 0;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x * f;
}
int wsta[25], wtp;
template <typename T>
inline void write(T x) {
  if (x < 0) {
    putchar('-');
    x = -x;
  }
  if (x == 0) {
    putchar('0');
    return;
  }
  while (x) wsta[++wtp] = x % 10, x /= 10;
  while (wtp) putchar(wsta[wtp--] + '0');
}
template <typename T>
inline void pr1(T x) {
  write(x);
  putchar(' ');
}
template <typename T>
inline void pr2(T x) {
  write(x);
  putchar('\n');
}
template <typename T>
inline void chkmin(T &x, T y) {
  x = x < y ? x : y;
}
template <typename T>
inline void chkmax(T &x, T y) {
  x = x > y ? x : y;
}
const int MAXN = 200005;
const long long INF = 1e18;
vector<int> nxt[MAXN];
void ins(int x, int y) { nxt[x].emplace_back(y); }
int in[MAXN], ot[MAXN], bel[MAXN], dfn, n, m;
void init_tree(int x) {
  in[x] = ++dfn;
  bel[dfn] = x;
  for (auto y : nxt[x]) init_tree(y);
  ot[x] = dfn;
}
int a[MAXN], b[MAXN], par[MAXN];
struct line {
  long long k, b;
  line() {}
  line(long long _k, long long _b) {
    k = _k;
    b = _b;
  }
  friend line operator+(line u, line v) { return line(u.k + v.k, u.b + v.b); }
  friend line operator-(line u, line v) { return line(u.k - v.k, u.b - v.b); }
  long long gval(long long x) { return k * x + b; }
  void pushx(long long x) { b += k * x; }
};
long long calculate_d(line Z, long long v) {
  if (Z.k == 0) return v < 0 ? 0 : INF;
  if (Z.k > 0) {
    if (v < 0) return 0;
    return v / Z.k + 1;
  } else {
    if (v >= 0) return INF;
    return v / Z.k + 1;
  }
}
struct SegmentTree {
  long long lazy[MAXN * 4], mnd[MAXN * 4];
  line L[MAXN * 4];
  void instag(int now, long long v) {
    lazy[now] += v;
    L[now].pushx(v);
    mnd[now] -= v;
  }
  void pushdown(int now) {
    if (!lazy[now]) return;
    instag((now << 1), lazy[now]);
    instag((now << 1 | 1), lazy[now]);
    lazy[now] = 0;
  }
  void pushup(int now) {
    mnd[now] = min(mnd[(now << 1)], mnd[(now << 1 | 1)]);
    long long c1 = L[(now << 1)].gval(0), c2 = L[(now << 1 | 1)].gval(0);
    if (c1 > c2)
      chkmin(mnd[now], calculate_d(L[(now << 1 | 1)] - L[(now << 1)], c1 - c2)),
          L[now] = L[(now << 1)];
    else if (c1 == c2) {
      long long z1 = calculate_d(L[(now << 1 | 1)] - L[(now << 1)], c1 - c2),
                z2 = calculate_d(L[(now << 1)] - L[(now << 1 | 1)], c2 - c1);
      if (z1 <= z2)
        L[now] = L[(now << 1)];
      else
        L[now] = L[(now << 1 | 1)];
      chkmin(mnd[now], min(z1, z2));
    } else
      chkmin(mnd[now], calculate_d(L[(now << 1)] - L[(now << 1 | 1)], c2 - c1)),
          L[now] = L[(now << 1 | 1)];
  }
  void buildtree(int now, int l, int r) {
    if (l == r) {
      L[now] = line(b[bel[l]], 0);
      L[now].pushx(a[bel[l]]);
      mnd[now] = INF;
      return;
    }
    int mid = (l + r) / 2;
    buildtree((now << 1), l, mid);
    buildtree((now << 1 | 1), mid + 1, r);
    if (l == 4 && r == 5) {
      int k;
      ++k;
    }
    pushup(now);
  }
  void modify(int now, int l, int r, int ql, int qr, long long c) {
    if (l == ql && r == qr && c < mnd[now]) {
      instag(now, c);
      return;
    }
    int mid = (l + r) / 2;
    pushdown(now);
    if (qr <= mid)
      modify((now << 1), l, mid, ql, qr, c);
    else if (mid + 1 <= ql)
      modify((now << 1 | 1), mid + 1, r, ql, qr, c);
    else
      modify((now << 1), l, mid, ql, mid, c),
          modify((now << 1 | 1), mid + 1, r, mid + 1, qr, c);
    pushup(now);
  }
  long long query(int now, int l, int r, int ql, int qr) {
    if (l == ql && r == qr) {
      return L[now].gval(0);
    }
    int mid = (l + r) / 2;
    pushdown(now);
    if (qr <= mid)
      return query((now << 1), l, mid, ql, qr);
    else if (mid + 1 <= ql)
      return query((now << 1 | 1), mid + 1, r, ql, qr);
    else
      return max(query((now << 1), l, mid, ql, mid),
                 query((now << 1 | 1), mid + 1, r, mid + 1, qr));
  }
  void pri(int now, int l, int r) {
    printf("now=%d l=%d r=%d mnd=%lld\n", now, l, r, mnd[now]);
  }
  void print(int now, int l, int r) {
    pri(now, l, r);
    if (l == r) return;
    int mid = (l + r) / 2;
    print((now << 1), l, mid);
    print((now << 1 | 1), mid + 1, r);
  }
} positive, negeitive;
int main() {
  n = read();
  m = read();
  for (int i = 2; i <= n; i++) ins(par[i] = read(), i);
  for (int i = 1; i <= n; i++) a[i] = read();
  for (int i = 1; i <= n; i++) b[i] = read();
  for (int i = 1; i <= n; i++) a[i] += a[par[i]], b[i] += b[par[i]];
  for (int i = 1; i <= n; i++) b[i] = abs(b[i]);
  init_tree(1);
  positive.buildtree(1, 1, n);
  for (int i = 1; i <= n; i++) b[i] = -b[i];
  negeitive.buildtree(1, 1, n);
  for (; m; m--) {
    int o = read(), x = read();
    if (o == 1) {
      int c = read();
      positive.modify(1, 1, n, in[x], ot[x], c);
      negeitive.modify(1, 1, n, in[x], ot[x], c);
    } else {
      long long z1 = positive.query(1, 1, n, in[x], ot[x]);
      long long z2 = negeitive.query(1, 1, n, in[x], ot[x]);
      pr2(max(z1, z2));
    }
  }
  return 0;
}