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>
const int MAXN = 200010;
void gma(long long& x, long long y) { x < y ? x = y : 0; }
int head[MAXN], nxt[MAXN], fa[MAXN];
int n, Q;
int _A[MAXN], _B[MAXN], in[MAXN], out[MAXN], idx;
int A[MAXN], B[MAXN];
void dfs(int u) {
  in[u] = ++idx;
  A[idx] = _A[u], B[idx] = _B[u];
  A[idx] += A[in[fa[u]]], B[idx] += B[in[fa[u]]];
  for (int i = head[u]; i; i = nxt[i]) dfs(i);
  out[u] = idx;
  B[in[u]] = std::abs(B[in[u]]);
}
int bel[MAXN];
const int BLO = 300;
const int CNT = MAXN / BLO + 3;
long long val(int x, int v) { return (long long)std::abs(A[x] + v) * B[x]; }
long long val(int x) { return (long long)std::abs(A[x]) * B[x]; }
int ks[MAXN], li[MAXN], st[MAXN];
long long bs[MAXN];
struct Block {
  int L, R;
  int minn, tag;
  std::vector<int> V, b;
  int cur;
  bool cross(int x, int y, int z) {
    int x1 = ks[y] - ks[x], x2 = ks[z] - ks[x];
    long long y1 = bs[y] - bs[x], y2 = bs[z] - bs[x];
    long double cr = (long double)x1 * y2 - (long double)x2 * y1;
    return cr >= -1e-8;
  }
  void rebuild() {
    for (int i = L; i <= R; ++i) A[i] += tag;
    cur = tag = 0;
    minn = 2000000000;
    int bak = 0;
    for (auto t : b)
      if (A[t] < 0) {
        li[++bak] = t, ks[t] = -B[t], bs[t] = val(t);
        minn = std::min(minn, -A[t]);
      }
    std::reverse(li + 1, li + 1 + bak);
    for (auto t : b)
      if (A[t] >= 0) li[++bak] = t, ks[t] = B[t], bs[t] = val(t);
    int top = 0;
    for (int i = 1; i <= bak; ++i) {
      while (top > 1 && cross(st[top - 1], st[top], li[i])) --top;
      st[++top] = li[i];
    }
    V.clear();
    for (int i = 1; i <= top; ++i) V.push_back(st[i]);
  }
  void init() {
    for (int i = L; i <= R; ++i) b.push_back(i);
    std::sort(b.begin(), b.end(), [](int a, int b) { return B[a] < B[b]; });
    rebuild();
  }
  void add(int v, int hl = -1, int hr = -1) {
    if (hl == -1 && hr == -1) {
      if ((tag += v) < minn) return;
      rebuild();
    } else {
      if (hl == -1) hl = L;
      if (hr == -1) hr = R;
      for (int i = hl; i <= hr; ++i) A[i] += v;
      rebuild();
    }
  }
  long long qry(int hl = -1, int hr = -1) {
    if (hl == -1 && hr == -1) {
      const int S = V.size();
      while (cur + 1 < S && val(V[cur], tag) <= val(V[cur + 1], tag)) ++cur;
      return val(V[cur], tag);
    } else {
      long long res = 0;
      if (hl == -1) hl = L;
      if (hr == -1) hr = R;
      for (int i = hl; i <= hr; ++i) gma(res, val(i, tag));
      return res;
    }
  }
} blo[CNT];
int main() {
  std::ios_base::sync_with_stdio(false), std::cin.tie(0);
  std::cin >> n >> Q;
  for (int i = 2; i <= n; ++i)
    std::cin >> fa[i], nxt[i] = head[fa[i]], head[fa[i]] = i;
  for (int i = 1; i <= n; ++i) std::cin >> _A[i];
  for (int i = 1; i <= n; ++i) std::cin >> _B[i];
  for (int i = 1; i <= n; ++i) {
    bel[i] = (i - 1) / BLO;
    if (!blo[bel[i]].L) blo[bel[i]].L = i;
    blo[bel[i]].R = i;
  }
  dfs(1);
  for (int i = 1; i <= bel[n]; ++i) blo[i].init();
  while (Q-- > 0) {
    int opt, v, x;
    std::cin >> opt >> v;
    int l = in[v], r = out[v];
    if (opt == 1) {
      std::cin >> x;
      if (bel[l] != bel[r]) {
        blo[bel[l]].add(x, l);
        for (int i = bel[l] + 1; i < bel[r]; ++i) blo[i].add(x);
        blo[bel[r]].add(x, -1, r);
      } else
        blo[bel[l]].add(x, l, r);
    } else {
      long long ans = 0;
      if (bel[l] != bel[r]) {
        ans = blo[bel[l]].qry(l);
        for (int i = bel[l] + 1; i < bel[r]; ++i) gma(ans, blo[i].qry());
        gma(ans, blo[bel[r]].qry(-1, r));
      } else
        ans = blo[bel[l]].qry(l, r);
      std::cout << ans << '\n';
    }
  }
  return 0;
}