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>
int inp() {
  char c = getchar();
  int neg = 1;
  while (c < '0' || c > '9') {
    if (c == '-') neg = -1;
    c = getchar();
  }
  int sum = 0;
  while (c >= '0' && c <= '9') {
    sum = sum * 10 + c - '0';
    c = getchar();
  }
  return sum * neg;
}
int head[200010], nxt[200010], end[200010], dfn[200010], size[200010];
long long a2[200010], b2[200010], a[200010], b[200010];
int cou = 0;
void link(int a, int b) {
  nxt[++cou] = head[a];
  head[a] = cou;
  end[cou] = b;
}
struct Node {
  long long k;
  long long b;
  long long get(int x) { return x * k + b; }
};
bool cmp(Node a, Node b) { return a.k < b.k; }
struct Convex {
  std::vector<Node> s;
  void insert(Node x) {
    while (
        s.size() > 1 &&
        ((s[s.size() - 1].b - x.b) * (s[s.size() - 1].k - s[s.size() - 2].k) <=
         (s[s.size() - 2].b - s[s.size() - 1].b) * (x.k - s[s.size() - 1].k)))
      s.resize(s.size() - 1);
    s.push_back(x);
  }
  long long query(long long x) {
    if (s.size() == 0) return -1e18;
    int l = 0;
    int r = s.size() - 1;
    while (l < r) {
      int mid = (l + r) >> 1;
      if (s[mid].get(x) <= s[mid + 1].get(x))
        l = mid + 1;
      else
        r = mid;
    }
    return s[l].get(x);
  }
  void clear() { s.clear(); }
} c[1000], cf[1000];
int ql[1000], qr[1000];
long long delta[1000];
std::vector<Node> vec;
void rebuild(int x) {
  vec.clear();
  c[x].clear();
  cf[x].clear();
  for (int i = ql[x]; i <= qr[x]; i++) {
    a[i] += delta[x];
    vec.push_back((Node){b[i], a[i] * b[i]});
  }
  std::sort(vec.begin(), vec.end(), cmp);
  for (int i = 0; i < vec.size(); i++) c[x].insert(vec[i]);
  for (int i = 0; i < vec.size(); i++)
    cf[x].insert((Node){vec[i].k, -vec[i].b});
  delta[x] = 0;
}
int idx = 0;
void dfs(int cur) {
  dfn[cur] = ++idx;
  size[cur] = 1;
  for (int x = head[cur]; x != -1; x = nxt[x]) {
    a[end[x]] += a[cur];
    b[end[x]] += b[cur];
    dfs(end[x]);
    size[cur] += size[end[x]];
  }
}
int main() {
  memset(head, -1, sizeof(head));
  int n = inp();
  int q = inp();
  for (int i = 2; i <= n; i++) {
    int fa = inp();
    link(fa, i);
  }
  for (int i = 1; i <= n; i++) a[i] = inp();
  for (int i = 1; i <= n; i++) b[i] = inp();
  dfs(1);
  memcpy(a2, a, sizeof(a));
  memcpy(b2, b, sizeof(b));
  for (int i = 1; i <= n; i++) {
    a[dfn[i]] = a2[i];
    b[dfn[i]] = abs(b2[i]);
  }
  qr[0] = 0;
  int cur = 1;
  while (qr[cur - 1] < n) {
    ql[cur] = qr[cur - 1] + 1;
    qr[cur] = ql[cur] + 250 - 1;
    cur++;
  }
  qr[cur - 1] = n;
  for (int i = 1; i < cur; i++) rebuild(i);
  while (q--) {
    int op = inp();
    if (op == 1) {
      int v = inp();
      long long x = inp();
      int l = dfn[v];
      int r = dfn[v] + size[v] - 1;
      int lb = (l - 1) / 250 + 1;
      int rb = (r - 1) / 250 + 1;
      if (lb == rb) {
        for (int i = l; i <= r; i++) a[i] += x;
        rebuild(lb);
      } else {
        for (int i = lb + 1; i < rb; i++) delta[i] += x;
        for (int i = l; i <= qr[lb]; i++) a[i] += x;
        for (int i = ql[rb]; i <= r; i++) a[i] += x;
        rebuild(lb);
        rebuild(rb);
      }
    } else {
      int v = inp();
      int l = dfn[v];
      int r = dfn[v] + size[v] - 1;
      int lb = (l - 1) / 250 + 1;
      int rb = (r - 1) / 250 + 1;
      long long ans = -1e18;
      if (lb == rb) {
        for (int i = l; i <= r; i++)
          ans = std::max(ans, abs(a[i] + delta[lb]) * b[i]);
      } else {
        for (int i = lb + 1; i < rb; i++) {
          ans = std::max(ans, c[i].query(delta[i]));
          ans = std::max(ans, cf[i].query(-delta[i]));
        }
        for (int i = l; i <= qr[lb]; i++)
          ans = std::max(ans, abs(a[i] + delta[lb]) * b[i]);
        for (int i = ql[rb]; i <= r; i++)
          ans = std::max(ans, abs(a[i] + delta[rb]) * b[i]);
      }
      printf("%lld\n", ans);
    }
  }
}