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 = 2e5 + 10;
const int BB = 100;
const int MX = N / BB + 100;
const int INF = 1e9 + 10;
const long long BINF = 1e18 + 10;
struct line {
  long long k, b;
  line() : k(-INF), b(-BINF){};
  line(long long _k, long long _b) : k(_k), b(_b){};
  long long get(int x) { return k * 1ll * x + b; }
  long long intersect(line l) { return (b - l.b) / (l.k - k); }
};
long long from[MX][BB + 1];
int Ptr[MX], Sz[MX];
line arr[MX][BB + 1];
void init(int id) {
  Sz[id] = 1;
  from[id][1] = -INF;
  arr[id][1] = line();
  Ptr[id] = 1;
}
void add_line(int id, line nl) {
  while (Sz[id] > 1) {
    if (nl.k == arr[id][Sz[id]].k ||
        arr[id][Sz[id]].intersect(nl) < from[id][Sz[id]]) {
      Sz[id]--;
    } else {
      break;
    }
  }
  from[id][Sz[id] + 1] = arr[id][Sz[id]].intersect(nl);
  arr[id][Sz[id] + 1] = nl;
  Sz[id]++;
}
long long get(int id, int x) {
  Ptr[id] = min(Ptr[id], Sz[id]);
  while (Ptr[id] < Sz[id] &&
         arr[id][Ptr[id] + 1].get(x) >= arr[id][Ptr[id]].get(x)) {
    Ptr[id]++;
  }
  return arr[id][Ptr[id]].get(x);
}
vector<int> g[N], order;
int A[N], B[N], sz[N], a[N], b[N];
void dfs(int v, int sumA, int sumB) {
  sz[v] = 1;
  order.push_back(v);
  A[(int)(order).size() - 1] = sumA;
  B[(int)(order).size() - 1] = abs(sumB);
  for (auto u : g[v]) {
    dfs(u, sumA + a[u], sumB + b[u]);
    sz[v] += sz[u];
  }
}
int mx[N], L[N], R[N], ptr[N];
pair<long long, long long> lines[N];
void rebuild(int block_id) {
  int cur = 0;
  mx[block_id] = -INF;
  for (int i = L[block_id]; i <= R[block_id]; i++) {
    if (A[i] + ptr[block_id] >= 0) {
      lines[cur++] = {B[i], A[i] * 1ll * B[i]};
    } else {
      mx[block_id] = max(mx[block_id], A[i]);
      lines[cur++] = {-B[i], -A[i] * 1ll * B[i]};
    }
  }
  sort(lines, lines + cur);
  init(block_id);
  for (int i = 0; i < cur; i++) {
    add_line(block_id, line(lines[i].first, lines[i].second));
  }
}
int pos[N], need_rebuild[N];
bool block_begin[N], block_end[N];
signed main() {
  ios_base::sync_with_stdio(0);
  int n, q;
  cin >> n >> q;
  for (int i = 2; i <= n; i++) {
    int p;
    cin >> p;
    g[p].push_back(i);
  }
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  for (int i = 1; i <= n; i++) {
    cin >> b[i];
  }
  dfs(1, a[1], b[1]);
  for (int i = 0; i < n; i++) {
    pos[order[i]] = i;
  }
  int cnt_blocks = (n + BB - 1) / BB;
  for (int i = 0; i < cnt_blocks; i++) {
    L[i] = BB * i;
    R[i] = min(BB * (i + 1), n) - 1;
    block_begin[L[i]] = true;
    block_end[R[i]] = true;
    ptr[i] = 0;
    rebuild(i);
  }
  int C = 0;
  for (int i = 1; i <= q; i++) {
    int type;
    cin >> type;
    if (type == 1) {
      int v, x;
      cin >> v >> x;
      int l = pos[v], r = pos[v] + sz[v] - 1;
      int fr = l / BB, to = r / BB;
      need_rebuild[fr] = need_rebuild[to] = i;
      while (l <= r && !block_begin[l]) {
        A[l] += x;
        l++;
      }
      while (r >= l && !block_end[r]) {
        A[r] += x;
        r--;
      }
      if (l <= r) {
        for (int j = l / BB; j <= r / BB; j++) {
          ptr[j] += x;
          if (mx[j] + ptr[j] >= 0) {
            need_rebuild[j] = i;
          }
        }
      }
      for (int j = fr; j <= to; j++) {
        if (need_rebuild[j] == i) {
          C++;
          rebuild(j);
        }
      }
    } else {
      int v;
      cin >> v;
      int l = pos[v], r = pos[v] + sz[v] - 1;
      long long ans = 0;
      while (l <= r && !block_begin[l]) {
        ans = max(ans, abs(A[l] + ptr[l / BB]) * 1ll * B[l]);
        l++;
      }
      while (r >= l && !block_end[r]) {
        ans = max(ans, abs(A[r] + ptr[r / BB]) * 1ll * B[r]);
        r--;
      }
      if (l <= r) {
        for (int j = l / BB; j <= r / BB; j++) {
          ans = max(ans, get(j, ptr[j]));
        }
      }
      cout << ans << '\n';
    }
  }
  cerr << "TIME :: " << clock() * 1.0 / CLOCKS_PER_SEC << '\n';
  cerr << "REBUILDS " << C << '\n';
}