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 namespace std;
const int N = 200005, D = 1150;
int n, q, u, t, x, d, cnt = -1, p[N], in[N], out[N];
int a[N], b[N], add[D], ind[N][2];
vector<int> adj[N];
struct SLine {
  int a;
  long long b;
  SLine(int _a, long long _b) : a(_a), b(_b) {}
  bool operator<(const SLine &oth) const {
    return a < oth.a || (a == oth.a && b < oth.b);
  }
  double intersect(SLine oth) { return 1.0 * (oth.b - b) / (a - oth.a); }
  long long at(int pos) { return 1LL * a * pos + b; }
};
vector<pair<SLine, int>> con[D];
struct SCHT {
  vector<SLine> ve;
  int pt = 0;
  void push(SLine u) {
    if (!ve.empty() && u.a == ve.back().a) {
      u.b = max(u.b, ve.back().b);
      ve.pop_back();
    }
    while (ve.size() >= 2 &&
           u.intersect(ve[ve.size() - 2]) >= u.intersect(ve[ve.size() - 1]))
      ve.pop_back();
    ve.push_back(u);
  }
  void build(vector<pair<SLine, int>> &upd) {
    ve.clear();
    pt = 0;
    for (pair<SLine, int> &v : upd) push(v.first);
  }
  long long maxima(int pos) {
    while (pt + 1 < (int)ve.size() && ve[pt].at(pos) <= ve[pt + 1].at(pos))
      pt++;
    return ve[pt].at(pos);
  }
} cht[D];
void DFS(int u) {
  in[u] = ++cnt;
  for (int &v : adj[u]) DFS(v);
  out[u] = cnt;
}
void update(int l, int r, int u) {
  int bl = l / d;
  for (; l <= r && l / d == bl; l++) {
    con[bl][ind[l][0]].first.b += 1LL * a[l] * u;
    con[bl][ind[l][1]].first.b -= 1LL * a[l] * u;
  }
  cht[bl].build(con[bl]);
  for (; l + d - 1 <= r; l += d) add[l / d] += u;
  if (l > r) return;
  bl = l / d;
  for (; l <= r; l++) {
    con[bl][ind[l][0]].first.b += 1LL * a[l] * u;
    con[bl][ind[l][1]].first.b -= 1LL * a[l] * u;
  }
  cht[bl].build(con[bl]);
}
long long query(int l, int r) {
  long long ans = 0;
  int bl = l / d;
  for (; l <= r && l / d == bl; l++) {
    ans = max(ans, con[bl][ind[l][0]].first.at(add[bl]));
    ans = max(ans, con[bl][ind[l][1]].first.at(add[bl]));
  }
  for (; l + d - 1 <= r; l += d) ans = max(ans, cht[l / d].maxima(add[l / d]));
  bl = l / d;
  for (; l <= r; l++) {
    ans = max(ans, con[bl][ind[l][0]].first.at(add[bl]));
    ans = max(ans, con[bl][ind[l][1]].first.at(add[bl]));
  }
  return ans;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> n >> q;
  d = sqrt((n - 1) / 6) + 1;
  for (int i = 2; i <= n; i++) {
    cin >> p[i];
    adj[p[i]].push_back(i);
  }
  DFS(1);
  for (int i = 1; i <= n; i++) {
    cin >> u;
    b[in[i]] = b[in[p[i]]] + u;
  }
  for (int i = 1; i <= n; i++) {
    cin >> u;
    a[in[i]] = a[in[p[i]]] + u;
  }
  for (int i = 0; i < n; i += d) {
    int bl = i / d;
    for (int j = i; j < (bl + 1) * d && j < n; j++) {
      con[bl].push_back({SLine(a[j], 1LL * a[j] * b[j]), j + 1});
      con[bl].push_back({SLine(-a[j], -1LL * a[j] * b[j]), -j - 1});
    }
    sort(con[bl].begin(), con[bl].end());
    for (int i = 0; i < (int)con[bl].size(); i++) {
      int u = con[bl][i].second;
      if (u > 0)
        ind[u - 1][0] = i;
      else
        ind[-u - 1][1] = i;
    }
    cht[bl].build(con[bl]);
  }
  while (q--) {
    cin >> t >> u;
    if (t == 1) {
      cin >> x;
      update(in[u], out[u], x);
    } else
      cout << query(in[u], out[u]) << '\n';
  }
}