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;
const int SQ = 400;
int n, q, p, sq;
vector<int> g[N];
int a[N], b[N], x[N], y[N];
int L[N], R[N], dfs_cnt = 0;
void DFS(int node) {
  L[node] = R[node] = dfs_cnt++;
  a[L[node]] = x[node];
  b[L[node]] = y[node];
  b[L[node]] = abs(b[L[node]]);
  for (int i = 0; i < (int)g[node].size(); i++) {
    x[g[node][i]] += x[node];
    y[g[node][i]] += y[node];
    DFS(g[node][i]);
    R[node] = R[g[node][i]];
  }
}
int inc[N / SQ], mx[N / SQ];
int sz[N / SQ], last[N / SQ];
pair<long long, pair<int, long long> > v[N / SQ][SQ];
pair<int, long long> v2[SQ];
inline long long get(int a1, long long b1, int a2, long long b2) {
  if (a1 == a2) {
    if (b2 >= b1) return -(long long)1e18;
    return (long long)1e18;
  }
  return ((b1 - b2) / (a2 - a1)) +
         ((b1 >= b2 && (abs(b1 - b2) % abs(a2 - a1) != 0)) ? 1 : 0);
}
void build(int idx) {
  int num = 0;
  mx[idx] = -2000000000;
  for (int i = idx * sq; i < n && i < (idx + 1) * sq; i++) {
    a[i] += inc[idx];
    v2[num++] =
        make_pair((a[i] < 0 ? -b[i] : b[i]), abs((long long)a[i] * b[i]));
    if (a[i] < 0) {
      mx[idx] = max(mx[idx], a[i]);
    }
  }
  inc[idx] = last[idx] = 0;
  sort(v2, v2 + num);
  sz[idx] = 0;
  long long cur;
  for (int i = 0; i < num; i++) {
    while (sz[idx] > 0) {
      cur = get(v[idx][sz[idx] - 1].second.first,
                v[idx][sz[idx] - 1].second.second, v2[i].first, v2[i].second);
      if (cur <= v[idx][sz[idx] - 1].first)
        sz[idx]--;
      else
        break;
    }
    if (sz[idx] == 0)
      v[idx][sz[idx]++] = make_pair(-(long long)1e18, v2[i]);
    else
      v[idx][sz[idx]++] = make_pair(cur, v2[i]);
  }
}
inline long long get(int idx) {
  while (last[idx] + 1 < sz[idx] && v[idx][last[idx] + 1].first <= inc[idx])
    last[idx]++;
  return (long long)v[idx][last[idx]].second.first * (long long)inc[idx] +
         v[idx][last[idx]].second.second;
}
long long res = 0;
inline long long getmax(int l, int r) {
  res = -(long long)1e18;
  for (int i = l / sq; i <= r / sq; i++) {
    if (i * sq >= l && min(n - 1, (i + 1) * sq - 1) <= r) {
      res = max(res, get(i));
      continue;
    }
    for (int j = max(i * sq, l); j <= min(r, min(n - 1, (i + 1) * sq - 1)); j++)
      res = max(res, abs((long long)(a[j] + inc[i]) * (long long)b[j]));
  }
  return res;
}
inline void update(int l, int r, int val) {
  for (int i = l / sq; i <= r / sq; i++) {
    if (i * sq >= l && min(n - 1, (i + 1) * sq - 1) <= r) {
      inc[i] += val;
      if (mx[i] + inc[i] >= 0) build(i);
      continue;
    }
    for (int j = max(i * sq, l); j <= min(r, min(n - 1, (i + 1) * sq - 1)); j++)
      a[j] += val;
    build(i);
  }
}
int main() {
  sq = SQ;
  scanf("%d%d", &n, &q);
  for (int i = 2; i <= n; i++) {
    scanf("%d", &p);
    g[p].push_back(i);
  }
  for (int i = 1; i <= n; i++) scanf("%d", &x[i]);
  for (int i = 1; i <= n; i++) scanf("%d", &y[i]);
  DFS(1);
  for (int i = 0; i < n; i += sq) build(i / sq);
  int t, v, x;
  while (q--) {
    scanf("%d", &t);
    if (t == 1) {
      scanf("%d%d", &v, &x);
      update(L[v], R[v], x);
    } else {
      scanf("%d", &v);
      printf("%lld\n", getmax(L[v], R[v]));
    }
  }
  return 0;
}