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 ll = long long;
using ld = long double;
using ull = unsigned long long;
using namespace std;
const int N = 200100;
int p[N];
vector<int> eds[N];
int tin[N];
int tout[N];
ll C[N];
int A[N];
ll a[N];
ll b[N];
int tm1;
int n;
int q;
vector<int> GG;
void dfs1(int v, int ca, int cb) {
  ca += A[v];
  cb += C[v];
  A[v] = ca;
  C[v] = abs(cb);
  a[tm1] = C[v];
  b[tm1] = A[v] * C[v];
  tin[v] = tm1++;
  GG.push_back(v);
  for (int u : eds[v]) dfs1(u, ca, cb);
  tout[v] = tm1;
}
const int SQ = 600;
ll ans[N];
ll ad[N];
int tp[N];
int tv[N];
int tx[N];
vector<array<ll, 2>> Vv[N / SQ + 2];
vector<int> gg[N / SQ + 2];
void prebuild(int k) {
  int l = k * SQ;
  int r = min(n, (k + 1) * SQ);
  gg[k].clear();
  for (int i = l; i < r; ++i) gg[k].push_back(i);
  sort((gg[k]).begin(), (gg[k]).end(), [&](int x, int y) -> bool {
    return make_pair(a[x], b[x]) > make_pair(a[y], b[y]);
  });
}
bool bad(const array<ll, 2>& a, const array<ll, 2>& b, const array<ll, 2>& c) {
  return (a[1] - b[1]) * (c[0] - b[0]) >= (b[1] - c[1]) * (b[0] - a[0]);
}
void build(int k) {
  int l = k * SQ;
  int r = min(n, (k + 1) * SQ);
  auto& vv = Vv[k];
  vv.clear();
  vv.reserve(SQ + 2);
  for (int i = l; i < r; ++i) b[i] += a[i] * ad[k];
  ad[k] = 0;
  for (int i : gg[k]) {
    if (!vv.empty() && vv.back()[1] >= b[i]) continue;
    array<ll, 2> cur = {a[i], b[i]};
    while (vv.size() >= 2 && bad(cur, vv.back(), vv[vv.size() - 2]))
      vv.pop_back();
    vv.push_back(cur);
  }
}
void upd(int k, int l, int r, ll x) {
  for (int i = l; i < r; ++i) b[i] += a[i] * x;
  build(k);
}
void add(int l, int r, ll x) {
  int kl = l / SQ;
  int kr = (r - 1) / SQ;
  for (int i = kl + 1; i < kr; ++i) ad[i] += x;
  if (kl == kr)
    upd(kl, l, r, x);
  else {
    if (kl * SQ == l)
      ad[kl] += x;
    else
      upd(kl, l, (kl + 1) * SQ, x);
    if ((kr + 1) * SQ == r)
      ad[kr] += x;
    else
      upd(kr, kr * SQ, r, x);
  }
}
ll get2(int k) {
  ll ans = 0;
  auto& vv = Vv[k];
  while (vv.size() >= 2 &&
         vv.back()[0] * ad[k] + vv.back()[1] <=
             vv[vv.size() - 2][0] * ad[k] + vv[vv.size() - 2][1])
    vv.pop_back();
  if (!vv.empty()) ans = max(ans, vv.back()[0] * ad[k] + vv.back()[1]);
  return ans;
}
ll get3(int k, int l, int r) {
  ll ans = 0;
  for (int i = l; i < r; ++i) ans = max(ans, a[i] * ad[k] + b[i]);
  return ans;
}
ll get(int l, int r) {
  ll ans = 0;
  int kl = l / SQ;
  int kr = (r - 1) / SQ;
  for (int i = kl + 1; i < kr; ++i) ans = max(ans, get2(i));
  if (kl == kr)
    ans = max(ans, get3(kl, l, r));
  else {
    if (kl * SQ == l)
      ans = max(ans, get2(kl));
    else
      ans = max(ans, get3(kl, l, (kl + 1) * SQ));
    if ((kr + 1) * SQ == r)
      ans = max(ans, get2(kr));
    else
      ans = max(ans, get3(kr, kr * SQ, r));
  }
  return ans;
}
int main() {
  ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  cout.setf(ios::fixed), cout.precision(20);
  cin >> n >> q;
  for (int i = 1; i < n; ++i) {
    cin >> p[i], --p[i];
    eds[p[i]].push_back(i);
  }
  for (int i = 0; i < n; ++i) cin >> A[i];
  for (int i = 0; i < n; ++i) cin >> C[i];
  dfs1(0, 0, 0);
  for (int i = 0; i < n; i += SQ) prebuild(i / SQ);
  for (int i = 0; i < n; i += SQ) ad[i / SQ] = 0, build(i / SQ);
  for (int i = 0; i < q; ++i) {
    cin >> tp[i];
    if (tp[i] == 1) {
      cin >> tv[i] >> tx[i];
      --tv[i];
      add(tin[tv[i]], tout[tv[i]], tx[i]);
    } else {
      cin >> tv[i];
      --tv[i];
      ans[i] = max(ans[i], abs(get(tin[tv[i]], tout[tv[i]])));
    }
  }
  for (int i = 0; i < n; ++i) {
    b[i] += a[i] * ad[i / SQ];
    b[i] = -b[i];
  }
  for (int i = 0; i < n; i += SQ) ad[i / SQ] = 0, build(i / SQ);
  for (int i = q - 1; i >= 0; --i) {
    if (tp[i] == 1) {
      add(tin[tv[i]], tout[tv[i]], tx[i]);
    } else {
      ans[i] = max(ans[i], abs(get(tin[tv[i]], tout[tv[i]])));
    }
  }
  for (int i = 0; i < q; ++i)
    if (tp[i] == 2) cout << ans[i] << "\n";
  return 0;
}