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;
int read(int &x) { return scanf("%d", &x); }
int read(int &x, int &y) { return scanf("%d%d", &x, &y); }
int read(int &x, int &y, int &z) { return scanf("%d%d%d", &x, &y, &z); }
int read(long long &x) { return scanf("%lld", &x); }
char buff[1000010];
int read(string &s) {
  int r = scanf("%s", buff);
  s = buff;
  return r;
}
template <class E, class G, class Q, class U>
struct SqrtDecomp {
  int GSZ;
  int N;
  vector<G> group;
  vector<U> ups;
  vector<E> elem;
  template <class I>
  SqrtDecomp(const vector<I> &V) : N(V.size()) {
    GSZ = 200;
    for (int i = 0; i < V.size(); ++i) {
      elem.push_back(E(V[i]));
    }
    for (int i = 0, j = 0; i < V.size(); i += GSZ, j++) {
      group.push_back(G(getGroup(j)));
      ups.push_back(U());
    }
  }
  vector<E> getGroup(int i) {
    return vector<E>(elem.begin() + getBegin(i), elem.begin() + getEnd(i) + 1);
  }
  int getBegin(int i) { return i * GSZ; }
  int getEnd(int i) { return min((i + 1) * GSZ, N) - 1; }
  Q query(int l, int r) {
    Q ans = Q();
    for (int i = 0; i < group.size(); ++i) {
      int s = getBegin(i), e = getEnd(i);
      if (e < l || r < s) continue;
      if (l <= s && e <= r) {
        ans = ans + group[i].query();
      } else {
        bool nu = false;
        for (int k = s; k <= e; ++k) {
          assert(0 <= k && k < elem.size());
          nu |= ups[i].applyOne(elem[k]);
          if (l <= k && k <= r) ans = ans + elem[k].query();
        }
        ups[i] = U();
        if (nu) group[i].rebuild(getGroup(i));
      }
    }
    return ans;
  }
  void update(int l, int r, const U &u) {
    for (int i = 0; i < group.size(); ++i) {
      int s = getBegin(i), e = getEnd(i);
      if (e < l || r < s) continue;
      if (l <= s && e <= r) {
        u.applyMany(s, e, group[i]);
        ups[i] += u;
      } else {
        for (int k = s; k <= e; ++k) {
          ups[i].applyOne(elem[k]);
          if (l <= k && k <= r) u.applyOne(elem[k]);
        }
        ups[i] = U();
        group[i].rebuild(getGroup(i));
      }
    }
  }
};
struct Line {
  long long m, b;
  Line(long long m = 0, long long b = 0) : m(m), b(b) {}
  long long query() { return max(b, -b); }
  long long eval(long long x) { return m * x + b; }
  bool pitty(Line l, Line r) {
    long long d0 = (l.b - r.b) / (r.m - l.m);
    long long d1 = (l.b - b) / (m - l.m);
    if (d0 != d1) return d0 <= d1;
    return 1LL * (l.b - r.b - d0 * (m - l.m)) * (m - l.m) <=
           1LL * (l.b - b - d0 * (r.m - l.m)) * (r.m - l.m);
  }
};
struct CHT {
  vector<int> INC, DEC;
  vector<int> INCR, DECR;
  vector<Line> L;
  int x, pi, pd;
  CHT(vector<Line> L) : L(L), x(0), pi(0), pd(0) {
    for (int i = 0; i < L.size(); ++i) {
      INC.push_back(i);
      DEC.push_back(i);
    }
    sort(INC.begin(), INC.end(), [&L](int a, int b) {
      return L[a].m != L[b].m ? L[a].m < L[b].m : (L[a].b < L[b].b);
    });
    sort(DEC.begin(), DEC.end(), [&L](int a, int b) {
      return L[a].m != L[b].m ? L[a].m > L[b].m : (L[a].b > L[b].b);
    });
    INCR = process(INC);
    DECR = process(DEC);
  }
  vector<int> process(vector<int> T) {
    vector<int> R;
    for (int v : T) {
      while (R.size() >= 1 && L[R.back()].m == L[v].m) R.pop_back();
      while (R.size() >= 2 && L[R.back()].pitty(L[R[R.size() - 2]], L[v]))
        R.pop_back();
      R.push_back(v);
    }
    return R;
  }
  void rebuild(vector<Line> L) {
    sort(INC.begin(), INC.end(), [&L](int a, int b) {
      return L[a].m != L[b].m ? L[a].m < L[b].m : (L[a].b < L[b].b);
    });
    sort(DEC.begin(), DEC.end(), [&L](int a, int b) {
      return L[a].m != L[b].m ? L[a].m > L[b].m : (L[a].b > L[b].b);
    });
    this->L = L;
    x = pi = pd = 0;
    INCR = process(INC);
    DECR = process(DEC);
  }
  long long query() {
    while (pi + 1 < INCR.size() &&
           L[INCR[pi]].eval(x) < L[INCR[pi + 1]].eval(x))
      pi++;
    while (pd + 1 < DECR.size() &&
           L[DECR[pd]].eval(x) > L[DECR[pd + 1]].eval(x))
      pd++;
    return max(L[INCR[pi]].eval(x), -L[DECR[pd]].eval(x));
  }
};
struct Add {
  long long v;
  Add(long long v = 0) : v(v) {}
  void applyMany(int b, int e, CHT &s) const { s.x += v; }
  bool applyOne(Line &s) const {
    if (v == 0) return false;
    s.b += s.m * v;
    return true;
  }
  void operator+=(const Add &o) { v += o.v; }
};
struct Max {
  long long v;
  Max(long long v = 0) : v(v) {}
  Max operator+(Max o) { return Max(max(v, o.v)); }
};
vector<pair<int, int> > R;
vector<int> A, B;
vector<long long> SA, SB;
vector<vector<int> > adj;
int idx;
void dfs(int u, int p = -1, long long sa = 0, long long sb = 0) {
  sa += A[u];
  sb += B[u];
  SA[u] = sa;
  SB[u] = sb;
  pair<int, int> r(idx, -1);
  idx++;
  for (int v : adj[u]) {
    if (v == p) continue;
    dfs(v, u, sa, sb);
  }
  r.second = idx - 1;
  R[u] = r;
}
int main() {
  int N, Q;
  read(N, Q);
  A = vector<int>(N);
  B = vector<int>(N);
  adj = vector<vector<int> >(N);
  for (int i = 0; i < N - 1; ++i) {
    int u;
    read(u);
    u--;
    adj[u].push_back(i + 1);
  }
  for (int &v : A) read(v);
  for (int &v : B) read(v);
  SA = vector<long long>(N);
  SB = vector<long long>(N);
  R = vector<pair<int, int> >(N);
  dfs(0);
  vector<Line> T(N);
  for (int i = 0; i < N; ++i) {
    T[R[i].first] = Line(SB[i], 1LL * SA[i] * SB[i]);
  }
  SqrtDecomp<Line, CHT, Max, Add> D(T);
  for (int i = 0; i < Q; ++i) {
    int c;
    read(c);
    if (c == 1) {
      int v, x;
      read(v, x);
      v--;
      D.update(R[v].first, R[v].second, Add(x));
    } else {
      int v;
      read(v);
      v--;
      printf("%lld\n", D.query(R[v].first, R[v].second).v);
    }
  }
  return 0;
}