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 max_n = 200222;
const long long inf = 2000111222000111222LL;
struct line {
  int k;
  long long b;
  line() {}
  line(int k, long long b) : k(k), b(b) {}
  long long get(int x) const { return 1LL * k * x + b; }
  bool operator<(const line &l) const { return k < l.k || k == l.k && b < l.b; }
};
pair<long long, int> get_intersection(const line &l1, const line &l2) {
  return {l1.b - l2.b, l2.k - l1.k};
}
bool cmp(const pair<long long, int> &a, const pair<long long, int> &b) {
  if (a.first < 0 && b.first < 0) {
    return cmp({-b.first, b.second}, {-a.first, a.second});
  }
  if (a.first < 0) {
    return true;
  }
  if (b.first < 0) {
    return false;
  }
  long long q = a.first / a.second;
  long long w = b.first / b.second;
  if (q != w) {
    return q < w;
  }
  return 1LL * (a.first % a.second) * b.second <
         1LL * (b.first % b.second) * a.second;
}
void add_line(vector<line> &v, const line &l) {
  while (!v.empty()) {
    if (v.back().k == l.k) {
      if (l.b <= v.back().b) {
        return;
      }
      v.pop_back();
      continue;
    }
    if (v.size() == 1) {
      break;
    }
    if (cmp(get_intersection(v[v.size() - 2], l),
            get_intersection(v[v.size() - 2], v.back()))) {
      v.pop_back();
    } else {
      break;
    }
  }
  v.push_back(l);
}
int n, q, a[max_n], b[max_n], na[max_n], nb[max_n];
int l[max_n], r[max_n];
vector<int> g[max_n], order;
line l1[max_n], l2[max_n];
void dfs(int v) {
  l[v] = order.size();
  order.push_back(v);
  for (int to : g[v]) {
    a[to] += a[v];
    b[to] += b[v];
    dfs(to);
  }
  r[v] = order.size() - 1;
}
const int bsize = 233;
const int max_blocks = max_n / bsize + 2;
int num[max_n];
int lb[max_blocks], rb[max_blocks];
void init() {
  for (int i = 0; i < max_blocks; ++i) {
    lb[i] = min(n, i * bsize);
    rb[i] = min(n, (i + 1) * bsize);
    for (int j = lb[i]; j < rb[i]; ++j) {
      num[j] = i;
    }
  }
}
long long get_max_line(const vector<line> &v, int x) {
  int l = -1, r = v.size() - 1;
  while (r - l > 1) {
    int mid = (l + r) / 2;
    if (v[mid].get(x) < v[mid + 1].get(x)) {
      l = mid;
    } else {
      r = mid;
    }
  }
  return v[r].get(x);
}
line *pt;
bool cmp2(int a, int b) { return pt[a] < pt[b]; }
struct sqrt_decomp {
  line ln[max_n];
  int add[max_blocks];
  vector<line> v[max_blocks];
  vector<int> order[max_blocks];
  void init(line l[max_n]) {
    for (int i = 0; i < n; ++i) {
      ln[i] = l[i];
    }
    pt = ln;
    for (int i = 0; i < max_blocks; ++i) {
      for (int j = lb[i]; j < rb[i]; ++j) {
        order[i].push_back(j);
      }
      sort(order[i].begin(), order[i].end(), cmp2);
      rebuild(i);
    }
  }
  void rebuild(int b) {
    if (add[b]) {
      for (int i = lb[b]; i < rb[b]; ++i) {
        ln[i].b += 1LL * ln[i].k * add[b];
      }
      add[b] = 0;
    }
    v[b].clear();
    for (int i : order[b]) {
      add_line(v[b], ln[i]);
    }
  }
  void update(int l, int r, int x) {
    const int n1 = num[l];
    const int n2 = num[r];
    if (n1 == n2) {
      for (int i = l; i <= r; ++i) {
        ln[i].b += 1LL * ln[i].k * x;
      }
      rebuild(n1);
      return;
    }
    for (int i = l; i < rb[n1]; ++i) {
      ln[i].b += 1LL * ln[i].k * x;
    }
    for (int i = lb[n2]; i <= r; ++i) {
      ln[i].b += 1LL * ln[i].k * x;
    }
    rebuild(n1);
    rebuild(n2);
    for (int i = n1 + 1; i < n2; ++i) {
      add[i] += x;
    }
  }
  long long get_max(int l, int r) {
    const int n1 = num[l];
    const int n2 = num[r];
    if (n1 == n2) {
      long long res = -inf;
      for (int i = l; i <= r; ++i) {
        res = max(res, ln[i].get(add[n1]));
      }
      return res;
    }
    long long res = -inf;
    for (int i = l; i < rb[n1]; ++i) {
      res = max(res, ln[i].get(add[n1]));
    }
    for (int i = lb[n2]; i <= r; ++i) {
      res = max(res, ln[i].get(add[n2]));
    }
    for (int i = n1 + 1; i < n2; ++i) {
      res = max(res, get_max_line(v[i], add[i]));
    }
    return res;
  }
};
sqrt_decomp s1, s2;
int main() {
  scanf("%d%d", &n, &q);
  for (int i = 1; i < n; ++i) {
    int p;
    scanf("%d", &p);
    --p;
    g[p].push_back(i);
  }
  for (int i = 0; i < n; ++i) {
    scanf("%d", &a[i]);
  }
  for (int i = 0; i < n; ++i) {
    scanf("%d", &b[i]);
  }
  dfs(0);
  for (int i = 0; i < n; ++i) {
    na[i] = a[order[i]];
    nb[i] = abs(b[order[i]]);
    l1[i] = {-nb[i], -1LL * nb[i] * na[i]};
    l2[i] = {nb[i], 1LL * nb[i] * na[i]};
  }
  init();
  s1.init(l1);
  s2.init(l2);
  while (q--) {
    int tp;
    scanf("%d", &tp);
    if (tp == 1) {
      int v, x;
      scanf("%d%d", &v, &x);
      --v;
      s1.update(l[v], r[v], x);
      s2.update(l[v], r[v], x);
    } else {
      int v;
      scanf("%d", &v);
      --v;
      long long mx = max(s1.get_max(l[v], r[v]), s2.get_max(l[v], r[v]));
      printf("%I64d\n", mx);
    }
  }
  return 0;
}