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 N = 200005, M = 1005, B = 300;
using ll = long long;
int n, q;
vector<int> v[N];
ll a[N], b[N], a2[N], b2[N];
struct Line {
  ll k, b;
  inline ll y(ll x) { return k * x + b; };
};
inline bool worse(const Line &a, const Line &b, const Line &c) {
  return __int128_t(b.b - c.b) * (b.k - a.k) <=
         __int128_t(a.b - b.b) * (c.k - b.k);
}
struct ConvexHull {
  vector<Line> l;
  void ins(Line x) {
    while (l.size() > 1 && worse(l[l.size() - 2], l.back(), x)) l.pop_back();
    l.push_back(x);
  }
  ll query(ll x) {
    if (l.empty()) return LLONG_MIN;
    int lv = 0, rv = l.size() - 1;
    while (lv < rv) {
      int mid = (lv + rv) >> 1;
      if (l[mid].y(x) <= l[mid + 1].y(x))
        lv = mid + 1;
      else
        rv = mid;
    }
    return l[lv].y(x);
  }
  inline void clear() { l.clear(); }
} c[M], cf[M];
int ql[M], qr[M];
ll d[M];
vector<Line> vec;
inline bool cmp(const Line &a, const Line &b) { return a.k < b.k; }
void rebuild(int x) {
  vec.clear();
  c[x].clear();
  cf[x].clear();
  for (int i = ql[x]; i <= qr[x]; i++)
    a[i] += d[x], vec.push_back({b[i], a[i] * b[i]});
  sort(vec.begin(), vec.end(), cmp);
  for (int i = 0; i < int(vec.size()); i++) c[x].ins(vec[i]);
  for (int i = 0; i < int(vec.size()); i++) cf[x].ins({vec[i].k, -vec[i].b});
  d[x] = 0;
}
int idx, dfn[N], sz[N];
void dfs(int pos) {
  dfn[pos] = ++idx;
  sz[pos] = 1;
  for (auto &i : v[pos]) {
    a[i] += a[pos];
    b[i] += b[pos];
    dfs(i);
    sz[pos] += sz[i];
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin >> n >> q;
  int t1;
  for (int i = 2; i <= n; i++) cin >> t1, v[t1].push_back(i);
  for (int i = 1; i <= n; i++) cin >> a[i];
  for (int i = 1; i <= n; i++) cin >> b[i];
  dfs(1);
  memcpy(a2, a, sizeof(a));
  memcpy(b2, b, sizeof(b));
  for (int i = 1; i <= n; i++) a[dfn[i]] = a2[i], b[dfn[i]] = abs(b2[i]);
  int tot = 1;
  while (qr[tot - 1] < n)
    ql[tot] = qr[tot - 1] + 1, qr[tot] = qr[tot - 1] + B, ++tot;
  qr[--tot] = n;
  for (int i = 1; i <= tot; i++) rebuild(i);
  while (q--) {
    int op;
    cin >> op;
    if (op == 1) {
      int p;
      ll x;
      cin >> p >> x;
      int l = dfn[p], r = dfn[p] + sz[p] - 1, lb = (l - 1) / B + 1,
          rb = (r - 1) / B + 1;
      if (lb == rb) {
        for (int i = l; i <= r; i++) a[i] += x;
        rebuild(lb);
        continue;
      }
      for (int i = lb + 1; i < rb; i++) d[i] += x;
      for (int i = l; i <= qr[lb]; i++) a[i] += x;
      for (int i = ql[rb]; i <= r; i++) a[i] += x;
      rebuild(lb);
      rebuild(rb);
      continue;
    }
    int p;
    cin >> p;
    ll ans = LLONG_MIN;
    int l = dfn[p], r = dfn[p] + sz[p] - 1, lb = (l - 1) / B + 1,
        rb = (r - 1) / B + 1;
    if (lb == rb) {
      for (int i = l; i <= r; i++) ans = max(ans, abs(d[lb] + a[i]) * b[i]);
    } else {
      for (int i = lb + 1; i < rb; i++)
        ans = max(ans, c[i].query(d[i])), ans = max(ans, cf[i].query(-d[i]));
      for (int i = l; i <= qr[lb]; i++)
        ans = max(ans, abs(d[lb] + a[i]) * b[i]);
      for (int i = ql[rb]; i <= r; i++)
        ans = max(ans, abs(d[rb] + a[i]) * b[i]);
    }
    cout << ans << '\n';
  }
  return 0;
}