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;
#pragma GCC optimize(2)
struct no {
  long long k, b;
};
long long f(long long x, no y) { return x * y.k + y.b; }
vector<no> v[500010];
vector<int> id[500010], vc[500010];
long long k[500010], b[500010], tg[500010];
int dfn[500010], sz[500010], p[500010], va[500010], vb[500010], po[500010], n,
    q, s, pl[500010], pr[500010], ct, h[500010], vv[500010 * 2],
    nxt[500010 * 2], ec, bl[500010];
inline void add(int x, int y) {
  vv[++ec] = y;
  nxt[ec] = h[x];
  h[x] = ec;
}
inline void dfs(int x, long long s1, long long s2) {
  dfn[x] = ++ct;
  s1 += va[x];
  s2 += vb[x];
  k[ct] = s2;
  b[ct] = 1ll * s2 * s1;
  k[ct + n] = -s2;
  b[ct + n] = 1ll * -s1 * s2;
  for (auto i : vc[x]) dfs(i, s1, s2);
  po[x] = ct;
}
inline int cp(int x, int y) { return k[x] < k[y]; }
inline double xl(no x, no y) { return 1.0 * (x.b - y.b) / (y.k - x.k); }
inline void b1(vector<no>& v) {
  vector<no> tp;
  for (no x : v) {
    if (!tp.empty() && tp.back().k == x.k) {
      if (tp.back().b <= x.b)
        tp.pop_back();
      else
        continue;
    }
    while (tp.size() > 1 &&
           xl(tp[tp.size() - 2], x) <= xl(tp[tp.size() - 2], tp.back()))
      tp.pop_back();
    tp.push_back(x);
  }
  v = tp;
}
inline void b2(int x) {
  v[x].clear();
  for (auto i : id[x]) {
    no tp;
    if (i > n)
      tp = (no){-k[i - n], -b[i - n]};
    else
      tp = (no){k[i], b[i]};
    v[x].push_back(tp);
  }
  b1(v[x]);
}
inline void mod(int l, int r, long long x) {
  int c = bl[l], d = bl[r];
  if (c == d) {
    for (int i = l; i <= r; i++) b[i] += 1ll * x * k[i];
    b2(c);
    p[c] = 0;
  } else {
    for (int i = l; i <= pr[c]; i++) b[i] += 1ll * x * k[i];
    b2(c);
    p[c] = 0;
    for (int i = c + 1; i < d; i++) tg[i] += x;
    for (int i = pl[d]; i <= r; i++) b[i] += 1ll * x * k[i];
    b2(d);
    p[d] = 0;
  }
}
inline long long q1(long long x) {
  while (p[x] + 1 < v[x].size() &&
         f(tg[x], v[x][p[x]]) <= f(tg[x], v[x][p[x] + 1]))
    p[x]++;
  return f(tg[x], v[x][p[x]]);
}
inline long long q2(int l, int r) {
  int c = bl[l], d = bl[r];
  long long va = 0;
  if (c == d) {
    for (int i = l; i <= r; i++) {
      va = max(va, 1ll * k[i] * tg[c] + b[i]);
      va = max(va, 1ll * -k[i] * tg[c] - b[i]);
    }
    return va;
  }
  for (int i = l; i <= pr[c]; i++) {
    va = max(va, 1ll * k[i] * tg[c] + b[i]);
    va = max(va, 1ll * -k[i] * tg[c] - b[i]);
  }
  for (int i = c + 1; i < d; i++) va = max(va, q1(i));
  for (int i = pl[d]; i <= r; i++) {
    va = max(va, 1ll * k[i] * tg[d] + b[i]);
    va = max(va, 1ll * -k[i] * tg[d] - b[i]);
  }
  return va;
}
signed main() {
  cin >> n >> q;
  for (int i = 2; i <= n; i++) {
    int x;
    cin >> x;
    vc[x].push_back(i);
  }
  for (int i = 1; i <= n; i++) cin >> va[i];
  for (int i = 1; i <= n; i++) cin >> vb[i];
  s = max((int)sqrt(n / 7), 1);
  for (int i = 1; i <= n; i++) bl[i] = (i - 1) / s + 1;
  for (int i = 1; i <= bl[n]; i++) {
    pl[i] = pr[i - 1] + 1;
    pr[i] = i * s;
  }
  pr[bl[n]] = n;
  dfs(1, 0, 0);
  for (int i = 1; i <= bl[n]; i++) {
    for (int j = pl[i]; j <= pr[i]; j++) {
      id[i].push_back(j);
      id[i].push_back(j + n);
    }
    sort(id[i].begin(), id[i].end(), cp);
  }
  for (int i = 1; i <= bl[n]; i++) b2(i);
  while (q--) {
    int op, v;
    cin >> op >> v;
    if (op == 1) {
      int x;
      cin >> x;
      mod(dfn[v], po[v], x);
    } else
      cout << q2(dfn[v], po[v]) << '\n';
  }
}