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 ll = long long;
using ld = long double;
using ull = unsigned long long;
using namespace std;
const int N = 2e5 + 2, BLOCK = 400, NB = N / BLOCK + 2;
const ll INF = 1e18;
int n, q, st[N], ed[N], neu, b[N], a[N], eul[N], nb, ofBlock[N], preX[NB],
    aa[N], bb[N];
vector<int> g[N], ver[NB];
struct Line {
  ll A, B;
  ld isect(const Line &oth) {
    if (A == oth.A) return INF;
    return (ld)(B - oth.B) / (oth.A - A);
  }
  ll eval(int x) { return A * x + B; }
};
vector<Line> dq[N], dq1[N];
void dfs(int u, int sumA, int sumB) {
  st[u] = ++neu;
  a[neu] = sumA;
  b[neu] = abs(sumB);
  for (int v : g[u]) dfs(v, sumA + aa[v], sumB + bb[v]);
  ed[u] = neu;
}
void rebuildCHT(int id) {
  dq[id].clear(), dq1[id].clear();
  dq[id].reserve(BLOCK + 1);
  dq1[id].reserve(BLOCK + 1);
  for (int u : ver[id]) a[u] += preX[id];
  preX[id] = 0;
  for (int u : ver[id]) {
    Line cur = {b[u], b[u] * 1LL * a[u]};
    if (!dq[id].empty() && cur.B <= dq[id].back().B) continue;
    while (((int)(dq[id]).size()) >= 2 &&
           cur.isect(dq[id].back()) >=
               dq[id].back().isect(dq[id][((int)(dq[id]).size()) - 2]))
      dq[id].pop_back();
    dq[id].push_back(cur);
  }
  for (int i = (((int)(ver[id]).size()) - 1); i >= (0); --i) {
    int u = ver[id][i];
    Line cur = {-b[u], -b[u] * 1LL * a[u]};
    if (!dq1[id].empty() && cur.B <= dq1[id].back().B) continue;
    while (((int)(dq1[id]).size()) >= 2 &&
           cur.isect(dq1[id].back()) >=
               dq1[id].back().isect(dq1[id][((int)(dq1[id]).size()) - 2]))
      dq1[id].pop_back();
    dq1[id].push_back(cur);
  }
}
ll query(int id) {
  while (((int)(dq[id]).size()) >= 2 &&
         dq[id].back().isect(dq[id][((int)(dq[id]).size()) - 2]) <= preX[id])
    dq[id].pop_back();
  while (((int)(dq1[id]).size()) >= 2 &&
         dq1[id].back().isect(dq1[id][((int)(dq1[id]).size()) - 2]) <= preX[id])
    dq1[id].pop_back();
  return max(dq[id].back().eval(preX[id]), dq1[id].back().eval(preX[id]));
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> n >> q;
  for (int i = (1); i <= (n); ++i) ofBlock[i] = i / BLOCK;
  for (int i = (2); i <= (n); ++i) {
    int p;
    cin >> p;
    g[p].emplace_back(i);
  }
  for (int i = (1); i <= (n); ++i) cin >> aa[i];
  for (int i = (1); i <= (n); ++i) cin >> bb[i];
  dfs(1, aa[1], bb[1]);
  for (int i = (1); i <= (n); ++i) ver[ofBlock[i]].emplace_back(i);
  for (int i = (0); i <= (ofBlock[n]); ++i) {
    sort((ver[i]).begin(), (ver[i]).end(),
         [&](const int &A, const int &B) { return b[A] > b[B]; });
    rebuildCHT(i);
  }
  while (q--) {
    int t, u, L, R;
    cin >> t >> u;
    L = st[u], R = ed[u];
    if (t == 1) {
      int x;
      cin >> x;
      if (ofBlock[L] == ofBlock[R]) {
        for (int i = (L); i <= (R); ++i) a[i] += x;
        rebuildCHT(ofBlock[L]);
        continue;
      }
      int LB = ofBlock[L] + (L % BLOCK != 0),
          RB = ofBlock[R] - (R != n && R % BLOCK != BLOCK - 1);
      for (int i = (LB); i <= (RB); ++i) preX[i] += x;
      LB *= BLOCK, RB = (RB + 1) * BLOCK;
      for (int i = (L); i <= (min(R, LB - 1)); ++i) a[i] += x;
      for (int i = (max(L, RB)); i <= (R); ++i) a[i] += x;
      if (L < LB) rebuildCHT(ofBlock[L]);
      if (RB <= R) rebuildCHT(ofBlock[R]);
    } else {
      ll ans = 0;
      if (ofBlock[L] == ofBlock[R]) {
        for (int i = (L); i <= (R); ++i)
          ans = max(ans, b[i] * 1LL * abs((a[i] + preX[ofBlock[L]])));
        cout << ans << '\n';
        continue;
      }
      int LB = ofBlock[L] + (L % BLOCK != 0),
          RB = ofBlock[R] - (R != n && R % BLOCK != BLOCK - 1);
      for (int i = (LB); i <= (RB); ++i) ans = max(ans, query(i));
      LB *= BLOCK, RB = (RB + 1) * BLOCK;
      int idL = ofBlock[L], idR = ofBlock[R];
      for (int i = (L); i <= (min(R, LB - 1)); ++i)
        ans = max(ans, b[i] * 1LL * abs((a[i] + preX[idL])));
      for (int i = (max(L, RB)); i <= (R); ++i)
        ans = max(ans, b[i] * 1LL * abs((a[i] + preX[idR])));
      cout << ans << '\n';
    }
  }
  return 0;
}