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;
struct Line {
  long long k, b;
  int id;
  Line(long long kk = 0, long long bb = 0, int ind = 0) {
    k = kk;
    b = bb;
    id = ind;
  }
  long long getval(long long x) { return k * x + b; }
};
double getpos(const Line& a, const Line& b) {
  return ((double)a.b - (double)b.b) / (b.k - a.k);
}
bool cmp(Line a, Line b) { return a.k < b.k; }
template <typename T>
void Clear(vector<T>& vec) {
  vector<T> tmp;
  swap(tmp, vec);
  return;
}
struct Convex {
  vector<Line> L;
  int pos;
  int siz;
  long long val;
  Convex(int n = 0) {
    pos = 0;
    siz = 0;
    val = 0;
    L.resize(n);
  }
  void clear() {
    pos = 0;
    siz = 0;
    val = 0;
    return;
  }
  void insert(const Line& x) {
    if (siz > 0 && L[siz - 1].k == x.k && L[siz - 1].b >= x.b) return;
    while (siz > 0 && x.b >= L[siz - 1].b) siz--;
    while (siz > 1 && getpos(L[siz - 2], L[siz - 1]) >= getpos(L[siz - 1], x))
      siz--;
    L[siz++] = x;
    return;
  }
  void update(long long x) {
    val += x;
    while (pos < siz - 1 && L[pos].getval(val) < L[pos + 1].getval(val)) pos++;
    return;
  }
  long long curVal() { return L[pos].getval(val); }
};
struct Block {
  vector<Line> vec;
  Convex C;
  int l, r;
  long long curx;
  void build() {
    C.clear();
    for (int i = 0; i < vec.size(); i++) C.insert(vec[i]);
    C.update(0ll);
    return;
  }
  Block(const vector<pair<long long, long long> >& V, int lpos, int rpos) {
    curx = 0ll;
    l = lpos;
    r = rpos;
    C = Convex((r - l + 1) * 2);
    for (int i = l; i <= r; i++)
      vec.push_back(Line(V[i].second, V[i].first * V[i].second, i));
    for (int i = l; i <= r; i++)
      if (V[i].first < 0 || V[i].second < 0)
        vec.push_back(Line(-V[i].second, -V[i].first * V[i].second, i));
    sort(vec.begin(), vec.end(), cmp);
    build();
  }
  void Add(int lpos, int rpos, long long add) {
    if (rpos < l || r < lpos) return;
    if (lpos <= l && r <= rpos) {
      curx += add;
      C.update(add);
      return;
    } else {
      for (int i = 0; i < vec.size(); i++) {
        vec[i].b += vec[i].k * curx;
        if (lpos <= vec[i].id && vec[i].id <= rpos) vec[i].b += vec[i].k * add;
      }
      curx = 0;
      build();
    }
  }
  long long Query(int lpos, int rpos) {
    if (rpos < l || r < lpos) return 0ll;
    if (lpos <= l && r <= rpos)
      return C.curVal();
    else {
      long long ans = 0;
      for (int i = 0; i < vec.size(); i++) {
        if (lpos <= vec[i].id && vec[i].id <= rpos)
          ans = max(ans, vec[i].getval(curx));
      }
      return ans;
    }
  }
};
vector<int> A, B;
vector<pair<long long, long long> > P;
vector<vector<int> > son;
vector<int> dfn, to;
int cur_index;
void dfs(int u, long long sumA, long long sumB) {
  dfn[u] = cur_index++;
  sumA += A[u];
  sumB += B[u];
  P[dfn[u]] = make_pair(sumA, sumB);
  for (int i = 0; i < son[u].size(); i++) dfs(son[u][i], sumA, sumB);
  to[u] = cur_index - 1;
  return;
}
const int M = 200;
vector<Block> O;
int main() {
  int n, q;
  scanf("%d %d", &n, &q);
  P.resize(n);
  son.resize(n);
  dfn.resize(n);
  to.resize(n);
  cur_index = 0;
  for (int i = 1; i < n; i++) {
    int p;
    scanf("%d", &p);
    p--;
    son[p].push_back(i);
  }
  for (int i = 0; i < n; i++) {
    int x;
    scanf("%d", &x);
    A.push_back(x);
  }
  for (int i = 0; i < n; i++) {
    int x;
    scanf("%d", &x);
    B.push_back(x);
  }
  dfs(0, 0ll, 0ll);
  for (int i = 0; i < n; i += M) {
    int j = min(i + M, n) - 1;
    O.push_back(Block(P, i, j));
  }
  while (q--) {
    int opt, v;
    scanf("%d %d", &opt, &v);
    v--;
    if (opt == 1) {
      int x;
      scanf("%d", &x);
      for (int i = 0; i < O.size(); i++) O[i].Add(dfn[v], to[v], x);
    } else {
      long long ans = 0;
      for (int i = 0; i < O.size(); i++)
        ans = max(ans, O[i].Query(dfn[v], to[v]));
      printf("%I64d\n", ans);
    }
  }
  return 0;
}