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 MAXN = 400005;
const int SIZE = 250;
struct Edge {
  int to;
  int nxt;
} edge[MAXN];
struct Line {
  long long k, b;
  int id;
  long long val(long long x) { return k * x + b; }
} c[MAXN];
int n, q, id;
int first[MAXN];
int dfn[MAXN];
int laz[MAXN];
int endfn[MAXN];
int pos[MAXN];
vector<int> conv[MAXN];
bool cmp1(const Line &a, const Line &b) { return a.id < b.id; }
bool cmp2(const Line &a, const Line &b) { return a.k < b.k; }
void addE(int u, int v) {
  edge[++id] = (Edge){v, first[u]};
  first[u] = id;
}
void dfs(int u) {
  dfn[u] = id++;
  for (int i = first[u]; i; i = edge[i].nxt) {
    c[edge[i].to].k += c[u].k;
    c[edge[i].to].b += c[u].b;
    dfs(edge[i].to);
  }
  endfn[u] = id - 1;
}
long double inter(const Line &a, const Line &b) {
  return (long double)(a.b - b.b) / (b.k - a.k);
}
void build(int cur) {
  int l = cur * SIZE, r = cur * SIZE + SIZE - 1;
  laz[cur] = 0;
  conv[cur].clear();
  pos[cur] = 0;
  for (int i = l; i <= r; i++) {
    while (
        conv[cur].size() > 1 &&
        ((c[i].k == c[conv[cur].back()].k && c[i].b > c[conv[cur].back()].b) ||
         (c[i].k != c[conv[cur].back()].k &&
          inter(c[conv[cur][conv[cur].size() - 2]], c[i]) >=
              inter(c[conv[cur].back()], c[i]))))
      conv[cur].pop_back();
    while (conv[cur].size() >= 1 &&
           (c[i].k == c[conv[cur].back()].k && c[i].b > c[conv[cur].back()].b))
      conv[cur].pop_back();
    if (!conv[cur].size() || c[conv[cur].back()].k != c[i].k)
      conv[cur].push_back(i);
  }
}
int main() {
  scanf("%d%d", &n, &q);
  for (int fa, i = 1; i < n; i++) {
    scanf("%d", &fa);
    addE(fa - 1, i);
  }
  id = 0;
  for (int i = 0; i < n; i++) scanf("%lld", &c[i].b);
  for (int i = 0; i < n; i++) scanf("%lld", &c[i].k);
  dfs(0);
  for (int i = n - 1; i >= 0; i--) {
    c[i << 1] = c[i << 1 | 1] = c[i];
    c[i << 1].id = dfn[i] << 1;
    c[i << 1 | 1].id = dfn[i] << 1 | 1;
    c[i << 1 | 1].k *= -1;
  }
  for (int i = 0; i < n; i++) {
    dfn[i] = dfn[i] << 1;
    endfn[i] = endfn[i] << 1 | 1;
  }
  n <<= 1;
  for (int i = 0; i < n; i++) c[i].b = c[i].k * c[i].b;
  sort(c, c + n, cmp1);
  for (int i = 0, j = min(n - 1, SIZE - 1); i < n;
       i = j + 1, j = min(n - 1, j + SIZE)) {
    sort(c + i, c + j + 1, cmp2);
    build(i / SIZE);
  }
  while (q--) {
    int tp, u, v;
    scanf("%d%d", &tp, &u);
    int l = dfn[u - 1], r = endfn[u - 1], L = l / SIZE, R = r / SIZE;
    if (tp == 1) {
      scanf("%d", &v);
      if (L == R) {
        for (int i = L * SIZE; i < min(n, L * SIZE + SIZE); i++)
          c[i].b += c[i].k * (laz[L] + (c[i].id >= l && c[i].id <= r) * v);
        build(L);
        continue;
      }
      for (int i = L * SIZE; i < min(n, L * SIZE + SIZE); i++)
        c[i].b += c[i].k * (laz[L] + (c[i].id >= l) * v);
      build(L);
      for (int i = R * SIZE; i < min(n, R * SIZE + SIZE); i++)
        c[i].b += c[i].k * (laz[R] + (c[i].id <= r) * v);
      build(R);
      for (int i = L + 1; i < R; i++) laz[i] += v;
    } else {
      long long ans = 0;
      if (L == R) {
        for (int i = L * SIZE; i < min(n, L * SIZE + SIZE); i++)
          if (c[i].id >= l && c[i].id <= r) ans = max(ans, c[i].val(laz[L]));
        printf("%lld\n", ans);
        continue;
      }
      for (int i = L * SIZE; i < min(n, L * SIZE + SIZE); i++)
        if (c[i].id >= l) ans = max(ans, c[i].val(laz[L]));
      for (int i = R * SIZE; i < min(n, R * SIZE + SIZE); i++)
        if (c[i].id <= r) ans = max(ans, c[i].val(laz[R]));
      for (int i = L + 1; i < R; i++) {
        while (pos[i] + 1 < conv[i].size() &&
               c[conv[i][pos[i]]].val(laz[i]) <
                   c[conv[i][pos[i] + 1]].val(laz[i]))
          pos[i]++;
        ans = max(ans, c[conv[i][pos[i]]].val(laz[i]));
      }
      printf("%lld\n", ans);
    }
  }
  return 0;
}