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 = 400009, BLOCK = 400, BLOCK_NUM = MAXN / BLOCK + 10;
long long A[MAXN], B[MAXN];
int N, Q;
int tour[MAXN], from[MAXN], to[MAXN];
int mapp[MAXN];
pair<long long, long long> pnts[MAXN];
int ptr[BLOCK_NUM], sz[BLOCK_NUM];
long long inc[BLOCK_NUM];
vector<int> G[MAXN];
bool bad(pair<long long, long long> p0, pair<long long, long long> p1,
         pair<long long, long long> p2) {
  return 1.0L * (p1.first - p0.first) * (p2.second - p0.second) -
             1.0L * (p2.first - p0.first) * (p1.second - p0.second) >=
         0;
}
long long val(int i, long long x) { return pnts[i].first * x + pnts[i].second; }
void build(int k) {
  int l = k * BLOCK, r = min((k + 1) * BLOCK, N) - 1;
  for (int i = l; i <= r; ++i) A[i] += inc[k];
  inc[k] = 0;
  ptr[k] = sz[k] = 0;
  for (int i = l; i <= r; ++i) {
    pair<long long, long long> p(B[mapp[i]], A[mapp[i]] * B[mapp[i]]);
    while (sz[k] > 1 && bad(pnts[l + sz[k] - 2], pnts[l + sz[k] - 1], p))
      --sz[k];
    pnts[l + (sz[k]++)] = p;
  }
}
long long get(int k) {
  int l = k * BLOCK;
  ptr[k] = min(ptr[k], sz[k] - 1);
  while (ptr[k] < sz[k] - 1 &&
         val(l + ptr[k], inc[k]) < val(l + ptr[k] + 1, inc[k]))
    ++ptr[k];
  return val(l + ptr[k], inc[k]);
}
void dfs(int u) {
  static int timer = 0;
  from[u] = timer++;
  for (auto &v : G[u]) dfs(v);
  to[u] = timer;
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  scanf("%d %d", &N, &Q);
  for (int v = 2; v <= N; ++v) {
    int u;
    scanf("%d", &u);
    G[u].push_back(v);
  }
  dfs(1);
  for (int u = 1; u <= N; ++u) {
    int first;
    scanf("%d", &first);
    A[from[u] << 1] += first, A[to[u] << 1] -= first;
  }
  for (int u = 1; u <= N; ++u) {
    int second;
    scanf("%d", &second);
    B[from[u] << 1] += second, B[to[u] << 1] -= second;
  }
  for (int i = 2; i < 2 * N; i += 2) A[i] += A[i - 2], B[i] += B[i - 2];
  for (int i = 1; i < 2 * N; i += 2) A[i] = A[i - 1], B[i] = -B[i - 1];
  N *= 2;
  for (int i = 0; i <= N - 1; ++i) mapp[i] = i;
  for (int l = 0; l < N; l += BLOCK) {
    sort(mapp + l, mapp + min(N, l + BLOCK),
         [&](int x, int y) { return B[x] < B[y]; });
    build(l / BLOCK);
  }
  for (int _ = 0; _ <= Q - 1; ++_) {
    int type, v, x;
    scanf("%d %d", &type, &v);
    int lo = from[v] * 2, hi = to[v] * 2 - 1;
    int lo_k = lo / BLOCK, hi_k = hi / BLOCK;
    int lo_r = lo_k * BLOCK + BLOCK - 1, hi_l = hi_k * BLOCK;
    if (type == 1) {
      scanf("%d", &x);
      if (lo_k == hi_k) {
        for (int i = lo; i <= hi; ++i) A[i] += x;
        build(lo_k);
        continue;
      }
      assert(lo_r < hi_l);
      for (int i = lo; i <= lo_r; ++i) A[i] += x;
      build(lo_k);
      for (int k = lo_k + 1; k <= hi_k - 1; ++k) inc[k] += x;
      for (int i = hi_l; i <= hi; ++i) A[i] += x;
      build(hi_k);
    } else {
      long long ans = 0;
      if (lo_k == hi_k) {
        for (int i = lo; i <= hi; ++i)
          ans = max(ans, (A[i] + inc[lo_k]) * B[i]);
        printf("%I64d\n", ans);
        continue;
      }
      assert(lo_r < hi_l);
      for (int i = lo; i <= lo_r; ++i)
        ans = max(ans, (A[i] + inc[lo_k]) * B[i]);
      for (int i = hi_l; i <= hi; ++i)
        ans = max(ans, (A[i] + inc[hi_k]) * B[i]);
      for (int k = lo_k + 1; k <= hi_k - 1; ++k) ans = max(ans, get(k));
      printf("%I64d\n", ans);
    }
  }
  return 0;
}