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 = 2e5 + 20;
const int oo = 1e9 + 20;
const int MOD = 1e9 + 7;
vector<vector<int>> g;
long long a[N], b[N];
int from[N], to[N], t;
bool fractionGreaterOrEqual(double a, double b, double c, double d) {
  return a / b >= c / d;
}
int TOTAL;
const int MX = 200005, SQ = 450;
bool leq(double a, double b, double c, double d) { return a / b <= c / d; }
struct CHT {
  long long m[2 * SQ + 5], y[2 * SQ + 5];
  int s, i;
  CHT() : s(0), i(0) {}
  void add(long long a, long long b) {
    if (s > 0 && a == m[s - 1] && b <= y[s - 1]) return;
    while (s > 0 && ((y[s - 1] < b) || (y[s - 1] == b && m[s - 1] < a))) s--;
    while (s >= 2) {
      if (leq(y[s - 1] - b, a - m[s - 1], y[s - 2] - y[s - 1],
              m[s - 1] - m[s - 2]))
        s--;
      else
        break;
    }
    m[s] = a, y[s] = b;
    s++;
  }
  long long get_max(long long x) {
    while (i + 1 < s && m[i + 1] * x + y[i + 1] >= m[i] * x + y[i]) i++;
    return m[i] * x + y[i];
  }
  void clear() {
    s = 0;
    i = 0;
  }
};
int order[N];
struct bucket {
  int l, r;
  long long x;
  bool ordered;
  CHT ds;
  bucket(int l, int r) : l(l), r(r), x(0), ordered(0) {}
  void build() {
    if (!ordered)
      sort(order + l, order + r + 1, [](int i, int j) { return b[i] < b[j]; });
    ordered = 1;
    for (int i = l; i <= r; i++) a[i] += x;
    ds.clear();
    for (int i = r; i >= l; i--) {
      int I = order[i];
      ds.add(-b[I], -a[I] * b[I]);
    }
    for (int i = l; i <= r; i++) {
      int I = order[i];
      ds.add(b[I], a[I] * b[I]);
    }
    x = 0;
  }
  void update(int L, int R, long long v) {
    if (L == l && R == r)
      x += v;
    else {
      for (int i = L; i <= R; i++) a[i] += v;
      build();
    }
  }
  long long query(int L, int R) {
    if (L == l && R == r) return ds.get_max(x);
    long long ans = LLONG_MIN;
    for (int i = L; i <= R; i++) {
      ans = max(ans, abs(a[i] + x) * b[i]);
    }
    return ans;
  }
};
long long A[N], B[N];
void dfs(int u, long long suma = 0, long long sumb = 0) {
  from[u] = t++;
  a[from[u]] = A[u] + suma;
  b[from[u]] = abs(B[u] + sumb);
  for (int v : g[u]) {
    dfs(v, suma + A[u], sumb + B[u]);
  }
  to[u] = t - 1;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n, q;
  while (cin >> n >> q) {
    g.assign(n + 1, {});
    iota(order, order + n, 0);
    for (int i = 1; i < n; i++) {
      int pi;
      cin >> pi;
      pi--;
      g[pi].push_back(i);
    }
    for (int i = 0; i < n; i++) cin >> A[i];
    for (int i = 0; i < n; i++) cin >> B[i];
    dfs(0);
    int len = sqrt(n);
    vector<bucket> ds;
    int n_bucket = (n + len - 1) / len;
    for (int i = 0; i < n_bucket; i++) {
      ds.push_back({i * len, min(n - 1, (i + 1) * len - 1)});
      ds.back().build();
    }
    while (q--) {
      int cmd, u;
      cin >> cmd >> u;
      u--;
      int l = from[u] / len, r = to[u] / len;
      assert(l < n && r < n);
      if (cmd == 1) {
        int x;
        cin >> x;
        if (l == r)
          ds[l].update(from[u], to[u], x);
        else {
          ds[l].update(from[u], (l + 1) * len - 1, x);
          for (int i = l + 1; i < r; i++) {
            ds[i].update(i * len, (i + 1) * len - 1, x);
          }
          ds[r].update(r * len, to[u], x);
        }
      } else {
        if (l == r)
          cout << ds[l].query(from[u], to[u]) << '\n';
        else {
          long long ans = LLONG_MIN;
          ans = max(ans, ds[l].query(from[u], (l + 1) * len - 1));
          for (int i = l + 1; i < r; i++) {
            ans = max(ans, ds[i].query(i * len, (i + 1) * len - 1));
          }
          ans = max(ans, ds[r].query(r * len, to[u]));
          cout << ans << '\n';
        }
      }
    }
  }
}