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 void read(int &x) {
  int v = 0, f = 1;
  char c = getchar();
  while (!isdigit(c) && c != '-') c = getchar();
  if (c == '-')
    f = -1;
  else
    v = (c & 15);
  while (isdigit(c = getchar())) v = (v << 1) + (v << 3) + (c & 15);
  x = v * f;
}
inline void read(long long &x) {
  long long v = 0ll, f = 1ll;
  char c = getchar();
  while (!isdigit(c) && c != '-') c = getchar();
  if (c == '-')
    f = -1;
  else
    v = (c & 15);
  while (isdigit(c = getchar())) v = (v << 1) + (v << 3) + (c & 15);
  x = v * f;
}
inline void readc(char &x) {
  char c;
  while (((c = getchar()) == ' ') || c == '\n')
    ;
  x = c;
}
int n, m, i, j, blk;
int first[200005], ed[200005], ti;
long long tag[1105], ta[200005], tb[200005], a[200005], b[200005];
int ord[200005];
vector<int> e[200005];
bool cmp(int x, int y) { return b[x] < b[y]; }
void dfs(int x) {
  first[x] = ++ti;
  a[ti] = ta[x];
  b[ti] = tb[x];
  for (__typeof((e[x]).begin()) it = (e[x]).begin(); it != (e[x]).end(); it++) {
    ta[*it] = ta[x] + ta[*it];
    tb[*it] = tb[x] + tb[*it];
    dfs(*it);
  }
  ed[x] = ti;
}
struct pnt {
  long long x, y;
};
struct block {
  vector<pnt> v;
  int p;
  void init() {
    v.clear();
    p = 0;
  }
  double slp(pnt x, pnt y) { return 1.0 * (y.y - x.y) / (y.x - x.x); }
  long long calc(pnt x, long long k) { return x.y - k * x.x; }
  void ins(long long a, long long b) {
    while (!v.empty() && v.back().x == a) {
      if (v.back().y >= b) return;
      v.pop_back();
    }
    pnt t = (pnt){a, b};
    while (v.size() > 1 &&
           slp(v[v.size() - 2], v[v.size() - 1]) <= slp(v[v.size() - 1], t)) {
      v.pop_back();
    }
    v.push_back(t);
  }
  long long query(long long k) {
    while (p + 1 < v.size() && calc(v[p], k) < calc(v[p + 1], k)) {
      p++;
    }
    return calc(v[p], k);
  }
} f[1105], g[1105];
void rebuild(int x) {
  int l = max(1, x * blk), r = min(n, x * blk + blk - 1);
  int i;
  for ((i) = (l); (i) <= (r); (i)++) {
    a[i] += tag[x];
  }
  tag[x] = 0;
  f[x].init();
  g[x].init();
  for ((i) = (l); (i) <= (r); (i)++) {
    int t = ord[i];
    f[x].ins(b[t], b[t] * a[t]);
  }
  for ((i) = (r); (i) >= (l); (i)--) {
    int t = ord[i];
    g[x].ins(-b[t], -b[t] * a[t]);
  }
}
void update(int l, int r, int c) {
  if (l / blk == (l - 1) / blk) {
    while (l <= r && l / blk == (l - 1) / blk) {
      a[l] += c;
      l++;
    }
    rebuild((l - 1) / blk);
  }
  if (l > r) return;
  if (r / blk == (r + 1) / blk) {
    while (l <= r && r / blk == (r + 1) / blk) {
      a[r] += c;
      r--;
    }
    rebuild((r + 1) / blk);
  }
  if (l > r) return;
  l /= blk;
  r /= blk;
  while (l <= r) {
    tag[l] += c;
    l++;
  }
}
long long query(int l, int r) {
  long long ans = 0;
  while (l <= r && l / blk == (l - 1) / blk) {
    ans = max(ans, abs((a[l] + tag[l / blk]) * b[l]));
    l++;
  }
  if (l > r) return ans;
  while (l <= r && r / blk == (r + 1) / blk) {
    ans = max(ans, abs((a[r] + tag[r / blk]) * b[r]));
    r--;
  }
  if (l > r) return ans;
  l /= blk;
  r /= blk;
  while (l <= r) {
    ans = max(ans, max(f[l].query(-tag[l]), g[l].query(-tag[l])));
    l++;
  }
  return ans;
}
int main() {
  read(n);
  read(m);
  blk = sqrt(n / 6) + 2;
  for (((i)) = (1); ((i)) <= ((n - 1)); ((i))++) {
    int x;
    read(x);
    e[x].push_back(i + 1);
  }
  for (((i)) = (1); ((i)) <= ((n)); ((i))++) {
    read(ta[i]);
  }
  for (((i)) = (1); ((i)) <= ((n)); ((i))++) {
    read(tb[i]);
  }
  dfs(1);
  for (((i)) = (1); ((i)) <= ((n)); ((i))++) {
    ord[i] = i;
  }
  for (i = 0; i <= n; i += blk) {
    int l = max(i, 1), r = min(i + blk - 1, n);
    sort(ord + l, ord + r + 1, cmp);
  }
  for ((i) = (1 / blk); (i) <= (n / blk); (i)++) {
    rebuild(i);
  }
  while (m--) {
    int op;
    read(op);
    if (op == 1) {
      int x, y;
      read(x);
      read(y);
      update(first[x], ed[x], y);
    } else {
      int x;
      read(x);
      printf("%lld\n", query(first[x], ed[x]));
    }
  }
  return 0;
}