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;
template <typename T>
void read(T &x) {
  cin >> x;
}
const int N = 200020;
int n, q, fa, a[N], b[N];
long long c[N] = {0}, d[N] = {0};
vector<int> G[N];
int dfn[N], sz[N], tim = 1;
void dfs(int num) {
  c[num] += a[num];
  d[num] += b[num];
  dfn[num] = tim;
  tim += 1;
  sz[num] = 1;
  for (auto ct : G[num]) {
    c[ct] = c[num];
    d[ct] = d[num];
    dfs(ct);
    sz[num] += sz[ct];
  }
}
struct P {
  int id;
  long long x, y;
  P(long long cx = 0, long long cy = 0, long long nid = 0)
      : x(cx), y(cy), id(nid) {}
  P operator-(const P &rhs) const { return P(x - rhs.x, y - rhs.y); }
  bool operator<(const P &rhs) const {
    if (x != rhs.x) return x < rhs.x;
    return y < rhs.y;
  }
  long long operator*(const P &rhs) const {
    if (abs(1.0 * x * rhs.y - 1.0 * y * rhs.x) > 1e5) {
      if (1.0 * x * rhs.y - 1.0 * y * rhs.x > 0)
        return 1;
      else
        return -1;
    }
    return x * rhs.y - y * rhs.x;
  }
};
struct convex {
  int l = 1e9, r = 0, cpo = 0;
  long long accu = 0, cans = 0;
  vector<P> cp;
  vector<P> alp;
  void rebuild() {
    alp.clear();
    for (int i = 0; i < cp.size(); i++) {
      cp[i].y += cp[i].x * accu;
      while (alp.size() >= 2 && (alp[alp.size() - 1] - alp[alp.size() - 2]) *
                                        (cp[i] - alp[alp.size() - 1]) >=
                                    0)
        alp.pop_back();
      alp.push_back(cp[i]);
    }
    assert(alp.size() != 0);
    accu = cpo = 0;
    while (cpo < (int)alp.size() - 1 && alp[cpo + 1].y > alp[cpo].y) cpo += 1;
    cans = alp[cpo].y;
  }
  void build() {
    sort(cp.begin(), cp.end());
    rebuild();
  }
  void add(int cl, int cr, int cx) {
    if (cr < l || cl > r) return;
    if (cl <= l && r <= cr) {
      accu += cx;
      if (cx > 0)
        while (cpo < (int)alp.size() - 1 &&
               alp[cpo + 1].y + alp[cpo + 1].x * accu >=
                   alp[cpo].y + alp[cpo].x * accu)
          cpo += 1;
      if (cx < 0)
        while (cpo > 0 && alp[cpo - 1].y + alp[cpo - 1].x * accu >=
                              alp[cpo].y + alp[cpo].x * accu)
          cpo -= 1;
      cans = alp[cpo].y + alp[cpo].x * accu;
      return;
    }
    for (int i = 0; i < cp.size(); i++) {
      if (cp[i].id <= cr && cp[i].id >= cl) cp[i].y += cp[i].x * cx;
    }
    rebuild();
  }
  long long qans(int cl, int cr) {
    if (cr < l || cl > r) return -1e18;
    if (cl <= l && r <= cr) return cans;
    long long ans = -1e18;
    for (auto ct : cp)
      if (ct.id <= cr && ct.id >= cl) ans = max(ans, ct.y + ct.x * accu);
    return ans;
  }
} C[2020], rC[2020];
int main() {
  cin >> n >> q;
  for (int i = 2; i <= n; i++) {
    read(fa);
    G[fa].push_back(i);
  }
  for (int i = 1; i <= n; i++) read(a[i]);
  for (int i = 1; i <= n; i++) read(b[i]);
  dfs(1);
  int blc = sqrt(n / 6) + 2, blcn = n / blc;
  for (int i = 1; i <= n; i++) {
    d[i] = abs(d[i]);
    C[dfn[i] / blc].l = min(C[dfn[i] / blc].l, dfn[i]);
    C[dfn[i] / blc].r = max(C[dfn[i] / blc].r, dfn[i]);
    C[dfn[i] / blc].cp.push_back(P(d[i], c[i] * d[i], dfn[i]));
    rC[dfn[i] / blc].cp.push_back(P(d[i], -c[i] * d[i], dfn[i]));
  }
  for (int i = 0; i <= blcn; i++) {
    C[i].build();
    rC[i].l = C[i].l;
    rC[i].r = C[i].r;
    rC[i].build();
  }
  while (q--) {
    int typ, v, x;
    read(typ);
    read(v);
    int l = dfn[v], r = dfn[v] + sz[v] - 1;
    if (typ == 1) {
      read(x);
      for (int i = 0; i <= blcn; i++) {
        rC[i].add(l, r, -x);
        C[i].add(l, r, x);
      }
    } else {
      long long ans = -1e18;
      for (int i = 0; i <= blcn; i++) {
        ans = max(ans, C[i].qans(l, r));
        ans = max(ans, rC[i].qans(l, r));
      }
      cout << ans << endl;
    }
  }
  return 0;
}