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;
void doRoutine() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  srand(322179);
}
bool eq(double x1, double x2) { return abs(x1 - x2) < 1e-9; }
double eval(pair<double, double> line, double x) {
  return line.first * x + line.second;
}
double intersect(pair<double, double> a, pair<double, double> b) {
  return (b.second - a.second) / (a.first - b.first);
}
struct CHT {
  vector<double> points;
  vector<pair<double, double> > lines;
  int ptr = 0;
  void add(long long k, long long b) {
    pair<double, double> line(k, b);
    if (lines.empty()) {
      lines.push_back(line);
    } else {
      if (eq(k, lines.back().first) && b <= lines.back().second) {
        return;
      }
      while (lines.size() >= 2 &&
             eval(line, points.back()) >= eval(lines.back(), points.back())) {
        lines.pop_back();
        points.pop_back();
      }
      points.push_back(intersect(lines.back(), line));
      lines.push_back(line);
    }
  }
  long long get(long long x) {
    while (ptr + 1 < lines.size() && x >= points[ptr]) {
      ++ptr;
    }
    return floor(eval(lines[ptr], x) + 0.5);
  }
};
void dfs_e(int v, int p, vector<int> &e, vector<pair<int, int> > &bounds,
           vector<vector<int> > &g, vector<int> &a, vector<int> &b,
           vector<long long> &c, vector<long long> &d) {
  c[v] = a[v], d[v] = b[v];
  if (p != -1) {
    c[v] += c[p], d[v] += d[p];
  }
  bounds[v].first = e.size();
  e.push_back(v);
  for (auto u : g[v]) {
    dfs_e(u, v, e, bounds, g, a, b, c, d);
  }
  bounds[v].second = e.size();
}
void rebuild_hull(int block, vector<vector<int> > &block_sort, vector<int> &e,
                  vector<long long> &c, vector<long long> &d,
                  vector<CHT> &hulls) {
  hulls[block] = CHT();
  int n = c.size();
  for (int id : block_sort[block]) {
    bool neg = (id >= n);
    id = id % n;
    int v = e[id];
    long long k = d[v], b = d[v] * c[v];
    if (neg) {
      k *= -1;
      b *= -1;
    }
    hulls[block].add(k, b);
  }
}
vector<int> buf;
int bufn;
bool cmp(int i, int j) {
  int vali = 1, valj = 1;
  if (i >= bufn) {
    vali = -1;
    i -= bufn;
  }
  vali *= buf[i];
  if (j >= bufn) {
    valj = -1;
    j -= bufn;
  }
  valj *= buf[j];
  if (vali != valj) {
    return vali < valj;
  } else {
    return i < j;
  }
}
signed main() {
  doRoutine();
  int n, q;
  cin >> n >> q;
  vector<vector<int> > g(n);
  for (int i = 0; i < n - 1; ++i) {
    int p;
    cin >> p;
    --p;
    g[p].push_back(i + 1);
  }
  vector<int> a(n), b(n);
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
  }
  for (int i = 0; i < n; ++i) {
    cin >> b[i];
  }
  vector<int> e;
  vector<pair<int, int> > bounds(n);
  vector<long long> c(n), d(n);
  dfs_e(0, -1, e, bounds, g, a, b, c, d);
  int block_size = 300;
  int sz = (n + block_size - 1) / block_size;
  vector<CHT> hulls(sz);
  vector<int> block_add(sz);
  vector<vector<int> > block_sort(sz);
  for (int i = 0; i < sz; ++i) {
    for (int j = i * block_size; j < (i + 1) * block_size && j < n; ++j) {
      block_sort[i].push_back(j);
      block_sort[i].push_back(j + n);
    }
    buf.resize(n);
    for (int j = 0; j < n; ++j) {
      buf[j] = d[e[j]];
    }
    bufn = n;
    sort(block_sort[i].begin(), block_sort[i].end(), cmp);
    rebuild_hull(i, block_sort, e, c, d, hulls);
  }
  for (int iter = 0; iter < q; ++iter) {
    int dec;
    cin >> dec;
    if (dec == 1) {
      int v, x;
      cin >> v >> x;
      --v;
      int l = bounds[v].first, r = bounds[v].second;
      for (int j = l / block_size + 1; j < (r - 1) / block_size; ++j) {
        block_add[j] += x;
      }
      set<int> rebuild_blocks;
      rebuild_blocks.insert(l / block_size);
      for (int j = l; j < r && j / block_size == l / block_size; ++j) {
        c[e[j]] += x;
      }
      if (!rebuild_blocks.count((r - 1) / block_size)) {
        rebuild_blocks.insert((r - 1) / block_size);
        for (int j = r - 1; j >= l && j / block_size == (r - 1) / block_size;
             --j) {
          c[e[j]] += x;
        }
      }
      for (auto block : rebuild_blocks) {
        for (int i = block * block_size; i < n && i < (block + 1) * block_size;
             ++i) {
          c[e[i]] += block_add[block];
        }
        block_add[block] = 0;
        rebuild_hull(block, block_sort, e, c, d, hulls);
      }
    } else {
      int v;
      cin >> v;
      --v;
      int l = bounds[v].first, r = bounds[v].second;
      const long long INF = 1000000000000000000;
      long long ans = -INF;
      for (int i = l; i < r && i / block_size == l / block_size; ++i) {
        ans = max(ans, abs((c[e[i]] + block_add[i / block_size]) * d[e[i]]));
      }
      for (int i = r - 1; i >= l && i / block_size == (r - 1) / block_size;
           --i) {
        ans = max(ans, abs((c[e[i]] + block_add[i / block_size]) * d[e[i]]));
      }
      for (int j = l / block_size + 1; j < (r - 1) / block_size; ++j) {
        ans = max(ans, hulls[j].get(block_add[j]));
      }
      cout << ans << endl;
    }
  }
  return 0;
}