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 = 200005, BLK = 200;
struct edge {
  int to, next;
} e[N * 2];
int head[N], tot, n, Q;
int dfn[N], ed[N], a[N], b[N];
int A[N], B[N], fa[N];
struct Line {
  long long k, b;
  long long F(long long x) { return k * x + b; }
};
bool cmp(Line a, Line b, Line c) {
  if (b.k == c.k) return b.b < c.b;
  long long ins1 = (a.b - b.b) / (b.k - a.k);
  long long ins2 = (a.b - c.b) / (c.k - a.k);
  if ((b.k - a.k) * ins1 < a.b - b.b) ++ins1;
  if ((c.k - a.k) * ins2 < a.b - c.b) ++ins2;
  return ins1 >= ins2;
}
struct BLOCK {
  int L, R, len, tp, vad, pos, tg;
  int va[BLK + 5], vb[BLK + 5], id[BLK + 5];
  Line q[BLK + 5];
  void build_que() {
    vad = 1 << 30;
    tp = 0;
    pos = 1;
    for (int i = (int)(len); i >= (int)(1); i--)
      if (va[id[i]] < 0) {
        int x = id[i];
        vad = min(vad, -va[x]);
        Line tmp = (Line){-vb[x], -1ll * va[x] * vb[x]};
        for (; tp && q[tp].k == tmp.k; tmp.b = max(tmp.b, q[tp--].b))
          ;
        for (; tp > 1 && cmp(q[tp - 1], q[tp], tmp); --tp)
          ;
        q[++tp] = tmp;
      }
    for (int i = (int)(1); i <= (int)(len); i++)
      if (va[id[i]] >= 0) {
        int x = id[i];
        Line tmp = (Line){vb[x], 1ll * va[x] * vb[x]};
        for (; tp && q[tp].k == tmp.k; tmp.b = max(tmp.b, q[tp--].b))
          ;
        for (; tp > 1 && cmp(q[tp - 1], q[tp], tmp); --tp)
          ;
        q[++tp] = tmp;
      }
  }
  void build() {
    len = R - L + 1;
    for (int i = (int)(L); i <= (int)(R); i++) va[i - L + 1] = A[i];
    for (int i = (int)(L); i <= (int)(R); i++) vb[i - L + 1] = abs(B[i]);
    for (int i = (int)(1); i <= (int)(len); i++) id[i] = i;
    for (int i = (int)(1); i <= (int)(len); i++)
      for (int j = (int)(i + 1); j <= (int)(len); j++)
        if (vb[id[i]] > vb[id[j]]) swap(id[i], id[j]);
    build_que();
  }
  void change(int l, int r, int v) {
    if (l == -1)
      l = 1;
    else
      l = l - L + 1;
    if (r == -1)
      r = len;
    else
      r = r - L + 1;
    for (int i = (int)(1); i <= (int)(len); i++) va[i] += tg;
    for (int i = (int)(l); i <= (int)(r); i++) va[i] += v;
    tg = 0;
    build_que();
  }
  void change(int v) {
    if ((tg += v) > vad) change(-1, -1, 0);
  }
  long long ask() {
    for (; pos != tp && q[pos].F(tg) < q[pos + 1].F(tg); ++pos)
      ;
    return q[pos].F(tg);
  }
  long long ask(int l, int r) {
    if (l == -1)
      l = 1;
    else
      l = l - L + 1;
    if (r == -1)
      r = len;
    else
      r = r - L + 1;
    long long ans = 0;
    for (int i = (int)(l); i <= (int)(r); i++)
      ans = max(ans, 1ll * abs(va[i] + tg) * vb[i]);
    return ans;
  }
} BL[1005];
void add(int x, int y) {
  e[++tot] = (edge){y, head[x]};
  head[x] = tot;
}
void dfs(int x) {
  dfn[x] = ++*dfn;
  A[*dfn] = a[x];
  B[*dfn] = b[x];
  for (int i = head[x]; i; i = e[i].next) {
    a[e[i].to] += a[x];
    b[e[i].to] += b[x];
    dfs(e[i].to);
  }
  ed[x] = *dfn;
}
void change(int l, int r, int v) {
  int bl = (l - 1) / BLK + 1;
  int br = (r - 1) / BLK + 1;
  if (bl == br)
    BL[bl].change(l, r, v);
  else {
    BL[bl].change(l, -1, v);
    BL[br].change(-1, r, v);
    for (int i = (int)(bl + 1); i <= (int)(br - 1); i++) BL[i].change(v);
  }
}
long long ask(int l, int r) {
  long long ans = 0;
  int bl = (l - 1) / BLK + 1;
  int br = (r - 1) / BLK + 1;
  if (bl == br)
    ans = max(ans, BL[bl].ask(l, r));
  else {
    ans = max(ans, BL[bl].ask(l, -1));
    ans = max(ans, BL[br].ask(-1, r));
    for (int i = (int)(bl + 1); i <= (int)(br - 1); i++)
      ans = max(ans, BL[i].ask());
  }
  return ans;
}
int main() {
  scanf("%d%d", &n, &Q);
  for (int i = (int)(2); i <= (int)(n); i++) {
    scanf("%d", &fa[i]);
    add(fa[i], i);
  }
  for (int i = (int)(1); i <= (int)(n); i++) scanf("%d", &a[i]);
  for (int i = (int)(1); i <= (int)(n); i++) scanf("%d", &b[i]);
  dfs(1);
  int cnt = (n - 1) / BLK + 1;
  for (int i = (int)(1); i <= (int)(cnt); i++) {
    BL[i].L = (i - 1) * BLK + 1;
    BL[i].R = min(n, i * BLK);
    BL[i].build();
  }
  while (Q--) {
    int tp, x, y;
    scanf("%d%d", &tp, &x);
    if (tp == 1) {
      scanf("%d", &y);
      change(dfn[x], ed[x], y);
    } else
      printf("%lld\n", ask(dfn[x], ed[x]));
  }
}