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 <class T>
bool umin(T& a, T b) {
  if (a > b) {
    a = b;
    return 1;
  }
  return 0;
}
template <class T>
bool umax(T& a, T b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
vector<int> adj[200009];
int in[200009], out[200009], TIM;
int bel[200009], st[200009], en[200009], id[200009];
int p[200009], n, q;
long long A[200009], B[200009], cnt[200009], value[200009], color[200009];
const int BLOK = 222;
bool cmp(int x, int y) { return (color[x] < color[y]); }
bool cmp1(int x, int y) { return (color[x] > color[y]); }
struct CHT {
  vector<long long> m, b;
  vector<int> p;
  int pos;
  double intersection(int l1, int l2) {
    return 1.0 * (b[l1] - b[l2]) / (m[l2] - m[l1]);
  }
  void init(int x, int t) {
    m.clear();
    b.clear();
    pos = 0;
    if (p.empty()) {
      for (int i = st[x]; i <= en[x]; i++) p.push_back(i);
      if (!t)
        sort(p.begin(), p.end(), cmp);
      else
        sort(p.begin(), p.end(), cmp1);
    }
    for (int i = 0; i < p.size(); i++) {
      value[p[i]] += cnt[x];
      if (!t and m.size()) {
        if (m.back() == color[p[i]]) {
          if (value[p[i]] * 1LL * color[p[i]] > b.back())
            b[b.size() - 1] = value[p[i]] * 1LL * color[p[i]];
        } else {
          m.push_back(color[p[i]]);
          b.push_back(value[p[i]] * 1LL * color[p[i]]);
        }
      } else if (t and m.size()) {
        if (m.back() == color[p[i]]) {
          if (value[p[i]] * 1LL * color[p[i]] < b.back())
            b[b.size() - 1] = value[p[i]] * 1LL * color[p[i]];
        } else {
          m.push_back(color[p[i]]);
          b.push_back(value[p[i]] * 1LL * color[p[i]]);
        }
      } else {
        m.push_back(color[p[i]]);
        b.push_back(value[p[i]] * 1LL * color[p[i]]);
      }
      while (m.size() >= 3 and intersection(m.size() - 3, m.size() - 2) >=
                                   intersection(m.size() - 3, m.size() - 1)) {
        m.erase(m.end() - 2);
        b.erase(b.end() - 2);
      }
    }
    cnt[x] = 0;
  }
  long long get(long long x) {
    while (pos + 1 < m.size() and intersection(pos, pos + 1) <= x) pos++;
    return m[pos] * x + b[pos];
  }
} S[2][200009];
int a[200009], b[200009];
void build(int x) {
  for (int i = 0; i < 2; i++) S[i][bel[x]].init(bel[x], i);
}
void dfs(int nd) {
  in[nd] = ++TIM;
  id[TIM] = nd;
  for (int i = 0; i < int(adj[nd].size()); i++) {
    int to = adj[nd][i];
    A[to] = A[nd] + a[to];
    B[to] = B[nd] + b[to];
    dfs(to);
  }
  out[nd] = TIM;
}
void upd(int l, int r, int v) {
  if (bel[l] == bel[r]) {
    for (int i = l; i <= r; i++) value[i] += v;
    build(l);
    return;
  }
  for (int i = l; i <= en[bel[l]]; i++) value[i] += v;
  for (int i = st[bel[r]]; i <= r; i++) value[i] += v;
  build(l);
  build(r);
  for (int i = bel[l] + 1; i < bel[r]; i++) cnt[i] += v;
}
const long long C = 1e18;
long long tap(int l, int r) {
  long long mx = 0, mn = C;
  if (bel[l] == bel[r]) {
    for (int i = l; i <= r; i++) {
      umax(mx, value[i] * 1LL * color[i] + cnt[bel[l]] * 1LL * color[i]);
      umin(mn, value[i] * 1LL * color[i] + cnt[bel[l]] * 1LL * color[i]);
    }
    return max(mx, -mn);
  }
  for (int i = l; i <= en[bel[l]]; i++) {
    umax(mx, value[i] * 1LL * color[i] + cnt[bel[l]] * 1LL * color[i]);
    umin(mn, value[i] * 1LL * color[i] + cnt[bel[l]] * 1LL * color[i]);
  }
  for (int i = st[bel[r]]; i <= r; i++) {
    umax(mx, value[i] * 1LL * color[i] + cnt[bel[r]] * 1LL * color[i]);
    umin(mn, value[i] * 1LL * color[i] + cnt[bel[r]] * 1LL * color[i]);
  }
  for (int i = bel[l] + 1; i < bel[r]; i++) {
    umax(mx, S[0][i].get(cnt[i]));
    umin(mn, S[1][i].get(cnt[i]));
  }
  return max(mx, -mn);
}
int main() {
  scanf("%d%d", &n, &q);
  for (int i = 2; i <= n; i++) {
    int p;
    scanf("%d", &p);
    adj[p].push_back(i);
  }
  for (int i = 1; i <= n; i++) scanf("%d", a + i);
  for (int i = 1; i <= n; i++) scanf("%d", b + i);
  A[1] = a[1];
  B[1] = b[1];
  dfs(1);
  int cur = 1;
  st[1] = 1;
  for (int i = 1; i <= n; i++) {
    color[i] = B[id[i]];
    value[i] = A[id[i]];
    bel[i] = cur;
    if (i % BLOK == 0) {
      en[cur] = i;
      if (i < n) st[++cur] = i + 1;
    }
  }
  if (n % BLOK != 0) en[cur] = n;
  for (int i = 1; i <= cur; i++) build(st[i]);
  while (q--) {
    int t, u;
    scanf("%d%d", &t, &u);
    if (t == 1) {
      int x;
      scanf("%d", &x);
      int l = in[u], r = out[u];
      upd(l, r, x);
    } else
      printf("%lld\n", tap(in[u], out[u]));
  }
  return 0;
}