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 maxn = 2e5 + 14, sq = 530, inf = 1e9;
struct Line {
  int m;
  long long b;
};
struct ConvexHull {
  vector<Line> v;
  vector<pair<long long, int> > event;
  int lazy, ptr, cnt;
  void clear() {
    v = vector<Line>();
    event = vector<pair<long long, int> >();
    ptr = lazy = cnt = 0;
  }
  long long when(int i, int j) {
    return (v[i].b - v[j].b + v[j].m - v[i].m - 1) / (v[j].m - v[i].m);
  }
  long long val(int i, int x) { return (long long)x * v[i].m + v[i].b; }
  void build() {
    event.reserve(v.size());
    for (int i = 0; i < v.size(); i++) {
      if (event.size() && v[event.back().second].m == v[i].m)
        if (v[i].b >= v[event.back().second].b)
          event.pop_back();
        else
          continue;
      while (event.size() > 1 &&
             when(event.back().second, i) <= event.back().first)
        event.pop_back();
      event.emplace_back(event.empty() ? -inf : when(event.back().second, i),
                         i);
    }
  }
  long long get() {
    while (ptr < event.size() - 1 && event[ptr + 1].first <= lazy) ptr++;
    return val(event[ptr].second, lazy);
  }
} conv[maxn];
int n, q, b[maxn], p[maxn], a[maxn], sa[maxn], qv[maxn], qt[maxn], qx[maxn],
    myRoot[maxn], byB[maxn];
bool mark[maxn];
vector<int> g[maxn], c[maxn];
void add(int v, int x) {
  conv[v].lazy += x;
  for (auto &u : c[v]) add(u, x);
}
long long get(int v) {
  long long ans = conv[v].get();
  for (auto &u : c[v]) ans = max(ans, get(u));
  return ans;
}
void goAdd(int root, int v) {
  if (root != v && mark[v]) {
    c[root].push_back(v);
    return;
  }
  myRoot[v] = root;
  for (auto &u : g[v]) goAdd(root, u);
}
void build(int v = 0) {
  for (auto &u : g[v]) build(u);
  if (mark[v]) goAdd(v, v);
}
int main() {
  scanf("%d%d", &n, &q);
  for (int i = 1; i < n; i++) {
    scanf("%d", &p[i]);
    p[i]--;
    g[p[i]].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]);
    if (i) b[i] += b[p[i]];
  }
  for (int i = 0; i < n; i++) b[i] = abs(b[i]);
  iota(byB, byB + n, 0);
  sort(byB, byB + n, [](int i, int j) { return b[i] < b[j]; });
  for (int l = 0, r = 0; l < q; l = r) {
    memset(myRoot, -1, sizeof myRoot);
    int cntu = 0, cntg = 0;
    for (int &i = r; i < q; i++) {
      if (cntu + cntg > sq) break;
      scanf("%d%d", &qt[i], &qv[i]);
      qv[i]--;
      if (qt[i] == 1) {
        scanf("%d", &qx[i]);
        cntu += !mark[qv[i]];
        mark[qv[i]] = 1;
      } else {
        cntg += !mark[qv[i]];
        mark[qv[i]] = 1;
      }
    }
    sa[0] = a[0];
    for (int i = 1; i < n; i++) sa[i] = sa[p[i]] + a[i];
    build();
    for (int i = 0; i < n; i++) {
      int v = byB[i];
      if (myRoot[v] != -1)
        if (sa[v] < 0)
          conv[myRoot[v]].cnt += 2;
        else
          conv[myRoot[v]].cnt++;
    }
    for_each(qv + l, qv + r, [](int &v) { conv[v].v.reserve(conv[v].cnt); });
    for (int i = n - 1; i >= 0; i--) {
      int v = byB[i];
      if (myRoot[v] != -1)
        if (sa[v] < 0)
          conv[myRoot[v]].v.push_back({-b[v], (long long)-sa[v] * b[v]});
    }
    for (int i = 0; i < n; i++) {
      int v = byB[i];
      if (myRoot[v] != -1)
        if (sa[v] < 0)
          conv[myRoot[v]].v.push_back({b[v], (long long)sa[v] * b[v]});
        else
          conv[myRoot[v]].v.push_back({b[v], (long long)sa[v] * b[v]});
    }
    for_each(qv + l, qv + r, [](int &v) {
      if (conv[v].event.empty()) conv[v].build();
    });
    for (int i = l; i < r; i++) {
      if (qt[i] == 1) {
        a[qv[i]] += qx[i];
        add(qv[i], qx[i]);
      } else
        printf("%lld ", get(qv[i]));
    }
    for_each(qv + l, qv + r, [](int &v) {
      mark[v] = 0;
      conv[v].clear();
      c[v].clear();
    });
  }
}