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>
#pragma GCC optimize("O3")
using namespace std;
const long long mod7 = 1000000007LL;
inline long long getint() {
  long long _x = 0, _tmp = 1;
  char _tc = getchar();
  while ((_tc < '0' || _tc > '9') && _tc != '-') _tc = getchar();
  if (_tc == '-') _tc = getchar(), _tmp = -1;
  while (_tc >= '0' && _tc <= '9') _x *= 10, _x += (_tc - '0'), _tc = getchar();
  return _x * _tmp;
}
inline long long add(long long _x, long long _y, long long _mod = mod7) {
  _x += _y;
  return _x >= _mod ? _x - _mod : _x;
}
inline long long sub(long long _x, long long _y, long long _mod = mod7) {
  _x -= _y;
  return _x < 0 ? _x + _mod : _x;
}
inline long long mul(long long _x, long long _y, long long _mod = mod7) {
  _x *= _y;
  return _x >= _mod ? _x % _mod : _x;
}
long long mypow(long long _a, long long _x, long long _mod) {
  if (_x == 0) return 1ll;
  long long _ret = mypow(mul(_a, _a, _mod), _x >> 1, _mod);
  if (_x & 1) _ret = mul(_ret, _a, _mod);
  return _ret;
}
long long mymul(long long _a, long long _x, long long _mod) {
  if (_x == 0) return 0ll;
  long long _ret = mymul(add(_a, _a, _mod), _x >> 1, _mod);
  if (_x & 1) _ret = add(_ret, _a, _mod);
  return _ret;
}
void sleep(double sec = 1021) {
  clock_t s = clock();
  while (clock() - s < CLOCKS_PER_SEC * sec)
    ;
}
int __ = 1, _cs;
template <typename T>
void dbg(T x, string s = "") {}
const int mxN = 2e5, B = 200, mxNB = (mxN - 1) / B + 1;
int n, q, p[mxN], dt, ds[mxN], de[mxN];
long long a[mxN + 1], b[mxN + 1];
vector<int> c[mxN];
void dfs(int u = 0) {
  ds[u] = dt++;
  for (int v : c[u]) dfs(v);
  de[u] = dt;
}
struct cht {
  long long a[B], b[B];
  int qh, qt = 0, p[B];
  void al(long long ai, long long bi) {
    if (qt && a[qt - 1] == ai) {
      if (bi < b[qt - 1]) return;
      --qt;
    }
    while (qt > 1 &&
           (long double)(b[qt - 1] - b[qt - 2]) / (a[qt - 2] - a[qt - 1]) >=
               (long double)(bi - b[qt - 1]) / (a[qt - 1] - ai))
      --qt;
    a[qt] = ai;
    b[qt] = bi;
    ++qt;
  }
  long long qry(long long x) {
    while (qh + 1 < qt && a[qh + 1] * x + b[qh + 1] > a[qh] * x + b[qh]) ++qh;
    return a[qh] * x + b[qh];
  }
  void bld(vector<pair<long long, long long>> &v) {
    qh = qt = 0;
    for (int i = 0; i < v.size(); ++i) al(v[p[i]].first, v[p[i]].second);
  }
};
struct ds {
  long long a[mxN], b[mxN], lz[mxNB];
  cht c[mxNB];
  void psh(int i) {
    for (int j = i * B; j < min((i + 1) * B, n); ++j) a[j] += lz[i];
    lz[i] = 0;
  }
  void cmb(int i) {
    vector<pair<long long, long long>> vl;
    for (int j = i * B; j < min((i + 1) * B, n); ++j)
      vl.push_back(pair<long long, long long>(b[j], a[j] * b[j]));
    if (!c[i].qt) {
      iota(c[i].p, c[i].p + min(B, n - i * B), 0);
      sort(c[i].p, c[i].p + min(B, n - i * B), [&](const int &i, const int &j) {
        return vl[i].first < vl[j].first;
      });
    }
    c[i].bld(vl);
  }
  void upd(int l1, int r1, int x) {
    for (int i = l1 / B; i <= r1 / B; ++i) {
      int l2 = i * B, r2 = (i + 1) * B - 1;
      if (l1 <= l2 && r2 <= r1) {
        lz[i] += x;
      } else {
        psh(i);
        l2 = max(l1, l2);
        r2 = min(r1, r2);
        for (int j = l2; j <= r2; ++j) a[j] += x;
        cmb(i);
      }
    }
  }
  long long qry(int l1, int r1) {
    long long r = 0;
    for (int i = l1 / B; i <= r1 / B; ++i) {
      int l2 = i * B, r2 = (i + 1) * B - 1;
      if (l1 <= l2 && r2 <= r1) {
        r = max(r, c[i].qry(lz[i]));
      } else {
        l2 = max(l1, l2);
        r2 = min(r1, r2);
        for (int j = l2; j <= r2; ++j) r = max(r, (a[j] + lz[i]) * b[j]);
      }
    }
    return r;
  }
} dx, dn;
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> q;
  for (int i = 1; i < n; ++i) {
    cin >> p[i], --p[i];
    c[p[i]].push_back(i);
  }
  dfs();
  for (int i = 0; i < n; ++i) {
    int ai;
    cin >> ai;
    a[ds[i]] += ai;
    a[de[i]] -= ai;
  }
  for (int i = 0; i < n; ++i) {
    int bi;
    cin >> bi;
    b[ds[i]] += bi;
    b[de[i]] -= bi;
  }
  for (int i = 0; i < n; ++i) {
    a[i + 1] += a[i];
    b[i + 1] += b[i];
    dbg(a[i], "a[i]");
    dbg(b[i], "b[i]");
    int c = 1;
    dx.a[i] = dn.a[i] = a[i];
    dx.b[i] = b[i];
    dn.b[i] = -b[i];
  }
  for (int i = 0; i * B < n; ++i) {
    dx.cmb(i);
    dn.cmb(i);
  }
  while (q--) {
    int qt;
    cin >> qt;
    if (qt == 1) {
      int v, x;
      cin >> v >> x, --v;
      dx.upd(ds[v], de[v] - 1, x);
      dn.upd(ds[v], de[v] - 1, x);
    } else {
      int v;
      cin >> v, --v;
      cout << max(dx.qry(ds[v], de[v] - 1), dn.qry(ds[v], de[v] - 1)) << "\n";
    }
  }
}