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;
int n, q, tot, p[200005], st[200005], ed[200005];
vector<int> G[200005];
const int blocks = 300;
long long a[200005], b[200005], c[200005], d[200005], ad[200005];
vector<int> order[200005];
vector<pair<long long, long long> > convex_hull[200005];
bool need[200005];
bool cmp(int x, int y) { return b[x] > b[y]; }
bool check(pair<long long, long long> x, pair<long long, long long> y,
           pair<long long, long long> z) {
  return (long double)1.0 * (z.second - y.second) * (y.first - x.first) <=
         (long double)1.0 * (y.second - x.second) * (z.first - y.first);
}
void dfs(int v) {
  st[v] = ++tot;
  for (auto to : G[v]) {
    b[st[to]] += b[st[v]];
    a[st[to]] += a[st[v]];
    dfs(to);
  }
  ed[v] = tot;
}
void dfs2(int v) {
  for (auto to : G[v]) {
    b[st[to]] += b[st[v]];
    a[st[to]] += a[st[v]];
    dfs2(to);
  }
}
void get_order() {
  for (int i = 1; i <= (n - 1) / blocks + 1; i++) {
    int st = (i - 1) * blocks + 1, ed = min(n, i * blocks);
    for (int j = st; j <= ed; j++) order[i].push_back(j);
    sort(order[i].begin(), order[i].end(), cmp);
  }
}
void add(int id, pair<long long, long long> p) {
  int t = (int)convex_hull[id].size();
  while (t >= 2 && check(convex_hull[id][t - 2], convex_hull[id][t - 1], p)) {
    convex_hull[id].pop_back();
    t--;
  }
  convex_hull[id].push_back(p);
}
void build(int id) {
  convex_hull[id].clear();
  int st = (id - 1) * blocks + 1, ed = min(n, id * blocks);
  if (ad[id]) {
    for (int j = st; j <= ed; j++) {
      c[j] += b[j] * ad[id];
      d[j] -= b[j] * ad[id];
    }
    ad[id] = 0;
  }
  for (int i = 0; i < (int)order[id].size(); i++) {
    pair<long long, long long> p =
        pair<long long, long long>(b[order[id][i]], c[order[id][i]]);
    add(id, p);
  }
  for (int i = (int)order[id].size() - 1; i >= 0; i--) {
    pair<long long, long long> p =
        pair<long long, long long>(-b[order[id][i]], d[order[id][i]]);
    add(id, p);
  }
  int t = (int)convex_hull[id].size();
  while (t >= 2 &&
         convex_hull[id][t - 1].second <= convex_hull[id][t - 2].second) {
    convex_hull[id].pop_back();
    t--;
  }
  need[id] = false;
}
long long query_block(int id) {
  if (need[id]) build(id);
  int t = (int)convex_hull[id].size();
  long long x = ad[id];
  while (t >= 2 &&
         convex_hull[id][t - 1].first * x + convex_hull[id][t - 1].second <=
             convex_hull[id][t - 2].first * x + convex_hull[id][t - 2].second) {
    convex_hull[id].pop_back();
    t--;
  }
  return convex_hull[id][t - 1].first * x + convex_hull[id][t - 1].second;
}
long long query(long long l, long long r) {
  long long ret = 0;
  int id = (l - 1) / blocks + 1;
  while (l <= r && l % blocks != 1) {
    ret = max(ret, -b[l] * ad[id] + d[l]);
    ret = max(ret, b[l] * ad[id] + c[l]);
    l++;
  }
  id = (r - 1) / blocks + 1;
  while (l <= r && r % blocks != 0) {
    ret = max(ret, -b[r] * ad[id] + d[r]);
    ret = max(ret, b[r] * ad[id] + c[r]);
    r--;
  }
  while (l < r) {
    ret = max(ret, query_block((l - 1) / blocks + 1));
    l += blocks;
  }
  return ret;
}
void update(long long l, long long r, long long v) {
  int id = (l - 1) / blocks + 1;
  while (l <= r && l % blocks != 1) {
    d[l] -= v * b[l];
    c[l] += v * b[l];
    need[id] = true;
    l++;
  }
  id = (r - 1) / blocks + 1;
  while (l <= r && r % blocks != 0) {
    d[r] -= v * b[r];
    c[r] += v * b[r];
    need[id] = true;
    r--;
  }
  while (l < r) {
    if (need[(l - 1) / blocks + 1]) build((l - 1) / blocks + 1);
    ad[(l - 1) / blocks + 1] += v;
    l += blocks;
  }
}
int main() {
  scanf("%d%d", &n, &q);
  for (int i = 2; i <= n; i++) {
    scanf("%d", &p[i]);
    G[p[i]].push_back(i);
  }
  dfs(1);
  for (int i = 1; i <= n; i++) scanf("%lld", &a[st[i]]);
  for (int i = 1; i <= n; i++) scanf("%lld", &b[st[i]]);
  dfs2(1);
  for (int i = 1; i <= n; i++) {
    b[i] = max(-b[i], b[i]);
    c[i] = b[i] * a[i];
    d[i] = -c[i];
  }
  get_order();
  for (int i = 1; i <= (n - 1) / blocks + 1; i++) build(i);
  for (int i = 0; i < q; i++) {
    int type, v, x;
    scanf("%d", &type);
    if (type == 1) {
      scanf("%d%d", &v, &x);
      update(st[v], ed[v], x);
    } else {
      scanf("%d", &v);
      printf("%lld\n", query(st[v], ed[v]));
    }
  }
  return 0;
}