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 03
using namespace std;
const int N = 5e5;
const int L = 500;
const long long inf = 1e9;
const long double EPS = 1e-9;
long long k[2][N / L][L], d[2][N / L][L];
long double l[2][N / L][L];
int top[2][N / L], tin[N], tout[N], p[N], pos[2][N];
long long db[2][N / L], c[N], a[N], b[N], t[N], top1 = 0, dx[N];
bool flag = 0;
vector<int> e[N];
int Lt = 0;
int uk[2][N];
void dfs(int u, long long sum, long long sum1) {
  sum += c[u];
  sum1 += t[u];
  tin[u] = ++top1;
  p[tin[u]] = u;
  a[u] = sum;
  b[u] = abs(sum1);
  for (int i = 0; i < e[u].size(); ++i) dfs(e[u][i], sum, sum1);
  tout[u] = top1;
}
void build(int u, int v, int vl, int vr) {
  int i, j;
  db[u][v] = 0;
  vector<pair<long long, pair<long long, int> > > fv;
  if (!flag) {
    for (i = vl; i < vr; ++i) {
      long long a1, b1;
      if ((u & 1) > 0)
        a1 = -a[p[i]];
      else
        a1 = a[p[i]];
      b1 = b[p[i]];
      fv.push_back({b1, {a1 * b1, i}});
    }
    sort(fv.begin(), fv.end());
    for (i = 0; i < fv.size(); ++i) pos[u][fv[i].second.second] = i;
  } else {
    fv.resize(vr - vl);
    for (i = vl; i < vr; ++i) {
      long long a1, b1;
      if ((u & 1) > 0)
        a1 = -a[p[i]];
      else
        a1 = a[p[i]];
      b1 = b[p[i]];
      fv[pos[u][i]] = {b1, {a1 * b1, i}};
    }
  }
  int tp = -1;
  for (i = 0; i < fv.size(); ++i) {
    long long kx = fv[i].first, dx = fv[i].second.first;
    while (tp >= 0 &&
           k[u][v][tp] * l[u][v][tp] + d[u][v][tp] < kx * l[u][v][tp] + dx)
      --tp;
    if (tp >= 0 && k[u][v][tp] == kx) continue;
    ++tp;
    k[u][v][tp] = fv[i].first;
    d[u][v][tp] = fv[i].second.first;
    if (tp == 0)
      l[u][v][tp] = -inf;
    else {
      l[u][v][tp] = (d[u][v][tp - 1] - d[u][v][tp]) * 1.0 /
                    (k[u][v][tp] - k[u][v][tp - 1]);
    }
  }
  top[u][v] = tp;
  if (u == 0)
    uk[u][v] = 0;
  else
    uk[u][v] = tp;
}
long long get(int u, int v) {
  if (u == 0)
    while (uk[u][v] < top[u][v] && db[u][v] > l[u][v][uk[u][v] + 1]) ++uk[u][v];
  else
    while (uk[u][v] > 0 && db[u][v] < l[u][v][uk[u][v]]) --uk[u][v];
  return db[u][v] * k[u][v][uk[u][v]] + d[u][v][uk[u][v]];
}
int main() {
  int i, j, k, n, w, h, q, type;
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> q;
  for (i = 2; i <= n; ++i) {
    cin >> j;
    e[j].push_back(i);
  }
  for (i = 1; i <= n; ++i) cin >> c[i];
  for (i = 1; i <= n; ++i) cin >> t[i];
  dfs(1, 0, 0);
  Lt = max(1, (int)sqrt(n) / 2);
  for (i = 0; i < 2; ++i)
    for (j = 0; j <= n / Lt; ++j)
      build(i, j, max(1, j * Lt), min(Lt * (1 + j), n + 1));
  flag = 1;
  for (i = 0; i < q; ++i) {
    cin >> type;
    if (type == 1) {
      cin >> w >> h;
      for (j = 0; j <= n / Lt; ++j)
        if (tin[w] <= j * Lt && (j + 1) * Lt - 1 <= tout[w]) {
          db[0][j] += h;
          db[1][j] -= h;
        } else if (max(j * Lt, tin[w]) <= min((j + 1) * Lt - 1, tout[w])) {
          for (int t = max(1, j * Lt); t < (j + 1) * Lt; ++t) {
            a[p[t]] += db[0][j];
            if (tin[w] <= t && t <= tout[w]) a[p[t]] += h;
          }
          for (int p = 0; p < 2; ++p)
            build(p, j, max(1, j * Lt), min(Lt * (1 + j), n + 1));
        }
    } else {
      cin >> w;
      long long ans = 0;
      for (j = 0; j <= n / Lt; ++j)
        if (tin[w] <= j * Lt && (j + 1) * Lt - 1 <= tout[w]) {
          for (int p = 0; p < 2; ++p) ans = max(ans, get(p, j));
        } else if (max(j * Lt, tin[w]) <= min((j + 1) * Lt - 1, tout[w])) {
          for (int t = j * Lt; t < (j + 1) * Lt; ++t)
            if (tin[w] <= t && t <= tout[w])
              ans = max(ans, abs(a[p[t]] + db[0][j]) * b[p[t]]);
        }
      cout << ans << "\n";
    }
  }
}