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;
template <typename T>
std::istream& operator>>(std::istream& i, vector<T>& t) {
  for (auto& v : t) {
    i >> v;
  }
  return i;
}
template <typename T>
bool in(T a, T b, T c) {
  return a <= b && b < c;
}
bool fractionGreaterOrEqual(long double a, long double b, long double c,
                            long double d) {
  return a * d >= b * c;
}
int TOTAL;
namespace LinearEnvelope {
template <typename T>
struct Line {
  T m, b;
  int id;
};
template <typename T>
struct Upper {
  Line<T>* V;
  T t;
  int i, s;
  Upper(int w) : V(new Line<T>[w]), t(0), i(0), s(0) { TOTAL++; }
  ~Upper() { TOTAL--; }
  void clear() {
    i = s = 0;
    t = 0;
  }
  void insert_line(T m, T b, int i = 0) {
    assert(t == 0);
    while (s >= 2 && fractionGreaterOrEqual(V[s - 2].b - V[s - 1].b,
                                            V[s - 1].m - V[s - 2].m,
                                            V[s - 1].b - b, m - V[s - 1].m))
      --s;
    V[s++] = {m, b, i};
  }
  pair<T, int> advance(T first) {
    assert(first >= 0);
    t += first;
    while (i + 1 < s && V[i].m * t + V[i].b < V[i + 1].m * t + V[i + 1].b) ++i;
    return {V[i].m * t + V[i].b, V[i].id};
  }
};
};  // namespace LinearEnvelope
class RPPS {
 public:
  vector<vector<int>> E;
  vector<long long> A, B, RA, RB;
  vector<int> Enter, Exit;
  int T;
  void dfs(int u, long long a, long long b) {
    A[u] += a;
    B[u] += b;
    Enter[u] = T++;
    for (int v : E[u]) dfs(v, A[u], B[u]);
    Exit[u] = T;
  }
  struct Block {
    Block(int L, int R, const vector<long long>& A, const vector<long long>& B)
        : U(2 * (R - L)), L(L), R(R), off(0), cur(0) {
      for (int i = L; i < R; ++i) W.push_back({{B[i], A[i] * B[i]}, i});
      for (int i = L; i < R; ++i)
        if (A[i] < 0 || B[i] < 0) W.push_back({{-B[i], -A[i] * B[i]}, i});
      sort(W.begin(), W.end());
      build();
    }
    void build() {
      U.clear();
      for (auto& w : W) U.insert_line(w.first.first, w.first.second);
      cur = U.advance(0LL).first;
    }
    void add(int l, int r, long long first) {
      if (l >= R || r <= L)
        return;
      else if (l <= L && r >= R) {
        cur = U.advance(first).first;
        off += first;
      } else {
        for (auto& w : W) {
          w.first.second += w.first.first * off;
          if (in(l, w.second, r)) {
            w.first.second += w.first.first * first;
          }
        }
        off = 0;
        build();
      }
    }
    long long get(int l, int r) {
      if (l >= R || r <= L)
        return numeric_limits<long long>::min();
      else if (l <= L && r >= R)
        return cur;
      else {
        long long ans = numeric_limits<long long>::min();
        for (auto& w : W) {
          if (in(l, w.second, r)) {
            ans = max(ans, w.first.first * off + w.first.second);
          }
        }
        return ans;
      }
    }
    LinearEnvelope::Upper<long long> U;
    vector<pair<pair<long long, long long>, int>> W;
    int L, R;
    long long off, cur;
  };
  void solve(istream& cin, ostream& cout) {
    TOTAL = 0;
    int N, Q;
    cin >> N >> Q;
    E.resize(N);
    A.resize(N);
    B.resize(N);
    RA.resize(N);
    RB.resize(N);
    Enter.resize(N);
    Exit.resize(N);
    for (int i = 1; i < N; ++i) {
      int p;
      cin >> p;
      --p;
      E[p].push_back(i);
    }
    cin >> A >> B;
    T = 0;
    dfs(0, 0, 0);
    for (int i = 0; i < N; ++i) {
      RA[Enter[i]] = A[i];
      RB[Enter[i]] = B[i];
    }
    int BS = max(1, (int)sqrt(N / 6));
    vector<Block> D;
    D.reserve(1 + (N - 1) / BS);
    for (int i = 0; i < N; i += BS) D.emplace_back(i, min(i + BS, N), RA, RB);
    long long diff = 0;
    for (int q = 0; q < Q; ++q) {
      int t, v;
      cin >> t >> v;
      --v;
      if (t == 1) {
        long long first;
        cin >> first;
        for (Block& b : D) b.add(Enter[v], Exit[v], first);
      } else {
        long long ans = numeric_limits<long long>::min();
        for (Block& b : D) ans = max(ans, b.get(Enter[v], Exit[v]));
        cout << ans << '\n';
      }
    }
  }
};
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  RPPS solver;
  std::istream& in(std::cin);
  std::ostream& out(std::cout);
  solver.solve(in, out);
  return 0;
}