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;
const int N = 4e5 + 7;
vector<int> v[N];
int n, m, tot, l[N], r[N], fa[N], dfn[N];
long long a[N], b[N], va[N], vb[N];
namespace sub1 {
long long k[N << 2], y[N << 2], tg[N << 2], rem[N << 2];
inline long long calc(int u, int t) {
  if (k[u] == k[t]) return 1e18;
  return (max(y[u], y[t]) - min(y[u], y[t])) /
         (max(k[u], k[t]) - min(k[u], k[t]));
}
inline void update(int u) {
  rem[u] = min(rem[u << 1], rem[u << 1 | 1]);
  if (y[u << 1] > y[u << 1 | 1])
    y[u] = y[u << 1], k[u] = k[u << 1];
  else
    y[u] = y[u << 1 | 1], k[u] = k[u << 1 | 1];
  if (y[u << 1] > y[u << 1 | 1] && k[u << 1] > k[u << 1 | 1]) return;
  if (y[u << 1] < y[u << 1 | 1] && k[u << 1] < k[u << 1 | 1]) return;
  rem[u] = min(rem[u], calc(u << 1, u << 1 | 1));
}
inline void build(int l, int r, int t) {
  if (l == r) {
    y[t] = va[l], k[t] = vb[l], rem[t] = 1e18;
    return;
  }
  int d = (l + r) >> 1;
  build(l, d, t << 1), build(d + 1, r, t << 1 | 1), update(t);
}
inline void pushdown(int t) {
  if (tg[t]) {
    y[t << 1] = y[t << 1] + k[t << 1] * tg[t], tg[t << 1] += tg[t],
           rem[t << 1] -= tg[t];
    y[t << 1 | 1] = y[t << 1 | 1] + k[t << 1 | 1] * tg[t],
               tg[t << 1 | 1] += tg[t], rem[t << 1 | 1] -= tg[t], tg[t] = 0;
  }
}
inline void dfs(int l, int r, int t) {
  if (rem[t] > 0) return;
  pushdown(t);
  int d = (l + r) >> 1;
  dfs(l, d, t << 1), dfs(d + 1, r, t << 1 | 1), update(t);
}
inline void addit(int ql, int qr, int l, int r, int t, int c) {
  if (ql == l && qr == r) {
    tg[t] += c, y[t] = y[t] + k[t] * c, rem[t] -= c;
    if (rem[t] < 0) dfs(l, r, t);
    return;
  }
  pushdown(t);
  int d = (l + r) >> 1;
  if (ql <= d) addit(ql, min(qr, d), l, d, t << 1, c);
  if (d + 1 <= qr) addit(max(d + 1, ql), qr, d + 1, r, t << 1 | 1, c);
  update(t);
}
inline long long getnum(int ql, int qr, int l, int r, int t) {
  pushdown(t);
  if (ql == l && qr == r) return y[t];
  int d = (l + r) >> 1;
  long long ans = -1e18;
  if (ql <= d) ans = max(ans, getnum(ql, min(qr, d), l, d, t << 1));
  if (d + 1 <= qr)
    ans = max(ans, getnum(max(d + 1, ql), qr, d + 1, r, t << 1 | 1));
  return ans;
}
}  // namespace sub1
namespace sub2 {
long long k[N << 2], y[N << 2], tg[N << 2], rem[N << 2];
inline long long calc(int u, int t) {
  if (k[u] == k[t]) return 1e18;
  return (max(y[u], y[t]) - min(y[u], y[t])) /
         (max(k[u], k[t]) - min(k[u], k[t]));
}
inline void update(int u) {
  rem[u] = min(rem[u << 1], rem[u << 1 | 1]);
  if (y[u << 1] > y[u << 1 | 1])
    y[u] = y[u << 1], k[u] = k[u << 1];
  else
    y[u] = y[u << 1 | 1], k[u] = k[u << 1 | 1];
  if (y[u << 1] > y[u << 1 | 1] && k[u << 1] > k[u << 1 | 1]) return;
  if (y[u << 1] < y[u << 1 | 1] && k[u << 1] < k[u << 1 | 1]) return;
  rem[u] = min(rem[u], calc(u << 1, u << 1 | 1));
}
inline void build(int l, int r, int t) {
  if (l == r) {
    y[t] = -va[l], k[t] = -vb[l], rem[t] = 1e18;
    return;
  }
  int d = (l + r) >> 1;
  build(l, d, t << 1), build(d + 1, r, t << 1 | 1), update(t);
}
inline void pushdown(int t) {
  if (tg[t]) {
    y[t << 1] = y[t << 1] + k[t << 1] * tg[t], tg[t << 1] += tg[t],
           rem[t << 1] -= tg[t];
    y[t << 1 | 1] = y[t << 1 | 1] + k[t << 1 | 1] * tg[t],
               tg[t << 1 | 1] += tg[t], rem[t << 1 | 1] -= tg[t], tg[t] = 0;
  }
}
inline void dfs(int l, int r, int t) {
  if (rem[t] > 0) return;
  pushdown(t);
  int d = (l + r) >> 1;
  dfs(l, d, t << 1), dfs(d + 1, r, t << 1 | 1), update(t);
}
inline void addit(int ql, int qr, int l, int r, int t, int c) {
  if (ql == l && qr == r) {
    tg[t] += c, y[t] = y[t] + k[t] * c, rem[t] -= c;
    if (rem[t] < 0) dfs(l, r, t);
    return;
  }
  pushdown(t);
  int d = (l + r) >> 1;
  if (ql <= d) addit(ql, min(qr, d), l, d, t << 1, c);
  if (d + 1 <= qr) addit(max(d + 1, ql), qr, d + 1, r, t << 1 | 1, c);
  update(t);
}
inline long long getnum(int ql, int qr, int l, int r, int t) {
  pushdown(t);
  if (ql == l && qr == r) return y[t];
  int d = (l + r) >> 1;
  long long ans = -1e18;
  if (ql <= d) ans = max(ans, getnum(ql, min(qr, d), l, d, t << 1));
  if (d + 1 <= qr)
    ans = max(ans, getnum(max(d + 1, ql), qr, d + 1, r, t << 1 | 1));
  return ans;
}
}  // namespace sub2
inline int read() {
  int num = 0;
  char g = getchar(), t = '+';
  while (g < 48 || 57 < g) t = g, g = getchar();
  while (47 < g && g < 58)
    num = (num << 1) + (num << 3) + g - 48, g = getchar();
  if (t == '-') return -num;
  return num;
}
inline void search(int u) {
  dfn[u] = ++tot, va[tot] = a[u] * abs(b[u]), vb[tot] = abs(b[u]),
  l[u] = r[u] = tot;
  for (int i = 0; i < v[u].size(); i++)
    a[v[u][i]] += a[u], b[v[u][i]] += b[u], search(v[u][i]), r[u] = r[v[u][i]];
}
int main() {
  n = read(), m = read();
  int op, u, t;
  for (int i = 2; i <= n; i++) fa[i] = read(), v[fa[i]].push_back(i);
  for (int i = 1; i <= n; i++) a[i] = read();
  for (int i = 1; i <= n; i++) b[i] = read();
  search(1), sub1::build(1, n, 1), sub2::build(1, n, 1);
  while (m--) {
    op = read();
    if (op == 1) {
      u = read(), t = read(), sub1::addit(l[u], r[u], 1, n, 1, t),
      sub2::addit(l[u], r[u], 1, n, 1, t);
    } else {
      u = read(), printf("%lld\n", max(sub1::getnum(l[u], r[u], 1, n, 1),
                                       sub2::getnum(l[u], r[u], 1, n, 1)));
    }
  }
  return 0;
}