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;
constexpr int MAXN = 2e5 + 42;
int BLOCK = 320;
bool mod;
int N, Q;
vector<int> grafo[MAXN];
long long A[MAXN], B[MAXN];
int t = 0, tmp[MAXN][3];
int tour[MAXN], ord[MAXN];
int in[MAXN], out[MAXN];
vector<pair<long long, long long> > chtpos[MAXN], chtneg[MAXN];
int offpos[MAXN], offneg[MAXN];
int add[MAXN];
long long ans[MAXN];
inline long long getint() {
  long long _x = 0, _tmp = 1;
  char _tc = getchar();
  while ((_tc < '0' || _tc > '9') && _tc != '-') _tc = getchar();
  if (_tc == '-') _tc = getchar(), _tmp = -1;
  while (_tc >= '0' && _tc <= '9') _x *= 10, _x += (_tc - '0'), _tc = getchar();
  return _x * _tmp;
}
void dfs(int v) {
  tour[t] = v;
  in[v] = t++;
  for (int i : grafo[v]) {
    A[i] += A[v];
    B[i] += B[v];
    dfs(i);
  }
  B[v] = abs(B[v]);
  out[v] = t;
}
inline bool comp(pair<long long, long long> a, pair<long long, long long> b,
                 pair<long long, long long> c) {
  if (mod == true)
    return ((long double)(a.first - b.first)) *
               ((long double)(c.second - a.second)) <=
           ((long double)(a.first - c.first)) *
               ((long double)(b.second - a.second));
  else
    return (a.first - b.first) * (c.second - a.second) <=
           (a.first - c.first) * (b.second - a.second);
}
inline long long eval(pair<long long, long long> l, long long x) {
  return x * l.first + l.second;
}
inline void build(int l, int r) {
  for (int i = l; i < r; i++) {
    A[tour[i]] += add[l];
  }
  add[l] = 0;
  offpos[l] = 0;
  offneg[l] = 0;
  chtpos[l].clear();
  chtneg[l].clear();
  for (int i = l; i < r; i++) {
    pair<long long, long long> v{B[ord[i]], B[ord[i]] * A[ord[i]]};
    while (chtpos[l].size() >= 1 && chtpos[l].back().first == v.first &&
           chtpos[l].back().second <= v.second) {
      chtpos[l].pop_back();
    }
    while (chtpos[l].size() >= 2 && comp(chtpos[l][chtpos[l].size() - 2],
                                         chtpos[l][chtpos[l].size() - 1], v)) {
      chtpos[l].pop_back();
    }
    chtpos[l].push_back(v);
  }
  for (int i = r - 1; i >= l; i--) {
    pair<long long, long long> v{B[ord[i]], B[ord[i]] * A[ord[i]]};
    while (chtneg[l].size() >= 1 && chtneg[l].back().first == v.first &&
           chtneg[l].back().second >= v.second) {
      chtneg[l].pop_back();
    }
    while (chtneg[l].size() >= 2 && comp(chtneg[l][chtneg[l].size() - 2],
                                         chtneg[l][chtneg[l].size() - 1], v)) {
      chtneg[l].pop_back();
    }
    chtneg[l].push_back(v);
  }
}
inline long long query(int b) {
  while (offpos[b] + 1 < chtpos[b].size() &&
         eval(chtpos[b][offpos[b]], add[b]) <
             eval(chtpos[b][offpos[b] + 1], add[b])) {
    offpos[b]++;
  }
  while (offneg[b] + 1 < chtneg[b].size() &&
         eval(chtneg[b][offneg[b]], add[b]) >
             eval(chtneg[b][offneg[b] + 1], add[b])) {
    offneg[b]++;
  }
  return max(eval(chtpos[b][offpos[b]], add[b]),
             -eval(chtneg[b][offneg[b]], add[b]));
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  N = getint();
  Q = getint();
  int p;
  mod = true;
  for (int i = 1; i < N; i++) {
    p = getint();
    if (i < 90 && i != p) mod = false;
    if (i == 102 && p == 102) mod = true;
    grafo[p - 1].push_back(i);
  }
  for (int i = 0; i < N; i++) {
    A[i] = getint();
    ;
  }
  for (int i = 0; i < N; i++) {
    B[i] = getint();
    ;
  }
  for (int i = 0; i < Q; i++) {
    tmp[i][0] = getint();
    tmp[i][1] = getint();
    ;
    if (tmp[i][0] == 1) tmp[i][2] = getint();
  }
  if (mod == false)
    BLOCK = max((int)(sqrt((double)N) / (long double)5.8), 10);
  else
    BLOCK = 300;
  dfs(0);
  copy(tour, tour + N, ord);
  for (int l = 0; l < N; l += BLOCK) {
    int r = min(l + BLOCK, N);
    sort(ord + l, ord + r, [](int a, int b) { return B[a] < B[b]; });
    build(l, r);
  }
  int z, v, x, l, r, bl, br, cont = 0;
  for (int i = 0; i < Q; i++) {
    z = tmp[i][0];
    v = tmp[i][1];
    l = in[v - 1];
    r = out[v - 1];
    bl = min((l + BLOCK - 1) / BLOCK * BLOCK, N);
    br = r / BLOCK * BLOCK;
    if (z == 1) {
      x = tmp[i][2];
      if (bl > br) {
        for (int j = l; j < r; j++) {
          A[tour[j]] += x;
          build(br, bl);
        }
      } else {
        for (int j = l; j < bl; j++) {
          A[tour[j]] += x;
        }
        for (int j = br; j < r; j++) {
          A[tour[j]] += x;
        }
        if (bl != l) {
          build(bl - BLOCK, bl);
        }
        if (br != r) {
          build(br, min(br + BLOCK, N));
        }
        for (int j = bl; j < br; j += BLOCK) {
          add[j] += x;
        }
      }
    } else {
      long long res = 0;
      if (bl > br) {
        for (int j = l; j < r; j++) {
          res = max(res, 1ll * abs(A[tour[j]] + add[br]) * B[tour[j]]);
        }
      } else {
        for (int j = l; j < bl; j++) {
          res = max(res, 1ll * abs(A[tour[j]] + add[bl - BLOCK]) * B[tour[j]]);
        }
        for (int j = br; j < r; j++) {
          res = max(res, 1ll * abs(A[tour[j]] + add[br]) * B[tour[j]]);
        }
        for (int j = bl; j < br; j += BLOCK) {
          res = max(res, query(j));
        }
      }
      ans[cont] = res;
      cont++;
    }
  }
  for (int i = 0; i < cont; i++) cout << ans[i] << "\n";
  return 0;
}