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;
using ll = long long;
const int maxn = 2e5 + 5;
const int BLK = 220;
int n, q;
int tin[maxn], tout[maxn];
ll a[maxn], b[maxn];
vector<int> adj[maxn];
int t = 0;
void DFS(int i) {
  tin[i] = t++;
  for (int j : adj[i]) {
    DFS(j);
  }
  tout[i] = t - 1;
}
struct FN {
  ll m, b;
  FN(ll _m, ll _b) : m(_m), b(_b) {}
  ll eval(ll x) const { return m * x + b; }
  long double intersect(const FN& r) const {
    return (long double)(r.b - b) / (long double)(m - r.m);
  }
  friend bool comp(const FN& l1, const FN& l2, const FN& l) {
    long double x1 = l1.intersect(l);
    long double x2 = l1.intersect(l2);
    return x1 <= x2;
  }
};
struct Hull : public deque<FN> {
  void add(const FN& l) {
    while (this->size() >= 2 &&
           comp((*this)[this->size() - 2], (*this)[this->size() - 1], l)) {
      this->pop_back();
    }
    this->push_back(l);
  }
  ll query(ll x) {
    while (this->size() >= 2 && (*this)[1].eval(x) >= (*this)[0].eval(x)) {
      this->pop_front();
    }
    assert(!this->empty());
    return (*this)[0].eval(x);
  }
};
int bucket[maxn];
struct Block {
  ll x = 0;
  ll start;
  vector<int> indices, pos;
  vector<pair<ll, ll>> ps;
  Hull hull;
  void setup() {
    sort(indices.begin(), indices.end(),
         [](int x, int y) { return b[x] < b[y]; });
    pos.resize(indices.size());
    for (int i = 0; i < indices.size(); i++) {
      pos[indices[i] - start] = i;
    }
    ps.resize(2 * indices.size());
    refresh();
  }
  void refresh() {
    hull.clear();
    int pt = 0;
    for (int i : indices) {
      int p = pos[i - start];
      ps[p + indices.size()] = {b[i], a[i] * b[i]};
      ps[indices.size() - p - 1] = {-b[i], -a[i] * b[i]};
    }
    ll currSlope = -1e18;
    ll maxB = -1e18;
    for (int i = 0; i < ps.size(); i++) {
      if (ps[i].first != currSlope) {
        if (currSlope != -1e18) {
          hull.add(FN(currSlope, maxB));
        }
        currSlope = ps[i].first;
        maxB = ps[i].second;
      } else {
        maxB = max(maxB, ps[i].second);
      }
    }
    hull.add(FN(currSlope, maxB));
  }
  ll getmax() { return hull.query(x); }
} blocks[maxn];
void ADD(int l, int r, int x) {
  int orig = l;
  while (l != 0 && bucket[l] == bucket[l - 1] && l <= r) {
    a[l] += x;
    l++;
  }
  if (l - 1 >= 0) blocks[bucket[l - 1]].refresh();
  while (l <= r && bucket[l] != bucket[r]) {
    blocks[bucket[l]].x += x;
    l += BLK;
  }
  while (l <= r) {
    a[l] += x;
    l++;
  }
  if (bucket[orig] != bucket[r]) blocks[bucket[r]].refresh();
}
ll QUERY(int l, int r) {
  ll res = 0;
  while (l != 0 && bucket[l] == bucket[l - 1] && l <= r) {
    res = max(res, abs((a[l] + blocks[bucket[l]].x) * b[l]));
    l++;
  }
  while (l <= r && bucket[l] != bucket[r]) {
    res = max(res, blocks[bucket[l]].getmax());
    l += BLK;
  }
  while (l <= r) {
    res = max(res, abs((a[l] + blocks[bucket[l]].x) * b[l]));
    l++;
  }
  return res;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> n >> q;
  for (int i = 2; i <= n; i++) {
    int pi;
    cin >> pi;
    adj[pi].push_back(i);
  }
  DFS(1);
  for (int i = 1; i <= n; i++) {
    int ai;
    cin >> ai;
    a[tin[i]] += ai;
    a[tout[i] + 1] -= ai;
  }
  for (int i = 1; i <= n; i++) {
    int bi;
    cin >> bi;
    b[tin[i]] += bi;
    b[tout[i] + 1] -= bi;
  }
  for (int i = 1; i <= n; i++) {
    a[i] += a[i - 1];
    b[i] += b[i - 1];
  }
  for (int i = 0; i < n; i++) {
    b[i] = abs(b[i]);
  }
  for (int i = 0; i < n; i++) {
    bucket[i] = i / BLK;
    blocks[bucket[i]].indices.push_back(i);
    if (i == 0 || bucket[i] != bucket[i - 1]) {
      blocks[bucket[i]].start = i;
    }
  }
  for (int i = 0; i <= bucket[n - 1]; i++) {
    blocks[i].setup();
  }
  while (q--) {
    int t, v;
    cin >> t >> v;
    if (t == 1) {
      int x;
      cin >> x;
      ADD(tin[v], tout[v], x);
    } else {
      cout << QUERY(tin[v], tout[v]) << endl;
    }
  }
}