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 maxn = 200005;
const int B = 600;
int n, m, pos[maxn], L[maxn], R[maxn], id[maxn], fa[maxn], head[maxn], to[maxn],
    nxt[maxn], tot, st[maxn], ed[maxn], tim;
long long _a[maxn], _b[maxn], a[maxn], b[maxn], add[maxn / B + 10];
struct node {
  long long x, y;
  node(long long _x = 0, long long _y = 0) : x(_x), y(_y) {}
  inline bool operator<(const node &a) const {
    return (x == a.x) ? y > a.y : x < a.x;
  }
  inline node operator-(const node &a) const { return node(x - a.x, y - a.y); }
  inline long long cross(const node &a) const { return x * a.y - y * a.x; }
};
struct hull {
  node s[B + 10];
  int n, o, op, len, l, id[B + 10];
  inline node &operator[](int x) { return s[x]; }
  inline const node operator[](int x) const { return s[x]; }
  inline void push(node p) { s[n++] = p; }
  inline bool cmp(const int &a, const int &b) { return s[a] < s[b]; }
  inline void build() {
    o = 0, n = len;
    for (int i = 0; i < n; i++)
      s[i] = node(b[id[i] + l] * (op ? -1 : 1),
                  a[id[i] + l] * b[id[i] + l] * (op ? -1 : 1));
    if (n <= 2) return;
    int top = 1;
    for (int i = 2; i < n; i++) {
      while (top > 0 && (s[top] - s[top - 1]).cross(s[i] - s[top - 1]) >= 0)
        top--;
      s[++top] = s[i];
    }
    n = top + 1;
  }
  inline long long getans(long long k) {
    for (; o < n - 1 && s[o].x * k + s[o].y <= s[o + 1].x * k + s[o + 1].y; o++)
      ;
    return s[o].x * k + s[o].y;
  }
} s[maxn / B + 10][2];
inline void addedge(int x, int y) {
  to[++tot] = y;
  nxt[tot] = head[x];
  head[x] = tot;
}
void dfs(int x) {
  st[x] = ++tim, a[tim] = _a[x], b[tim] = _b[x];
  for (int i = head[x]; i; i = nxt[i])
    _a[to[i]] += _a[x], _b[to[i]] += _b[x], dfs(to[i]);
  ed[x] = tim;
}
inline void update(int l, int r, long long x) {
  int p = pos[l], q = pos[r];
  if (p == q) {
    for (int i = l; i <= r; i++) a[i] += x;
    for (int o = 0; o < 2; o++) s[p][o].build();
    return;
  }
  for (int i = l; i <= R[p]; i++) a[i] += x;
  for (int i = L[q]; i <= r; i++) a[i] += x;
  for (int o = 0; o < 2; o++) s[p][o].build(), s[q][o].build();
  for (int i = p + 1; i < q; i++) add[i] += x;
}
inline long long query(int l, int r) {
  int p = pos[l], q = pos[r];
  long long ans = 0;
  if (p == q) {
    for (int i = l; i <= r; i++) ans = max(ans, abs(a[i] + add[p]) * b[i]);
    return ans;
  }
  for (int i = l; i <= R[p]; i++) ans = max(ans, abs(a[i] + add[p]) * b[i]);
  for (int i = L[q]; i <= r; i++) ans = max(ans, abs(a[i] + add[q]) * b[i]);
  for (int i = p + 1; i < q; i++)
    ans =
        max(ans, max(abs(s[i][0].getans(add[i])), abs(s[i][1].getans(add[i]))));
  return ans;
}
int P, O;
inline bool cmp(const int &a, const int &b) { return s[P][O][a] < s[P][O][b]; }
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 2; i <= n; i++) scanf("%d", &fa[i]), addedge(fa[i], i);
  for (int i = 1; i <= n; i++) scanf("%lld", &_a[i]);
  for (int i = 1; i <= n; i++) scanf("%lld", &_b[i]);
  dfs(1);
  for (int i = 1; i <= n; i++) {
    pos[i] = (i - 1) / B + 1;
    if (pos[i] != pos[i - 1]) L[pos[i]] = i, R[pos[i - 1]] = i - 1;
  }
  R[pos[n]] = n;
  for (int i = 1; i <= n; i++) b[i] = abs(b[i]);
  for (int i = 1; i <= pos[n]; i++) {
    for (int o = 0; o < 2; o++) {
      s[i][o].op = o, s[i][o].len = R[i] - L[i] + 1, s[i][o].l = L[i];
      for (int j = L[i]; j <= R[i]; j++)
        s[i][o].push(node(b[j] * (o ? -1 : 1), a[j] * b[j] * (o ? -1 : 1)));
      for (int j = 0; j < s[i][o].len; j++) s[i][o].id[j] = j;
      P = i, O = o, sort(s[i][o].id, s[i][o].id + s[i][o].len, cmp),
      s[i][o].build();
    }
  }
  int op, x, y;
  while (m--) {
    scanf("%d%d", &op, &x);
    if (op == 1)
      scanf("%d", &y), update(st[x], ed[x], y);
    else
      printf("%lld\n", query(st[x], ed[x]));
  }
  return 0;
}