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 SZ = 150;
vector<int> g[200005];
int a[200005], b[200005];
long long A[200005], B[200005];
int S[200005], E[200005], ti = -1;
const long long INF = (long long)2e18;
struct Line {
  long long k, b;
  Line() {}
  Line(long long k, long long b) : k(k), b(b) {}
  long long eval(long long x) const { return k * 1LL * x + b; }
};
bool cmp(Line a, Line b) {
  if (a.k == b.k) return a.b > b.b;
  return a.k < b.k;
}
long long div_up(long long x, long long y) {
  if (y < 0) {
    x = -x;
    y = -y;
  }
  if (x < 0) {
    return x / y;
  } else {
    return (x + y - 1) / y;
  }
}
long long intersect(const Line &u, const Line &v) {
  return div_up(u.b - v.b, v.k - u.k);
}
struct CHT {
  int ptr;
  vector<long long> points;
  vector<Line> lines;
  CHT() {}
  void init() {
    points.clear();
    lines.clear();
  }
  CHT(vector<Line> &what) {
    ptr = 0;
    long long lastk = -1e18;
    for (Line &l : what) {
      if (l.k == lastk) continue;
      while (!points.empty() && points.back() >= intersect(lines.back(), l)) {
        points.pop_back();
        lines.pop_back();
      }
      if (!lines.empty()) {
        points.push_back(intersect(lines.back(), l));
      }
      lines.push_back(l);
      lastk = l.k;
    }
  }
  long long get(long long x) {
    if (lines.empty()) {
      return INF;
    }
    while (ptr < (int)points.size() && points[ptr] <= x) {
      ptr++;
    }
    return lines[ptr].eval(x);
  }
} dp[200000 / SZ + 10];
void dfs(int u, int p, long long suma, long long sumb) {
  S[u] = ++ti;
  suma += a[u];
  sumb += b[u];
  A[S[u]] = suma;
  B[S[u]] = sumb;
  for (int i = 0; i < (int)(g[u]).size(); i++) {
    int v = g[u][i];
    if (v != p) dfs(v, u, suma, sumb);
  }
  E[u] = ti;
}
int l[200000 / SZ + 10], r[200000 / SZ + 10];
long long tmp[200000 / SZ + 10];
vector<Line> Li[200000 / SZ + 10];
int main() {
  int n, q;
  scanf("%d%d", &n, &q);
  for (int i = 1; i < n; i++) {
    int p;
    scanf("%d", &p);
    p--;
    g[p].emplace_back(i);
    g[i].emplace_back(p);
  }
  for (int i = 0; i < n; i++) scanf("%d", &a[i]);
  for (int i = 0; i < n; i++) scanf("%d", &b[i]);
  dfs(0, 0, 0, 0);
  memset(l, -1, sizeof(l));
  memset(r, -1, sizeof(r));
  int m = 0;
  for (int j = 0; j < n; j++) {
    int i = j / SZ;
    if (A[j] < 0) {
      Li[i].emplace_back(Line{-abs(B[j]), abs(A[j]) * 1ll * abs(B[j])});
      Li[i].emplace_back(Line{abs(B[j]), -abs(A[j]) * 1ll * abs(B[j])});
    } else {
      Li[i].emplace_back(Line{abs(B[j]), abs(A[j]) * 1ll * abs(B[j])});
    }
    if (l[i] == -1) l[i] = j;
    r[i] = j;
    m = max(m, i);
  }
  for (int i = 0; i <= m; i++) {
    sort((Li[i]).begin(), (Li[i]).end(), cmp);
    dp[i] = Li[i];
  }
  for (int i = 0; i < q; i++) {
    int t;
    scanf("%d", &t);
    if (t == 1) {
      int v, x;
      scanf("%d%d", &v, &x);
      v--;
      int left = S[v] / SZ, right = min(m, E[v] / SZ + 1);
      for (int i = left; i <= right; i++) {
        if (S[v] <= l[i] && r[i] <= E[v]) {
          tmp[i] += x;
        } else if (S[v] <= r[i] && l[i] <= E[v]) {
          dp[i].init();
          for (int j = l[i]; j <= r[i]; j++) A[j] += tmp[i];
          tmp[i] = 0;
          int L = max(S[v], l[i]), R = min(E[v], r[i]);
          for (int j = L; j <= R; j++) A[j] += x;
          Li[i].clear();
          for (int j = l[i]; j <= r[i]; j++) {
            if (A[j] < 0) {
              Li[i].emplace_back(Line{-abs(B[j]), abs(A[j]) * 1ll * abs(B[j])});
              Li[i].emplace_back(Line{abs(B[j]), -abs(A[j]) * 1ll * abs(B[j])});
            } else {
              Li[i].emplace_back(Line{abs(B[j]), abs(A[j]) * 1ll * abs(B[j])});
            }
          }
          sort((Li[i]).begin(), (Li[i]).end(), cmp);
          dp[i] = Li[i];
        }
      }
    } else {
      int v;
      scanf("%d", &v);
      v--;
      int left = S[v] / SZ, right = min(m, E[v] / SZ + 1);
      long long ans = 0;
      for (int i = left; i <= right; i++) {
        if (S[v] <= l[i] && r[i] <= E[v]) {
          ans = max(ans, dp[i].get(tmp[i]));
        } else if (S[v] <= r[i] && l[i] <= E[v]) {
          int L = max(S[v], l[i]), R = min(E[v], r[i]);
          for (int j = L; j <= R; j++) {
            ans = max(ans, abs(A[j] + tmp[i]) * 1ll * abs(B[j]));
          }
        }
      }
      printf("%lld\n", ans);
    }
  }
}