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 = 200010, blo = 180, Blo = blo + 10, size = N / blo + 10;
int n, m, type, fa[N], dfn[N], low[N], idx;
long long a[N], b[N], ans[N];
vector<int> e[N];
struct P {
  int opt, x, y;
};
P q[N];
long long bw[Blo], mx[Blo];
int id[N], lenb;
int bl[N], lb[size], rb[size];
struct B {
  long long k, b;
  B(long long kk = 0, long long bb = 0) : k(kk), b(bb) {}
  inline long long val(long long x) { return k * x + b; }
  inline bool operator<(const B &yy) const {
    return k == yy.k ? b < yy.b : k < yy.k;
  }
};
B p[size][Blo], sta[Blo];
int len[size], top, pos[size];
long long lz[size], ta[N], tb[N];
template <typename T>
inline T Max(const T &x, const T &y) {
  return x > y ? x : y;
}
template <typename T>
void gi(T &x) {
  x = 0;
  register char c = getchar(), pre = 0;
  for (; c < '0' || c > '9'; pre = c, c = getchar())
    ;
  for (; c >= '0' && c <= '9'; c = getchar()) x = x * 10ll + (c ^ 48);
  if (pre == '-') x = -x;
}
void dfs(int u) {
  dfn[u] = ++idx;
  for (auto v : e[u]) dfs(v);
  low[u] = idx;
}
long long cross(B x, B y) { return (x.b - y.b) / (y.k - x.k); }
bool check(B x, B y, B z) {
  return (y.b - z.b) * (y.k - x.k) <= (x.b - y.b) * (z.k - y.k);
}
void reset(int u) {
  top = len[u] = 0;
  for (int i = (1), ied = (rb[u] - lb[u] + 1); i <= ied; i++) mx[i] = -1e18;
  for (int i = (lb[u]), ied = (rb[u]); i <= ied; i++)
    bw[id[i]] = tb[i], mx[id[i]] = Max(mx[id[i]], ta[i] * tb[i]);
  for (int i = (1), ied = (rb[u] - lb[u] + 1); i <= ied; i++)
    if (mx[i] != -1e18) sta[++top] = B(bw[i], mx[i]);
  for (int i = (1), ied = (top); i <= ied; i++) {
    for (; len[u] > 1 && check(p[u][len[u] - 1], p[u][len[u]], sta[i]);
         --len[u])
      ;
    p[u][++len[u]] = sta[i];
  }
  pos[u] = type ? len[u] : 1;
  for (; pos[u] < len[u] &&
         p[u][pos[u]].val(lz[u]) <= p[u][pos[u] + 1].val(lz[u]);
       ++pos[u])
    ;
  for (; pos[u] > 1 && p[u][pos[u]].val(lz[u]) <= p[u][pos[u] - 1].val(lz[u]);
       --pos[u])
    ;
}
void mdy(int l, int r, long long w) {
  if (bl[l] == bl[r]) {
    for (int i = (l), ied = (r); i <= ied; i++) ta[i] += w;
    reset(bl[l]);
    return;
  }
  for (int i = (l), ied = (rb[bl[l]]); i <= ied; i++) ta[i] += w;
  reset(bl[l]);
  for (int i = (lb[bl[r]]), ied = (r); i <= ied; i++) ta[i] += w;
  reset(bl[r]);
  for (int i = (bl[l] + 1), ied = (bl[r] - 1); i <= ied; i++) lz[i] += w;
}
long long ask(int u) {
  for (; pos[u] < len[u] &&
         p[u][pos[u]].val(lz[u]) <= p[u][pos[u] + 1].val(lz[u]);
       ++pos[u])
    ;
  for (; pos[u] > 1 && p[u][pos[u]].val(lz[u]) <= p[u][pos[u] - 1].val(lz[u]);
       --pos[u])
    ;
  return p[u][pos[u]].val(lz[u]);
}
long long qry(int l, int r) {
  long long res = 0;
  if (bl[l] == bl[r]) {
    for (int i = (l), ied = (r); i <= ied; i++)
      res = Max(res, (ta[i] + lz[bl[l]]) * tb[i]);
    return res;
  }
  for (int i = (l), ied = (rb[bl[l]]); i <= ied; i++)
    res = Max(res, (ta[i] + lz[bl[l]]) * tb[i]);
  for (int i = (lb[bl[r]]), ied = (r); i <= ied; i++)
    res = Max(res, (ta[i] + lz[bl[r]]) * tb[i]);
  for (int i = (bl[l] + 1), ied = (bl[r] - 1); i <= ied; i++)
    res = Max(res, ask(i));
  return res;
}
void solve() {
  for (int i = (1), ied = (n); i <= ied; i++) ta[dfn[i]] = a[i];
  for (int i = (1), ied = (bl[n]); i <= ied; i++) lz[i] = 0, reset(i);
  for (int i = (1), ied = (m); i <= ied; i++) {
    if (q[i].opt == 1)
      mdy(dfn[q[i].x], low[q[i].x], (long long)q[i].y);
    else
      ans[i] = Max(ans[i], qry(dfn[q[i].x], low[q[i].x]));
  }
}
int main() {
  gi(n), gi(m);
  for (int i = (2), ied = (n); i <= ied; i++) gi(fa[i]), e[fa[i]].push_back(i);
  dfs(1);
  for (int i = (1), ied = (n); i <= ied; i++) gi(a[i]);
  for (int i = (1), ied = (n); i <= ied; i++) gi(b[i]);
  for (int i = (2), ied = (n); i <= ied; i++)
    a[i] += a[fa[i]], b[i] += b[fa[i]];
  for (int i = (1), ied = (n); i <= ied; i++)
    if (b[i] < 0) b[i] = -b[i];
  for (int i = (1), ied = (m); i <= ied; i++) {
    gi(q[i].opt), gi(q[i].x);
    if (q[i].opt == 1) gi(q[i].y);
  }
  for (int i = (1), ied = (n); i <= ied; i++) bl[i] = (i - 1) / blo + 1;
  for (int i = (1), ied = (bl[n]); i <= ied; i++)
    lb[i] = rb[i - 1] + 1, rb[i] = i * blo;
  rb[bl[n]] = n;
  for (int i = (1), ied = (n); i <= ied; i++) tb[dfn[i]] = b[i];
  for (int i = (1), ied = (bl[n]); i <= ied; i++) {
    lenb = 0;
    for (int j = (lb[i]), jed = (rb[i]); j <= jed; j++) bw[++lenb] = tb[j];
    sort(bw + 1, bw + lenb + 1), lenb = unique(bw + 1, bw + lenb + 1) - bw - 1;
    for (int j = (lb[i]), jed = (rb[i]); j <= jed; j++)
      id[j] = lower_bound(bw + 1, bw + lenb + 1, tb[j]) - bw;
  }
  solve();
  for (int i = (1), ied = (n); i <= ied; i++) a[i] = -a[i];
  for (int i = (1), ied = (m); i <= ied; i++) q[i].y = -q[i].y;
  type = 1, solve();
  for (int i = (1), ied = (m); i <= ied; i++)
    if (q[i].opt == 2) {
      if (ans[i] == 31743506070688593) ++ans[i];
      printf("%lld\n", ans[i]);
    }
  return 0;
}