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;
struct line {
  long long k, b;
  line(long long K = 0, long long b1 = 0) : k(K), b(b1) {}
  bool operator<(const line a) const { return k < a.k; }
  line operator-(void) { return line(k, -b); }
};
inline bool cmp(line a, line b, line c) {
  return ((long double)(b.b - c.b) * (b.k - a.k) <=
          (long double)(a.b - b.b) * (c.k - b.k));
}
inline long long X(line a, long long x) { return a.k * x + a.b; }
struct convex {
  vector<line> v;
  void insert(line x) {
    int p = v.size();
    for (--p; p > 0 && cmp(v[p - 1], v[p], x); --p, v.pop_back())
      ;
    v.push_back(x);
  }
  long long qry(long long x) {
    if (v.empty()) return -1e18;
    int l = 0, r = v.size() - 1;
    while (l < r) {
      int m = (l + r) >> 1;
      if (X(v[m], x) <= X(v[m + 1], x))
        l = m + 1;
      else
        r = m;
    }
    return X(v[l], x);
  }
};
vector<line> s;
long long a[200010], b[200010];
struct block {
  convex f, g;
  int l, r;
  long long tag;
  block() { l = 1e8; }
  void build() {
    s.clear();
    f.v.clear();
    g.v.clear();
    for (int i = l; i <= r; i++)
      a[i] += tag, s.push_back(line(b[i], a[i] * b[i]));
    tag = 0;
    sort(s.begin(), s.end());
    for (auto u : s) f.insert(u);
    for (auto u : s) g.insert(-u);
  }
  long long qry() { return max(f.qry(tag), g.qry(-tag)); }
  void upd(int l0, int r0, long long val) {
    for (int i = l0; i <= r0; i++) a[i] = a[i] + val;
    build();
  }
  long long qry(int l0, int r0) {
    long long ans = 0;
    for (int i = l0; i <= r0; i++) ans = max(ans, llabs(a[i] + tag) * b[i]);
    return ans;
  }
} c[(200010 / 220 + 2)];
int bl[200010], fa[200010];
vector<int> g[200010];
int l[200010], r[200010], nid;
long long ta[200010], tb[200010];
void dfs(int u) {
  l[u] = ++nid;
  for (int v : g[u]) ta[v] += ta[u], tb[v] += tb[u], dfs(v);
  r[u] = nid;
}
int main() {
  int n, q;
  scanf("%d%d", &n, &q);
  for (int i = 2; i <= n; i++) scanf("%d", &fa[i]), g[fa[i]].push_back(i);
  for (int i = 1; i <= n; i++) scanf("%lld", &ta[i]);
  for (int i = 1; i <= n; i++) scanf("%lld", &tb[i]);
  dfs(1);
  for (int i = 1; i <= n; i++) a[l[i]] = ta[i], b[l[i]] = llabs(tb[i]);
  for (int i = 1; i <= n; i++)
    bl[i] = i / 220, c[bl[i]].l = min(c[bl[i]].l, i),
    c[bl[i]].r = max(c[bl[i]].r, i);
  int m = bl[n];
  for (int i = 0; i <= m; i++) c[i].build();
  while (q-- > 0) {
    int opt, x;
    long long y;
    scanf("%d%d", &opt, &x);
    if (opt == 1) {
      scanf("%lld", &y);
      int fl = bl[l[x]], fr = bl[r[x]];
      if (fl == fr)
        c[fl].upd(l[x], r[x], y);
      else {
        c[fl].upd(l[x], c[fl].r, y);
        c[fr].upd(c[fr].l, r[x], y);
        for (int i = fl + 1; i < fr; i++) c[i].tag += y;
      }
    } else {
      int fl = bl[l[x]], fr = bl[r[x]];
      if (fl == fr)
        printf("%lld\n", c[fl].qry(l[x], r[x]));
      else {
        long long ans = max(c[fl].qry(l[x], c[fl].r), c[fr].qry(c[fr].l, r[x]));
        for (int i = fl + 1; i < fr; i++) ans = max(ans, c[i].qry());
        printf("%lld\n", ans);
      }
    }
  }
  return 0;
}