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 mod = 1000000007;
const long long INF = mod * mod;
const long double eps = 1e-8;
struct CHT {
  vector<pair<long long, long long>> v;
  int l;
  bool check(pair<long long, long long> a, pair<long long, long long> b,
             pair<long long, long long> c) {
    return (b.first - a.first) * (c.second - b.second) >=
           (b.second - a.second) * (c.first - b.first);
  }
  void build(vector<pair<long long, long long>> a) {
    v.clear();
    l = 0;
    l = 0;
    for (int i = (int)a.size() - 1; i >= 0; i--) {
      while (v.size() >= 2 && check(v[v.size() - 2], v[v.size() - 1], a[i]))
        v.pop_back();
      v.push_back(a[i]);
    }
  }
  long long f(pair<long long, long long> a, long long x) {
    return a.first * x + a.second;
  }
  long long query(long long x) {
    while (l + 1 < v.size() && f(v[l], x) > f(v[l + 1], x)) l++;
    return f(v[l], x);
  }
};
vector<int> G[1 << 18];
int ri[1 << 18];
int trans[1 << 18];
int cur = 0;
long long coef[1 << 18];
long long ori[1 << 18];
long long a[1 << 18], b[1 << 18];
vector<CHT> v, lv;
long long ad[1000] = {};
void dfs(int id, long long aval, long long bval) {
  aval += a[id];
  bval += b[id];
  coef[cur] = abs(bval);
  ori[cur] = aval;
  trans[id] = cur;
  cur++;
  for (int j = 0; j < G[id].size(); j++) {
    int to = G[id][j];
    dfs(to, aval, bval);
  }
  ri[trans[id]] = cur;
}
vector<vector<int>> ord;
void solve() {
  int n, q;
  cin >> n >> q;
  for (int i = 1; i <= n - 1; i++) {
    int a;
    cin >> a;
    a--;
    G[a].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, 0, 0);
  int k = sqrt(n);
  int d = (n + k - 1) / k;
  v.resize(d);
  lv.resize(d);
  ord.resize(d);
  for (int i = 0; i < d; i++) {
    vector<pair<long long, long long>> u, lu;
    for (int j = k * i; j < min(n, k * (i + 1)); j++) {
      ori[j] *= coef[j];
      u.push_back({coef[j], ori[j]});
      lu.push_back({-coef[j], -ori[j]});
    }
    {
      vector<pair<long long, long long>> v;
      for (int j = k * i; j < min(n, k * (i + 1)); j++) {
        v.push_back({coef[j], j});
      }
      sort(v.begin(), v.end());
      for (int j = 0; j < v.size(); j++) {
        ord[i].push_back(v[j].second);
      }
    }
    sort(u.begin(), u.end());
    sort(lu.begin(), lu.end());
    v[i].build(u);
    lv[i].build(lu);
  }
  for (int i = 0; i < q; i++) {
    int t;
    cin >> t;
    if (t == 1) {
      int loc, x;
      cin >> loc >> x;
      loc = trans[loc - 1];
      int lid = loc / k;
      int rid = (ri[loc] - 1) / k;
      if (lid == rid) {
        vector<pair<long long, long long>> nw, lnw;
        for (int id = 0; id < ord[lid].size(); id++) {
          int j = ord[lid][id];
          if (loc <= j && j < ri[loc]) {
            ori[j] += (ad[lid] + x) * coef[j];
          } else {
            ori[j] += ad[lid] * coef[j];
          }
          nw.push_back({coef[j], ori[j]});
          lnw.push_back({-coef[j], -ori[j]});
        }
        reverse(lnw.begin(), lnw.end());
        ad[lid] = 0;
        v[lid].build(nw);
        lv[lid].build(lnw);
      } else {
        {
          vector<pair<long long, long long>> nw, lnw;
          for (int id = 0; id < ord[lid].size(); id++) {
            int j = ord[lid][id];
            if (loc <= j) {
              ori[j] += (ad[lid] + x) * coef[j];
            } else {
              ori[j] += ad[lid] * coef[j];
            }
            nw.push_back({coef[j], ori[j]});
            lnw.push_back({-coef[j], -ori[j]});
          }
          reverse(lnw.begin(), lnw.end());
          ad[lid] = 0;
          v[lid].build(nw);
          lv[lid].build(lnw);
        }
        {
          vector<pair<long long, long long>> nw, lnw;
          for (int id = 0; id < ord[rid].size(); id++) {
            int j = ord[rid][id];
            if (j < ri[loc]) {
              ori[j] += (ad[rid] + x) * coef[j];
            } else {
              ori[j] += ad[rid] * coef[j];
            }
            nw.push_back({coef[j], ori[j]});
            lnw.push_back({-coef[j], -ori[j]});
          }
          reverse(lnw.begin(), lnw.end());
          ad[rid] = 0;
          v[rid].build(nw);
          lv[rid].build(lnw);
        }
        for (int j = lid + 1; j <= rid - 1; j++) ad[j] += x;
      }
    } else {
      int loc;
      cin >> loc;
      loc = trans[loc - 1];
      int lid = loc / k;
      int rid = (ri[loc] - 1) / k;
      long long ans = 0;
      if (lid == rid) {
        for (int j = loc; j < ri[loc]; j++) {
          ans = max(ans, abs(ad[lid] * coef[j] + ori[j]));
        }
      } else {
        for (int j = loc; j < (lid + 1) * k; j++) {
          ans = max(ans, abs(ad[lid] * coef[j] + ori[j]));
        }
        for (int j = rid * k; j < ri[loc]; j++) {
          ans = max(ans, abs(ad[rid] * coef[j] + ori[j]));
        }
        for (int j = lid + 1; j <= rid - 1; j++) {
          long long c = v[j].query(ad[j]);
          long long d = lv[j].query(ad[j]);
          ans = max({ans, abs(c), abs(d)});
        }
      }
      cout << ans << endl;
    }
  }
}
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  solve();
  return 0;
}