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>
#pragma GCC optimize("O3")
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using ld = long double;
const int N = 2e5;
const int B = 182;
const int C = (N + B - 1) / B;
int n, q;
vi g[N];
int a[N], b[N];
int in[N], out[N], tik_tak = -1, eu[N];
void dfs(int v) {
  in[v] = ++tik_tak;
  eu[tik_tak] = v;
  for (int to : g[v]) {
    a[to] += a[v];
    b[to] += b[v];
    dfs(to);
  }
  out[v] = tik_tak;
}
struct Line {
  ll k, b;
  int id;
  bool operator<(const Line& l) const { return k < l.k; }
};
ld isec(const Line& u, const Line& v) { return ((ld)u.b - v.b) / (v.k - u.k); }
int s[C];
Line H[C][2 * B];
int s1[C];
Line L[C][2 * B];
ld xs[C][2 * B];
ll x[C];
int pt[C];
void push(int i) {
  if (s[i] <= pt[i]) {
    pt[i] = s[i] - 1;
  }
  while (pt[i] < s[i] - 1) {
    if (x[i] < xs[i][pt[i]]) {
      break;
    }
    pt[i]++;
  }
}
void add(int i, const Line& l) {
  while (s[i] > 1) {
    const Line& u = H[i][s[i] - 2];
    const Line& v = H[i][s[i] - 1];
    if (l.k == v.k) {
      if (l.b <= v.b) {
        return;
      }
    } else {
      if (xs[i][s[i] - 2] < isec(l, v)) {
        break;
      }
    }
    s[i]--;
  }
  if (s[i] == 1) {
    const Line& v = H[i][s[i] - 1];
    if (l.k == v.k) {
      if (l.b <= v.b) {
        return;
      }
      s[i]--;
    }
  }
  if (s[i]) {
    xs[i][s[i] - 1] = isec(l, H[i][s[i] - 1]);
  }
  H[i][s[i]++] = l;
  push(i);
}
ll eval(int i) { return H[i][pt[i]].k * x[i] + H[i][pt[i]].b; }
int32_t main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n >> q;
  for (int i = 0; i < n - 1; i++) {
    int p;
    cin >> p;
    --p;
    g[p].push_back(i + 1);
  }
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  for (int i = 0; i < n; i++) {
    cin >> b[i];
  }
  dfs(0);
  for (int i = 0; i < n; i++) {
    b[i] = abs(b[i]);
  }
  for (int i = 0; i < (n + B - 1) / B; i++) {
    int l = B * i, r = min(n - 1, B * (i + 1) - 1);
    for (int j = l; j <= r; j++) {
      int id = eu[j];
      L[i][s1[i]++] = {b[id], 1LL * a[id] * b[id], j};
      L[i][s1[i]++] = {-b[id], -1LL * a[id] * b[id], j};
    }
    sort(L[i], L[i] + s1[i]);
    for (int j = 0; j < s1[i]; j++) {
      add(i, L[i][j]);
    }
  }
  while (q--) {
    int type, v;
    cin >> type >> v;
    --v;
    int l = in[v], r = out[v];
    int LL = l / B, RR = r / B;
    if (type == 1) {
      int d;
      cin >> d;
      for (int p : {LL, RR}) {
        s[p] = pt[p] = 0;
        for (int i = 0; i < s1[p]; i++) {
          Line& u = L[p][i];
          if (l <= u.id && u.id <= r) {
            if (u.k >= 0) {
              u.b += 1LL * d * b[eu[u.id]];
            } else {
              u.b -= 1LL * d * b[eu[u.id]];
            }
          }
          add(p, u);
        }
        if (LL == RR) {
          break;
        }
      }
      LL++;
      RR--;
      for (int i = LL; i <= RR; i++) {
        x[i] += d;
        push(i);
      }
    } else {
      ll ans = 0;
      for (int p : {LL, RR}) {
        for (int i = 0; i < s1[p]; i++) {
          Line& u = L[p][i];
          if (l <= u.id && u.id <= r) {
            ans = max(ans, abs(u.k * x[p] + u.b));
          }
        }
        if (LL == RR) {
          break;
        }
      }
      LL++;
      RR--;
      for (int i = LL; i <= RR; i++) {
        ans = max(ans, eval(i));
      }
      cout << ans << '\n';
    }
  }
}