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 kN = 2e5 + 10;
const long long kInf = 1e18 + 10;
int n, q;
long long a[kN], b[kN];
vector<int> g[kN];
int in[kN], out[kN], dfs_clock;
pair<long long, long long> p1[kN], p2[kN];
void dfs(int u) {
  in[u] = ++dfs_clock;
  for (int v : g[u]) {
    a[v] += a[u], b[v] += b[u];
    dfs(v);
  }
  out[u] = dfs_clock;
}
struct SegmentTree {
  pair<long long, long long> pos[kN << 2];
  struct Node {
    long long a, b;
    long long wait, tg;
  };
  Node seg[kN << 2];
  void init(pair<long long, long long> *a) {
    for (int i = 1; i <= n; i++) pos[i] = a[i];
  }
  void push_down(int o) {
    if (seg[o].tg == 0) return;
    seg[(o << 1)].tg += seg[o].tg, seg[(o << 1 | 1)].tg += seg[o].tg;
    seg[(o << 1)].wait -= seg[o].tg, seg[(o << 1 | 1)].wait -= seg[o].tg;
    seg[(o << 1)].a += seg[o].tg, seg[(o << 1 | 1)].a += seg[o].tg;
    seg[o].tg = 0;
  }
  void push_up(int o) {
    long long a1 = seg[(o << 1)].a, b1 = seg[(o << 1)].b;
    long long a2 = seg[(o << 1 | 1)].a, b2 = seg[(o << 1 | 1)].b;
    if (a1 * b1 > a2 * b2)
      seg[o].a = a1, seg[o].b = b1;
    else
      seg[o].a = a2, seg[o].b = b2;
    seg[o].wait = min(seg[(o << 1)].wait, seg[(o << 1 | 1)].wait);
    if (b1 != b2) {
      long long tmp = (a2 * b2 - a1 * b1) / (b1 - b2);
      if (tmp >= 0) seg[o].wait = min(seg[o].wait, tmp);
    }
  }
  void build(int l = 1, int r = n, int o = 1) {
    if (l == r) {
      seg[o] = {pos[l].first, pos[l].second, kInf, 0};
      return;
    }
    int m = (l + r) >> 1;
    build(l, m, (o << 1)), build(m + 1, r, (o << 1 | 1));
    push_up(o);
  }
  void update(int ql, int qr, int x, int l = 1, int r = n, int o = 1) {
    if (ql > r || qr < l) return;
    if (ql <= l && r <= qr && seg[o].wait >= x) {
      seg[o].tg += x, seg[o].wait -= x, seg[o].a += x;
      return;
    }
    push_down(o);
    int m = (l + r) >> 1;
    if (ql <= m) update(ql, qr, x, l, m, (o << 1));
    if (qr > m) update(ql, qr, x, m + 1, r, (o << 1 | 1));
    push_up(o);
  }
  long long query(int ql, int qr, int l = 1, int r = n, int o = 1) {
    if (ql > r || qr < l) return -kInf;
    if (ql <= l && r <= qr) return seg[o].a * seg[o].b;
    push_down(o);
    int m = (l + r) >> 1;
    return max(query(ql, qr, l, m, (o << 1)),
               query(ql, qr, m + 1, r, (o << 1 | 1)));
  }
};
SegmentTree t1, t2;
int main() {
  scanf("%d%d", &n, &q);
  for (int i = 2, x; i <= n; i++) {
    scanf("%d", &x);
    g[x].push_back(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++) {
    p1[in[i]] = {a[i], b[i]}, p2[in[i]] = {a[i], -b[i]};
  }
  t1.init(p1), t2.init(p2);
  t1.build(), t2.build();
  while (q--) {
    int op, v;
    scanf("%d%d", &op, &v);
    if (op == 1) {
      int x;
      scanf("%d", &x);
      t1.update(in[v], out[v], x);
      t2.update(in[v], out[v], x);
    } else {
      printf("%lld\n", max(t1.query(in[v], out[v]), t2.query(in[v], out[v])));
    }
  }
  return 0;
}