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 std::cin;
using std::cout;
const int maxn = 200200;
const long long inf = 1e18;
struct fc {
  int k;
  long long a;
};
int n, q;
fc o[maxn];
int a[maxn], b[maxn];
struct seg {
  static const int N = maxn << 2;
  fc max[N];
  long long rem[N], add[N];
  inline long long calc(const fc& x, const fc& y) {
    if (x.k >= y.k) return inf;
    return (x.a - y.a) / (y.k - x.k) + 1;
  }
  inline void update(int cur) {
    rem[cur] = std::min(rem[cur << 1], rem[cur << 1 | 1]);
    if (max[cur << 1].a > max[cur << 1 | 1].a) {
      max[cur] = max[cur << 1];
      rem[cur] = std::min(rem[cur], calc(max[cur << 1], max[cur << 1 | 1]));
    } else {
      max[cur] = max[cur << 1 | 1];
      rem[cur] = std::min(rem[cur], calc(max[cur << 1 | 1], max[cur << 1]));
    }
  }
  inline void put(int cur, long long v) {
    add[cur] += v;
    rem[cur] -= v;
    max[cur].a += max[cur].k * v;
  }
  inline void down(int cur) {
    put(cur << 1, add[cur]);
    put(cur << 1 | 1, add[cur]);
    add[cur] = 0;
  }
  inline void dfs(int cur) {
    if (rem[cur] > 0) return;
    down(cur);
    dfs(cur << 1), dfs(cur << 1 | 1);
    update(cur);
  }
  inline void upt(int ql, int qr, int v, int cur = 1, int l = 1, int r = n) {
    if (ql <= l && r <= qr) {
      put(cur, v);
      return;
    }
    int mid = l + r >> 1;
    down(cur);
    if (ql <= mid) upt(ql, qr, v, cur << 1, l, mid);
    if (mid < qr) upt(ql, qr, v, cur << 1 | 1, mid + 1, r);
    update(cur);
  }
  inline long long qmax(int ql, int qr, int cur = 1, int l = 1, int r = n) {
    if (ql <= l && r <= qr) {
      if (rem[cur] <= 0) dfs(cur);
      return max[cur].a;
    }
    int mid = l + r >> 1;
    long long ret = -1e18;
    down(cur);
    if (ql <= mid) ret = std::max(ret, qmax(ql, qr, cur << 1, l, mid));
    if (mid < qr) ret = std::max(ret, qmax(ql, qr, cur << 1 | 1, mid + 1, r));
    update(cur);
    return ret;
  }
  inline void build(int cur = 1, int l = 1, int r = n) {
    if (l == r) {
      max[cur] = o[l];
      rem[cur] = inf;
      return;
    }
    int mid = l + r >> 1;
    build(cur << 1, l, mid);
    build(cur << 1 | 1, mid + 1, r);
    update(cur);
  }
} seg0, seg1;
int head[maxn], next[maxn], size[maxn], dfn[maxn], tot;
inline void add(int fa, int x) { next[x] = head[fa], head[fa] = x; }
inline void dfs0(int x, int sa, int sb) {
  sa += a[x], sb += b[x];
  size[x] = 1;
  dfn[x] = ++tot;
  o[dfn[x]] = (fc){std::abs(sb), (long long)sa * std::abs(sb)};
  for (int i = head[x]; i; i = next[i]) {
    dfs0(i, sa, sb), size[x] += size[i];
  }
}
int main() {
  std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  cin >> n >> q;
  for (int i = (2), iend = (n); i <= iend; ++i) {
    int f;
    cin >> f;
    add(f, i);
  }
  for (int i = (1), iend = (n); i <= iend; ++i) {
    cin >> a[i];
  }
  for (int i = (1), iend = (n); i <= iend; ++i) {
    cin >> b[i];
  }
  dfs0(1, 0, 0);
  seg0.build();
  for (int i = (1), iend = (n); i <= iend; ++i) {
    o[i].a = -o[i].a;
    o[i].k = -o[i].k;
  }
  seg1.build();
  for (int i = (1), iend = (q); i <= iend; ++i) {
    int opt, x, v;
    cin >> opt >> x;
    if (opt == 1) {
      cin >> v;
      seg0.upt(dfn[x], dfn[x] + size[x] - 1, v);
      seg1.upt(dfn[x], dfn[x] + size[x] - 1, v);
    } else {
      long long a0 = seg0.qmax(dfn[x], dfn[x] + size[x] - 1);
      long long a1 = seg1.qmax(dfn[x], dfn[x] + size[x] - 1);
      cout << std::max(a0, a1) << '\n';
    }
  }
}