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 double inf = 1e15;
int n, q, cnt = -1;
int fir[200000], to[200000];
int nxt[200000], id[200000];
int sz[200000], pos[200000];
int vala[200000], valb[200000];
inline void add(int a, int b) {
  to[++cnt] = b;
  nxt[cnt] = fir[a];
  fir[a] = cnt;
  return;
}
void dfs(int i) {
  id[i] = ++cnt;
  sz[i] = 1;
  for (int j = fir[i]; j != -1; j = nxt[j]) {
    valb[to[j]] += valb[i];
    vala[to[j]] += vala[i];
    dfs(to[j]);
    sz[i] += sz[to[j]];
  }
  return;
}
int bsize, bcnt;
struct line {
  int k, id;
  long long int b;
};
inline bool comp1(line l1, line l2) { return l1.k < l2.k; }
inline bool comp2(line l1, line l2) { return l1.k > l2.k; }
struct Block {
  int now1, now2, st, ed, top1, top2, delta, size;
  line p1[220], p2[220], s1[220], s2[220];
  inline long long int getans1(int x) {
    return (long long int)s1[x].k * delta + s1[x].b;
  }
  inline long long int getans2(int x) {
    return (long long int)s2[x].k * delta + s2[x].b;
  }
  inline void upd(void) {
    while (now1 < top1 && getans1(now1) < getans1(now1 + 1)) now1++;
    while (now2 < top2 && getans2(now2) > getans2(now2 + 1)) now2++;
    return;
  }
  inline long long int ipoint(line l1, line l2) {
    return 1.0 * (l2.b - l1.b) / (l1.k - l2.k);
  }
  inline bool out1(line l) {
    if (s1[top1].k == l.k) return s1[top1].b <= l.b;
    return ipoint(s1[top1], s1[top1 - 1]) > ipoint(s1[top1], l);
  }
  inline bool out2(line l) {
    if (s2[top2].k == l.k) return s2[top2].b >= l.b;
    return ipoint(s2[top2], s2[top2 - 1]) > ipoint(s2[top2], l);
  }
  inline void rebuild(void) {
    top1 = top2 = -1;
    for (int i = 0; i < size; i++) {
      p1[i].b += (long long int)p1[i].k * delta;
      p2[i].b += (long long int)p2[i].k * delta;
      while (top1 > 0 && out1(p1[i])) top1--;
      while (top2 > 0 && out2(p2[i])) top2--;
      if (top1 == -1 || s1[top1].k != p1[i].k) s1[++top1] = p1[i];
      if (top2 == -1 || s2[top2].k != p2[i].k) s2[++top2] = p2[i];
    }
    now1 = now2 = delta = 0;
    upd();
    return;
  }
  void init(void) {
    size = bsize;
    ed = st + size - 1;
    if (ed >= n) {
      ed = n - 1;
      size = ed - st + 1;
    }
    for (int i = st; i <= ed; i++) {
      p1[i - st].k = p2[i - st].k = valb[pos[i]];
      p1[i - st].b = p2[i - st].b = (long long int)vala[pos[i]] * valb[pos[i]];
      p1[i - st].id = p2[i - st].id = i;
    }
    sort(p1, p1 + size, comp1);
    sort(p2, p2 + size, comp2);
    delta = 0;
    rebuild();
    return;
  }
  void update(int l, int r, int x) {
    if (l > ed || r < st) return;
    if (l <= st && ed <= r) {
      delta += x;
      upd();
    } else {
      for (int i = 0; i < size; i++) {
        if (l <= p1[i].id && p1[i].id <= r)
          p1[i].b += (long long int)x * p1[i].k;
        if (l <= p2[i].id && p2[i].id <= r)
          p2[i].b += (long long int)x * p2[i].k;
      }
      rebuild();
    }
    return;
  }
  long long int query(int l, int r) {
    if (l > ed || r < st) return -inf;
    long long int res = 0;
    if (l <= st && ed <= r) {
      res = (long long int)s1[now1].k * delta + s1[now1].b;
      return max(res, (long long int)-s2[now2].k * delta - s2[now2].b);
    }
    for (int i = 0; i < size; i++) {
      if (l <= p1[i].id && p1[i].id <= r)
        res = max(res, (long long int)p1[i].k * delta + p1[i].b);
      if (l <= p2[i].id && p2[i].id <= r)
        res = max(res, (long long int)-p2[i].k * delta - p2[i].b);
    }
    return res;
  }
} block[1100];
void read(void) {
  scanf("%d%d", &n, &q);
  for (int i = 0; i < n; i++) fir[i] = -1;
  int fa;
  for (int i = 1; i < n; i++) {
    scanf("%d", &fa);
    add(fa - 1, i);
  }
  for (int i = 0; i < n; i++) scanf("%d", &vala[i]);
  for (int i = 0; i < n; i++) scanf("%d", &valb[i]);
  return;
}
int main(void) {
  read();
  cnt = -1;
  dfs(0);
  for (int i = 0; i < n; i++) {
    if (valb[i] < 0) valb[i] *= -1;
    pos[id[i]] = i;
  }
  bsize = max(1, (int)sqrt(n / 6));
  bcnt = (n + bsize - 1) / bsize;
  for (int i = 0; i < bcnt; i++) {
    block[i].st = bsize * i;
    block[i].init();
  }
  int opt, x, y;
  while (q--) {
    scanf("%d%d", &opt, &x);
    x--;
    if (opt == 1) {
      scanf("%d", &y);
      for (int i = 0; i < bcnt; i++)
        block[i].update(id[x], id[x] + sz[x] - 1, y);
    } else {
      long long int res = 0;
      for (int i = 0; i < bcnt; i++)
        res = max(res, block[i].query(id[x], id[x] + sz[x] - 1));
      printf("%lld\n", res);
    }
  }
  return 0;
}