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 long long INF = 9e18;
const int N = 2e5 + 5, P = 100, CP = N / P + 1;
vector<int> g[N];
long long a[N], b[N];
int w[N], tin[N], tout[N];
int n, q;
vector<pair<long long, long long>> srt[CP];
struct Line {
  long long k, b;
  mutable double lx;
};
struct Hull : vector<Line> {
  long long anime = 0;
  iterator opt;
  bool bad(iterator y) {
    iterator x, z = next(y);
    if (y != begin()) {
      x = prev(y);
      if (x->k == y->k && x->b >= y->b) return true;
    }
    if (z != end() && z->k == y->k && z->b >= y->b) {
      return true;
    }
    if (y == begin() || z == end()) return false;
    return (x->b - y->b) * 1.0 * (z->k - y->k) >=
           (y->b - z->b) * 1.0 * (y->k - x->k);
  }
  void calcLx(iterator y) {
    if (y == begin())
      y->lx = -INF;
    else {
      auto x = prev(y);
      y->lx = (x->b - y->b) / (double)(y->k - x->k);
    }
  }
  void add(Line a) {
    push_back(a);
    if (bad(end() - 1)) {
      pop_back();
      return;
    }
    while (size() > 1 && bad(end() - 2)) erase(end() - 2);
    calcLx(end() - 1);
  }
  long long que() {
    if (empty()) return 0;
    while ((opt + 1) != end() && (opt + 1)->lx <= anime) opt++;
    return opt->k * anime + opt->b;
  }
} cht[CP];
int timer = -1;
void dfs(int node) {
  tin[node] = ++timer;
  w[timer] = node;
  for (int to : g[node]) {
    a[to] += a[node];
    b[to] += b[node];
    dfs(to);
  }
  tout[node] = timer;
}
void rebuild(int p) {
  int l = p * P, r = min(p * P + P, n);
  for (int i = l; i < r; i++) {
    a[w[i]] += cht[p].anime;
  }
  cht[p].clear();
  cht[p].anime = 0;
  for (auto x : srt[p]) {
    cht[p].add({x.first, x.first * a[x.second]});
  }
  cht[p].opt = cht[p].begin();
}
void handle1(int l, int r, int x) {
  int pl = l / P, pr = r / P;
  if (pl == pr) {
    for (int i = l; i <= r; i++) a[w[i]] += x;
    rebuild(pl);
  } else {
    for (int i = l; i < pl * P + P; i++) {
      a[w[i]] += x;
    }
    for (int i = pr * P; i <= r; i++) {
      a[w[i]] += x;
    }
    for (int i = pl + 1; i < pr; i++) {
      cht[i].anime += x;
    }
    rebuild(pl);
    rebuild(pr);
  }
}
long long handle2(int l, int r) {
  int pl = l / P, pr = r / P;
  long long ans = 0;
  if (pl == pr) {
    for (int i = l; i <= r; i++) {
      ans = max(ans, abs(cht[pl].anime + a[w[i]]) * b[w[i]]);
    }
  } else {
    for (int i = l; i < pl * P + P; i++) {
      ans = max(ans, abs(cht[pl].anime + a[w[i]]) * b[w[i]]);
    }
    for (int i = pr * P; i <= r; i++) {
      ans = max(ans, abs(cht[pr].anime + a[w[i]]) * b[w[i]]);
    }
    for (int i = pl + 1; i < pr; i++) {
      ans = max(ans, cht[i].que());
    }
  }
  return ans;
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> q;
  for (int i = 1; i < n; i++) {
    int p;
    cin >> p;
    g[p - 1].push_back(i);
  }
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  for (int i = 0; i < n; i++) {
    cin >> b[i];
  }
  dfs(0);
  for (int i = 0; i < n; i++) {
    b[i] = abs(b[i]);
  }
  for (int i = 0; i < n; i++) {
    int j = w[i];
    if (b[j] != 0) {
      srt[i / P].push_back({b[j], j});
      srt[i / P].push_back({-b[j], j});
    }
  }
  for (int i = 0; i <= (n - 1) / P; i++) {
    sort(srt[i].begin(), srt[i].end());
    rebuild(i);
  }
  while (q--) {
    int type;
    cin >> type;
    if (type == 1) {
      int x, y;
      cin >> x >> y;
      x--;
      handle1(tin[x], tout[x], y);
    } else {
      int x;
      cin >> x;
      x--;
      cout << handle2(tin[x], tout[x]) << "\n";
    }
  }
  return 0;
}