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 T1, typename T2>
inline void chkmin(T1 &x, T2 y) {
  if (x > y) x = y;
}
template <typename T1, typename T2>
inline void chkmax(T1 &x, T2 y) {
  if (x < y) x = y;
}
const string FILENAME = "input";
const int MAXN = 200229;
int n, q;
vector<int> gg[MAXN];
int a[MAXN], b[MAXN];
long long cura[MAXN], curb[MAXN];
vector<int> order;
int in[MAXN], out[MAXN];
int timer = 0;
void dfs(int u) {
  timer++;
  in[u] = timer;
  order.push_back(u);
  cura[u] += a[u];
  curb[u] += b[u];
  for (auto h : gg[u]) {
    cura[h] += cura[u];
    curb[h] += curb[u];
    dfs(h);
  }
  out[u] = timer;
}
struct Line {
  long long k, b;
  int id;
  Line() {}
  Line(long long _k, long long _b, int _id) {
    k = _k;
    b = _b;
    id = _id;
  }
  long long value(long long x) { return k * x + b; }
};
bool operator<(const Line &a, const Line &b) {
  return a.k < b.k || (a.k == b.k && a.b < b.b);
}
struct ConvexHull {
  vector<Line> st;
  int uks = 0;
  bool better(Line a, Line b, Line c) {
    return (c.b - a.b) * (a.k - b.k) <= (b.b - a.b) * (a.k - c.k);
  }
  void addLine(Line x) {
    while ((int)(st).size() >= 2 &&
           better(st[(int)(st).size() - 2], st.back(), x)) {
      st.pop_back();
    }
    st.push_back(x);
  }
} kek[MAXN], kek1[MAXN], kek2[MAXN], kek3[MAXN];
long long curadd[MAXN];
long long curadd1[MAXN];
vector<Line> g[MAXN], g1[MAXN];
void pushadd(ConvexHull &a, long long value) {
  while (a.uks + 1 < (int)(a.st).size() &&
         a.st[a.uks].value(value) <= a.st[a.uks + 1].value(value)) {
    a.uks++;
  }
}
void pushadd1(ConvexHull &a, long long value) {
  while (a.uks > 0 &&
         a.st[a.uks - 1].value(value) >= a.st[a.uks].value(value)) {
    a.uks--;
  }
}
void upd(int i, int val) {
  curadd[i] += val;
  curadd1[i] -= val;
  pushadd(kek[i], curadd[i]);
  pushadd1(kek1[i], curadd1[i]);
}
void add(vector<Line> &f, ConvexHull &a, int l, int r, long long x,
         long long val, bool ff = false) {
  a.st.clear();
  a.uks = 0;
  for (auto &z : f) {
    z.b += z.k * val;
    if (in[z.id] >= l && in[z.id] <= r) {
      z.b += z.k * x;
    }
  }
  for (auto z : f) {
    a.addLine(z);
  }
  if (ff) {
    a.uks = (int)(a.st).size() - 1;
    pushadd1(a, 0);
  } else {
    pushadd(a, 0);
  }
}
void add(int l, int r, long long x) {
  for (int i = l >> 8; i <= (r >> 8); i++) {
    if (i == (l >> 8) || i == (r >> 8)) {
      add(g[i], kek[i], l, r, x, curadd[i]);
      add(g1[i], kek1[i], l, r, -x, curadd1[i], true);
      curadd[i] = 0;
      curadd1[i] = 0;
    } else {
      upd(i, x);
    }
  }
}
long long get(int l, int r) {
  long long ans = -4e18;
  for (int i = l >> 8; i <= (r >> 8); i++) {
    if (i == (l >> 8) || i == (r >> 8)) {
      for (auto z : g[i]) {
        if (in[z.id] >= l && in[z.id] <= r) {
          chkmax(ans, z.value(curadd[i]));
        }
      }
      for (auto z : g1[i]) {
        if (in[z.id] >= l && in[z.id] <= r) {
          chkmax(ans, z.value(curadd1[i]));
        }
      }
    } else {
      chkmax(ans, kek[i].st[kek[i].uks].value(curadd[i]));
      chkmax(ans, kek1[i].st[kek1[i].uks].value(curadd1[i]));
    }
  }
  return ans;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> q;
  for (int i = 1; i < n; i++) {
    int p;
    cin >> p;
    p--;
    gg[p].push_back(i);
  }
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  for (int i = 0; i < n; i++) {
    cin >> b[i];
  }
  dfs(0);
  for (int i = 0; i < n; i++) {
    in[i]--;
    out[i]--;
  }
  for (int i = 0; i < n; i++) {
    int u = order[i];
    curb[u] = abs(curb[u]);
    g[i >> 8].push_back(Line(curb[u], cura[u] * curb[u], u));
    g1[i >> 8].push_back(Line(curb[u], -cura[u] * curb[u], u));
  }
  for (int i = 0; i <= (n - 1) >> 8; i++) {
    sort((g[i]).begin(), (g[i]).end());
    sort((g1[i]).begin(), (g1[i]).end());
    for (auto z : g[i]) {
      kek[i].addLine(z);
    }
    pushadd(kek[i], 0);
    for (auto z : g1[i]) {
      kek1[i].addLine(z);
    }
    pushadd(kek1[i], 0);
  }
  for (int i = 0; i < q; i++) {
    int t;
    cin >> t;
    if (t == 1) {
      int v, x;
      cin >> v >> x;
      v--;
      add(in[v], out[v], x);
    } else {
      int u;
      cin >> u;
      u--;
      cout << get(in[u], out[u]) << '\n';
    }
  }
  return 0;
}