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 N = 200006;
const int M = N << 1;
const int BM = 505;
int n, q, m;
int cnt, head[N], Next[M], v[M];
int a[N], b[N], c[N], d[N];
int clo, pre[N], dfn[N], ver[N];
struct data {
  int x, y;
};
int bm;
void chkmax(long long &x, long long y) {
  if (y > x) x = y;
}
int cmp1(const int &q, const int &w) { return d[q] < d[w]; }
int cmp2(const int &q, const int &w) { return -d[q] < -d[w]; }
struct blo {
  int num[BM], l, r;
  int inc;
  long long x[BM], y[BM];
  int h[BM], t, w;
  long long chk(long long x1, long long y1, long long x2, long long y2) {
    return x1 * y2 - x2 * y1;
  }
  void AddPoint(int i) {
    for (; w - 1 >= t && chk(x[h[w]] - x[h[w - 1]], y[h[w]] - y[h[w - 1]],
                             x[i] - x[h[w]], y[i] - y[h[w]]) >= 0;
         w--)
      ;
    h[++w] = i;
  }
  long long query() {
    for (; w - 1 >= t &&
           x[h[t]] * inc + y[h[t]] <= x[h[t + 1]] * inc + y[h[t + 1]];
         t++)
      ;
    return x[h[t]] * inc + y[h[t]];
  }
  void build() {
    t = 1;
    w = 0;
    assert(r <= n);
    assert(r - l <= m);
    for (int i = (0); i <= (r - l); i++)
      x[i] = d[num[i]], y[i] = 1LL * c[num[i]] * d[num[i]], AddPoint(i);
  }
  void init() {
    assert(r <= n);
    assert(r - l <= m);
    assert(m < BM);
    for (int i = (l); i <= (r); i++) num[i - l] = i;
    sort(num, num + r - l + 1, cmp1);
    build();
  }
} bo[BM];
struct bloo {
  int num[BM], l, r;
  int inc;
  long long x[BM], y[BM];
  int h[BM], t, w;
  long long chk(long long x1, long long y1, long long x2, long long y2) {
    return x1 * y2 - x2 * y1;
  }
  void AddPoint(int i) {
    for (; w - 1 >= t && chk(x[h[w]] - x[h[w - 1]], y[h[w]] - y[h[w - 1]],
                             x[i] - x[h[w]], y[i] - y[h[w]]) >= 0;
         w--)
      ;
    h[++w] = i;
  }
  long long query() {
    for (; w - 1 >= t &&
           x[h[t]] * inc + y[h[t]] <= x[h[t + 1]] * inc + y[h[t + 1]];
         t++)
      ;
    return x[h[t]] * inc + y[h[t]];
  }
  void build() {
    t = 1;
    w = 0;
    assert(r <= n);
    assert(r - l <= m);
    for (int i = (0); i <= (r - l); i++)
      x[i] = -d[num[i]], y[i] = -1LL * c[num[i]] * d[num[i]], AddPoint(i);
  }
  void init() {
    assert(r <= n);
    assert(r - l <= m);
    assert(m < BM);
    for (int i = (l); i <= (r); i++) num[i - l] = i;
    sort(num, num + r - l + 1, cmp2);
    build();
  }
} boo[BM];
void read(int &x) {
  char ch = getchar();
  x = 0;
  int w = 0;
  for (; ch < '0' || ch > '9'; ch = getchar())
    if (ch == '-') w = 1;
  for (; ch >= '0' && ch <= '9'; ch = getchar())
    x = (x << 3) + (x << 1) + ch - '0';
  if (w) x = -x;
}
void add(int x, int y) {
  Next[++cnt] = head[x];
  head[x] = cnt;
  v[cnt] = y;
}
void dfs(int x, int fa) {
  pre[x] = ++clo;
  ver[clo] = x;
  a[x] += a[fa];
  b[x] += b[fa];
  for (int i = head[x]; i; i = Next[i]) dfs(v[i], x);
  dfn[x] = clo;
}
void init() {
  m = sqrt(n);
  for (int i = (1); i <= (n); i++) c[i] = a[ver[i]], d[i] = b[ver[i]];
  bo[0].l = 1;
  bo[0].r = m - 1;
  bm = n / m;
  for (int i = m; i <= n; i += m) bo[i / m].l = i, bo[i / m].r = i + m - 1;
  bo[bm].r = n;
  for (int o = (0); o <= (bm); o++) {
    boo[o].l = bo[o].l;
    boo[o].r = bo[o].r;
    bo[o].init();
    boo[o].init();
  }
}
void incc(int l, int r, int v) {
  if (l / m == r / m) {
    for (int i = (l); i <= (r); i++) c[i] += v;
    bo[l / m].build();
    boo[l / m].build();
    return;
  }
  for (int i = (l), z = bo[l / m].r; i <= z; i++) c[i] += v;
  bo[l / m].build();
  boo[l / m].build();
  for (int i = (bo[r / m].l); i <= (r); i++) c[i] += v;
  bo[r / m].build();
  boo[r / m].build();
  for (int i = (l / m + 1), z = r / m - 1; i <= z; i++)
    bo[i].inc += v, boo[i].inc += v;
}
long long query(int l, int r) {
  long long ans = -1000000000000000000;
  if (l / m == r / m) {
    for (int i = (l); i <= (r); i++)
      chkmax(ans, 1LL * abs(c[i] + bo[l / m].inc) * d[i]);
    return ans;
  }
  for (int i = (l), z = bo[l / m].r; i <= z; i++)
    chkmax(ans, 1LL * abs(c[i] + bo[l / m].inc) * d[i]);
  for (int i = (bo[r / m].l); i <= (r); i++)
    chkmax(ans, 1LL * abs(c[i] + bo[r / m].inc) * d[i]);
  for (int i = (l / m + 1), z = r / m - 1; i <= z; i++)
    chkmax(ans, bo[i].query()), chkmax(ans, boo[i].query());
  return ans;
}
int main() {
  read(n);
  read(q);
  int tp, x, y;
  for (int i = (2); i <= (n); i++) {
    read(x);
    add(x, i);
  }
  for (int i = (1); i <= (n); i++) read(a[i]);
  for (int i = (1); i <= (n); i++) read(b[i]);
  dfs(1, 0);
  for (int i = (1); i <= (n); i++) b[i] = abs(b[i]);
  init();
  while (q--) {
    read(tp);
    read(x);
    if (tp == 1) {
      read(y);
      incc(pre[x], dfn[x], y);
    } else {
      printf("%lld\n", query(pre[x], dfn[x]));
    }
  }
  return 0;
}