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;
long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); }
const int MAXN = 200000;
const int MAXQ = 100000;
int n, nq;
int par[MAXN];
int ainit[MAXN], binit[MAXN];
int qkind[MAXQ], qidx[MAXQ], qval[MAXQ];
long long qans[MAXQ];
long long asum[MAXN], bsum[MAXN];
vector<int> ch[MAXN];
int pre[MAXN], fstpreidx[MAXN], lstpreidx[MAXN], npre;
int bsz, nb;
vector<int> blazy;
vector<vector<pair<long long, int>>> border;
vector<vector<pair<long long, long long>>> bpos;
vector<int> bposidx;
vector<vector<pair<long long, long long>>> bneg;
vector<int> bnegidx;
vector<long long> bmxneg;
void init(int b) {
  int l = b * bsz, r = min(n, (b + 1) * bsz);
  for (int i = (l); i < (r); ++i)
    border[b].push_back(make_pair(bsum[pre[i]], pre[i]));
  sort(border[b].begin(), border[b].end());
}
long long overtake(const pair<long long, long long> &a,
                   const pair<long long, long long> &b) {
  assert(a.first > b.first);
  assert(a.second < b.second);
  return (b.second - a.second + a.first - b.first - 1) / (a.first - b.first);
}
void append(vector<pair<long long, long long>> &z, long long c, long long d) {
  int nz = ((int)(z).size());
  while (nz >= 1 && z[nz - 1].second <= d) z.pop_back(), --nz;
  if (nz >= 1) assert(c >= z[nz - 1].first);
  if (nz >= 1 && z[nz - 1].first == c) return;
  while (nz >= 1) {
    assert(c > z[nz - 1].first);
    long long t1 = overtake(make_pair(c, d), z[nz - 1]);
    if (nz == 1) {
      if (t1 > 0) break;
    } else {
      long long t2 = overtake(z[nz - 1], z[nz - 2]);
      if (t1 > t2) break;
    }
    z.pop_back(), --nz;
  }
  z.push_back(make_pair(c, d));
}
void push(int b) {
  int l = b * bsz, r = min(n, (b + 1) * bsz);
  for (int i = (l); i < (r); ++i) asum[pre[i]] += blazy[b];
  blazy[b] = 0;
}
void rebuild(int b) {
  int l = b * bsz, r = min(n, (b + 1) * bsz);
  bmxneg[b] = LLONG_MIN;
  bpos[b].clear();
  bposidx[b] = 0;
  for (int _ = (0); _ < (((int)(border[b]).size())); ++_) {
    int at = border[b][_].second;
    if (asum[at] >= 0) {
      long long c = bsum[at], d = asum[at] * bsum[at];
      append(bpos[b], c, d);
    }
  }
  bneg[b].clear();
  bnegidx[b] = 0;
  for (int _ = (0); _ < (((int)(border[b]).size())); ++_) {
    int at = border[b][((int)(border[b]).size()) - _ - 1].second;
    if (asum[at] < 0) {
      bmxneg[b] = max(bmxneg[b], asum[at]);
      long long c = bsum[at], d = -asum[at] * bsum[at];
      append(bneg[b], -c, d);
    }
  }
}
void mod(int l, int r, int by) {
  if (l <= r && l % bsz != 0) {
    int b = l / bsz;
    push(b);
    while (l <= r && l % bsz != 0) {
      asum[pre[l]] += by;
      ++l;
    }
    rebuild(b);
  }
  if (l <= r && r % bsz != bsz - 1) {
    int b = r / bsz;
    push(b);
    while (l <= r && r % bsz != bsz - 1) {
      asum[pre[r]] += by;
      --r;
    }
    rebuild(b);
  }
  if (l <= r) {
    int bl = l / bsz, br = r / bsz;
    for (int b = (bl); b <= (br); ++b) blazy[b] += by;
  }
}
long long eval(const pair<long long, long long> &a, int x) {
  return a.first * x + a.second;
}
long long calc(vector<pair<long long, long long>> &z, int x, int &pos) {
  int nz = ((int)(z).size());
  while (pos + 1 < nz && eval(z[pos + 1], x) > eval(z[pos], x)) ++pos;
  return pos < nz ? eval(z[pos], x) : LLONG_MIN;
}
long long bcalc(int b) {
  if (bmxneg[b] != LLONG_MIN && bmxneg[b] + blazy[b] >= 0) {
    push(b);
    rebuild(b);
  }
  long long ret = LLONG_MIN;
  ret = max(ret, calc(bpos[b], blazy[b], bposidx[b]));
  ret = max(ret, calc(bneg[b], blazy[b], bnegidx[b]));
  return ret;
}
long long calc(int l, int r) {
  long long ret = LLONG_MIN;
  if (l <= r && l % bsz != 0) {
    int b = l / bsz;
    push(b);
    while (l <= r && l % bsz != 0) {
      ret = max(ret, abs(asum[pre[l]]) * bsum[pre[l]]);
      ++l;
    }
    rebuild(b);
  }
  if (l <= r && r % bsz != bsz - 1) {
    int b = r / bsz;
    push(b);
    while (l <= r && r % bsz != bsz - 1) {
      ret = max(ret, abs(asum[pre[r]]) * bsum[pre[r]]);
      --r;
    }
    rebuild(b);
  }
  if (l <= r) {
    int bl = l / bsz, br = r / bsz;
    for (int b = (bl); b <= (br); ++b) ret = max(ret, bcalc(b));
  }
  return ret;
}
void dfsinit(int at) {
  pre[npre] = at, fstpreidx[at] = npre, ++npre;
  for (int i = (0); i < (((int)(ch[at]).size())); ++i) {
    int to = ch[at][i];
    dfsinit(to);
  }
  lstpreidx[at] = npre - 1;
}
void solve() {
  for (int i = (0); i < (n); ++i) {
    asum[i] = ainit[i];
    if (par[i] != -1) asum[i] += asum[par[i]];
  }
  for (int i = (0); i < (n); ++i) {
    bsum[i] = binit[i];
    if (par[i] != -1) bsum[i] += bsum[par[i]];
  }
  for (int i = (0); i < (n); ++i) bsum[i] = abs(bsum[i]);
  for (int i = (0); i < (n); ++i) ch[i].clear();
  for (int i = (0); i < (n); ++i)
    if (par[i] != -1) ch[par[i]].push_back(i);
  npre = 0;
  dfsinit(0);
  assert(npre == n);
  bsz = sqrt(1.0 * n);
  nb = (n + bsz - 1) / bsz;
  blazy = vector<int>(nb, 0);
  border = vector<vector<pair<long long, int>>>(nb);
  bpos = vector<vector<pair<long long, long long>>>(nb);
  bposidx = vector<int>(nb);
  bneg = vector<vector<pair<long long, long long>>>(nb);
  bnegidx = vector<int>(nb);
  bmxneg = vector<long long>(nb);
  for (int b = (0); b < (nb); ++b) init(b), rebuild(b);
  for (int i = (0); i < (nq); ++i) {
    if (qkind[i] == 1) {
      mod(fstpreidx[qidx[i]], lstpreidx[qidx[i]], qval[i]);
    }
    if (qkind[i] == 2) {
      qans[i] = calc(fstpreidx[qidx[i]], lstpreidx[qidx[i]]);
    }
  }
}
void run() {
  scanf("%d%d", &n, &nq);
  par[0] = -1;
  for (int i = (1); i < (n); ++i) scanf("%d", &par[i]), --par[i];
  for (int i = (0); i < (n); ++i) scanf("%d", &ainit[i]);
  for (int i = (0); i < (n); ++i) scanf("%d", &binit[i]);
  for (int i = (0); i < (nq); ++i) {
    scanf("%d", &qkind[i]);
    if (qkind[i] == 1) scanf("%d%d", &qidx[i], &qval[i]), --qidx[i];
    if (qkind[i] == 2) scanf("%d", &qidx[i]), --qidx[i];
  }
  solve();
  for (int i = (0); i < (nq); ++i)
    if (qkind[i] == 2) printf("%lld\n", qans[i]);
}
long long qchk[MAXQ];
long long stupidget(vector<long long> &a, vector<long long> &b, int at,
                    int want, bool seen, long long aa, long long bb) {
  aa += a[at], bb += b[at];
  if (at == want) seen = true;
  long long ret = LLONG_MIN;
  if (seen) ret = max(ret, abs(aa) * abs(bb));
  for (int i = (0); i < (((int)(ch[at]).size())); ++i) {
    int to = ch[at][i];
    ret = max(ret, stupidget(a, b, to, want, seen, aa, bb));
  }
  return ret;
}
void solvestupid() {
  vector<long long> a(n), b(n);
  for (int i = (0); i < (n); ++i) a[i] = ainit[i], b[i] = binit[i];
  for (int i = (0); i < (nq); ++i) {
    if (qkind[i] == 1) {
      a[qidx[i]] += qval[i];
    }
    if (qkind[i] == 2) {
      qchk[i] = stupidget(a, b, 0, qidx[i], false, 0, 0);
    }
  }
}
void stress() {
  int mxn = 10, mxq = 10, mxabsval = 10;
  for (int rep = (0); rep < (1000); ++rep) {
    n = rand() % mxn + 1;
    nq = rand() % mxq + 1;
    par[0] = -1;
    for (int i = (1); i < (n); ++i) par[i] = rand() % i;
    for (int i = (0); i < (n); ++i)
      ainit[i] = rand() % (2 * mxabsval + 1) - mxabsval;
    for (int i = (0); i < (n); ++i)
      binit[i] = rand() % (2 * mxabsval + 1) - mxabsval;
    for (int i = (0); i < (nq); ++i) {
      qkind[i] = rand() % 2 + 1;
      if (qkind[i] == 1) qidx[i] = rand() % n, qval[i] = rand() % mxabsval;
      if (qkind[i] == 2) qidx[i] = rand() % n;
    }
    solve();
    solvestupid();
    bool ok = true;
    for (int i = (0); i < (nq); ++i)
      if (qkind[i] == 2 && qans[i] != qchk[i]) ok = false;
    if (ok) {
      printf(".");
      continue;
    }
    printf("err rep=%d\n", rep);
    printf("%d %d\n", n, nq);
    for (int i = (1); i < (n); ++i) {
      if (i != 1) printf(" ");
      printf("%d", par[i] + 1);
    }
    puts("");
    for (int i = (0); i < (n); ++i) {
      if (i != 0) printf(" ");
      printf("%d", ainit[i]);
    }
    puts("");
    for (int i = (0); i < (n); ++i) {
      if (i != 0) printf(" ");
      printf("%d", binit[i]);
    }
    puts("");
    for (int i = (0); i < (nq); ++i) {
      printf("%d %d", qkind[i], qidx[i] + 1);
      if (qkind[i] == 1) printf(" %d", qval[i]);
      puts("");
    }
    printf("have:");
    for (int i = (0); i < (nq); ++i)
      if (qkind[i] == 2) printf(" %lld", qans[i]);
    puts("");
    printf("want:");
    for (int i = (0); i < (nq); ++i)
      if (qkind[i] == 2) printf(" %lld", qchk[i]);
    puts("");
    break;
  }
}
int main() {
  run();
  return 0;
}