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 = 400200;
const int64_t INF = 2e18;
struct Node {
  int64_t a, b, wait, lazy;
  void add(int64_t x) { a += x, wait -= x, lazy += x; }
} tree[MAXN << 2];
int64_t A[MAXN], B[MAXN];
int N, Q;
int tour[MAXN], from[MAXN], to[MAXN];
vector<int> G[MAXN];
void push(int root) {
  tree[(root << 1)].add(tree[root].lazy),
      tree[(root << 1 | 1)].add(tree[root].lazy);
  tree[root].lazy = 0;
}
void pull(int root) {
  int64_t a1 = tree[(root << 1)].a, a2 = tree[(root << 1 | 1)].a,
          b1 = tree[(root << 1)].b, b2 = tree[(root << 1 | 1)].b;
  if (a1 * b1 > a2 * b2 || (a1 * b1 == a2 * b2 && b1 > b2))
    swap(a1, a2), swap(b1, b2);
  tree[root] = {a2, b2, min(tree[(root << 1)].wait, tree[(root << 1 | 1)].wait),
                0};
  if (b1 > b2) {
    tree[root].wait = min(tree[root].wait, (a2 * b2 - a1 * b1) / (b1 - b2));
  }
}
void build(int root = 1, int lo = 0, int hi = 2 * N) {
  if (lo + 1 == hi) {
    int64_t a = A[lo >> 1];
    tree[root] = {A[lo >> 1], ((lo & 1) ? 1 : -1) * B[lo >> 1], INF, 0};
    return;
  }
  build((root << 1), lo, ((lo + hi) >> 1));
  build((root << 1 | 1), ((lo + hi) >> 1), hi);
  pull(root);
}
void update(int64_t x, int l, int r, int root = 1, int lo = 0, int hi = 2 * N) {
  if (hi <= l || r <= lo) return;
  if (l <= lo && hi <= r && tree[root].wait > tree[root].lazy + x) {
    tree[root].add(x);
  } else {
    push(root);
    update(x, l, r, (root << 1), lo, ((lo + hi) >> 1));
    update(x, l, r, (root << 1 | 1), ((lo + hi) >> 1), hi);
    pull(root);
  }
}
int64_t get(int l, int r, int root = 1, int lo = 0, int hi = 2 * N) {
  if (hi <= l || r <= lo) return -INF;
  if (l <= lo && hi <= r) return tree[root].a * tree[root].b;
  push(root);
  return max(get(l, r, (root << 1), lo, ((lo + hi) >> 1)),
             get(l, r, (root << 1 | 1), ((lo + hi) >> 1), hi));
}
void dfs(int u) {
  static int cur = 0;
  from[u] = cur++;
  for (auto &v : G[u]) dfs(v);
  to[u] = cur;
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  scanf("%d %d", &N, &Q);
  for (int u = 2; u <= N; ++u) {
    int v;
    scanf("%d", &v);
    G[v].push_back(u);
  }
  dfs(1);
  for (int u = 1; u <= N; ++u) {
    int64_t a;
    scanf("%I64d", &a);
    A[from[u]] += a, A[to[u]] -= a;
  }
  for (int u = 1; u <= N; ++u) {
    int64_t b;
    scanf("%I64d", &b);
    B[from[u]] += b, B[to[u]] -= b;
  }
  for (int u = 1; u <= N; ++u) A[u] += A[u - 1], B[u] += B[u - 1];
  build();
  for (int _ = 1; _ <= Q; ++_) {
    int type;
    scanf("%d", &type);
    if (type == 1) {
      int v;
      int64_t x;
      scanf("%d %I64d", &v, &x);
      update(x, from[v] << 1, to[v] << 1);
    } else {
      int v;
      scanf("%d", &v);
      printf("%I64d\n", get(from[v] << 1, to[v] << 1));
    }
  }
  return 0;
}