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;
template <class t, class u>
void chmax(t& first, u second) {
  if (first < second) first = second;
}
template <class t, class u>
void chmin(t& first, u second) {
  if (second < first) first = second;
}
template <class t>
using vc = vector<t>;
template <class t>
using vvc = vc<vc<t>>;
using pi = pair<int, int>;
using vi = vc<int>;
template <class t, class u>
ostream& operator<<(ostream& os, const pair<t, u>& p) {
  return os << "{" << p.first << "," << p.second << "}";
}
template <class t>
ostream& operator<<(ostream& os, const vc<t>& v) {
  os << "{";
  for (auto e : v) os << e << ",";
  return os << "}";
}
using uint = unsigned;
using ull = unsigned long long;
template <int i, class T>
void print_tuple(ostream&, const T&) {}
template <int i, class T, class H, class... Args>
void print_tuple(ostream& os, const T& t) {
  if (i) os << ",";
  os << get<i>(t);
  print_tuple<i + 1, T, Args...>(os, t);
}
template <class... Args>
ostream& operator<<(ostream& os, const tuple<Args...>& t) {
  os << "{";
  print_tuple<0, tuple<Args...>, Args...>(os, t);
  return os << "}";
}
void print(ll x, int suc = 1) {
  cout << x;
  if (suc == 1) cout << endl;
  if (suc == 2) cout << " ";
}
ll read() {
  ll i;
  cin >> i;
  return i;
}
vi readvi(int n, int off = 0) {
  vi v(n);
  for (int i = int(0); i < int(n); i++) v[i] = read() + off;
  return v;
}
template <class T>
void print(const vector<T>& v, int suc = 1) {
  for (int i = int(0); i < int(v.size()); i++)
    print(v[i], i == int(v.size()) - 1 ? suc : 2);
}
string readString() {
  string s;
  cin >> s;
  return s;
}
template <class T>
T sq(const T& t) {
  return t * t;
}
void yes(bool ex = true) {
  cout << "Yes" << endl;
  if (ex) exit(0);
}
void no(bool ex = true) {
  cout << "No" << endl;
  if (ex) exit(0);
}
constexpr ll ten(int n) { return n == 0 ? 1 : ten(n - 1) * 10; }
const ll infLL = LLONG_MAX / 3;
const int inf = INT_MAX / 2 - 100;
int topbit(signed t) { return t == 0 ? -1 : 31 - __builtin_clz(t); }
int topbit(ll t) { return t == 0 ? -1 : 63 - __builtin_clzll(t); }
int popcount(signed t) { return __builtin_popcount(t); }
int popcount(ll t) { return __builtin_popcountll(t); }
bool ispow2(int i) { return i && (i & -i) == i; }
bool inc(int first, int second, int c) {
  return first <= second && second <= c;
}
template <class t>
void mkuni(vc<t>& v) {
  sort(v.begin(), v.end());
  v.erase(unique(v.begin(), v.end()), v.end());
}
ll rand_int(ll l, ll r) {
  static mt19937 gen(2434);
  return uniform_int_distribution<ll>(l, r)(gen);
}
const int Nmax = 200010;
vi g[Nmax];
int in[Nmax], out[Nmax], as[Nmax], bs[Nmax], ei;
void dfs(int v) {
  in[v] = ei++;
  for (auto to : g[v]) {
    as[to] += as[v];
    bs[to] += bs[v];
    dfs(to);
  }
  out[v] = ei;
}
ll fdiv(ll first, ll second) {
  return first / second - ((first ^ second) < 0 && first % second);
}
struct ln {
  ll first, second;
  ll eval(int x) { return first * x + second; }
};
ll pos(ln x, ln y) { return fdiv(x.second - y.second, y.first - x.first); }
ln buf[Nmax * 2];
struct CHT {
  int l, r;
  void init(int x) { l = r = x; }
  void add(ln first) {
    if (l < r && buf[r - 1].first == first.first) {
      chmax(first.second, buf[r - 1].second);
      r--;
    }
    while (r - l >= 2) {
      ll x = pos(buf[r - 2], buf[r - 1]);
      ll y = pos(buf[r - 1], first);
      if (x < y) break;
      r--;
    }
    buf[r++] = first;
  }
  ll query(int x) {
    while (r - l >= 2) {
      if (buf[l].eval(x) > buf[l + 1].eval(x)) break;
      l++;
    }
    return buf[l].eval(x);
  }
};
signed main() {
  cin.tie(0);
  ios::sync_with_stdio(0);
  cout << fixed << setprecision(20);
  int n;
  cin >> n;
  bool dbg = false;
  if (n == -1) {
    n = 200000;
    dbg = true;
  }
  int q;
  if (dbg)
    q = 100000;
  else
    cin >> q;
  for (int i = int(1); i < int(n); i++) {
    int p;
    if (dbg)
      p = i - 1;
    else
      cin >> p;
    g[p - 1].push_back(i);
  }
  if (dbg) {
    for (int i = int(0); i < int(n); i++) as[i] = rand_int(-5000, 5000);
    for (int i = int(0); i < int(n); i++) bs[i] = rand_int(-5000, 5000);
  } else {
    for (int i = int(0); i < int(n); i++) cin >> as[i];
    for (int i = int(0); i < int(n); i++) cin >> bs[i];
  }
  dfs(0);
  vc<ll> val(2 * n);
  vc<pi> bi;
  for (int i = int(0); i < int(n); i++) {
    val[in[i] * 2] = ll(as[i]) * bs[i];
    bi.emplace_back(bs[i], in[i] * 2);
    val[in[i] * 2 + 1] = ll(as[i]) * (-bs[i]);
    bi.emplace_back(-bs[i], in[i] * 2 + 1);
  }
  sort(bi.begin(), bi.end());
  vc<pi> qs;
  for (int i = int(0); i < int(q); i++) {
    int t, v;
    if (dbg) {
      t = rand_int(1, 2);
      v = rand_int(0, n - 1);
    } else {
      cin >> t >> v;
      v--;
    }
    if (t == 1) {
      int x;
      if (dbg)
        x = rand_int(1, 5000);
      else
        cin >> x;
      qs.emplace_back(v, x);
    } else {
      qs.emplace_back(v, -1);
    }
  }
  void(0);
  const int B = 2000;
  vi cur(n * 2);
  vc<ll> ans;
  for (int i = 0; i < q; i += B) {
    vi pos;
    for (int j = int(i); j < int(min(i + B, q)); j++) {
      pos.push_back(in[qs[j].first] * 2);
      pos.push_back(out[qs[j].first] * 2);
    }
    mkuni(pos);
    int s = pos.size() - 1;
    vc<CHT> cs(s);
    fill(cur.begin(), cur.end(), -1);
    for (int j = int(0); j < int(s); j++) {
      cs[j].init(pos[j]);
      for (int k = int(pos[j]); k < int(pos[j + 1]); k++) cur[k] = j;
    }
    for (auto w : bi) {
      int j = cur[w.second];
      if (j == -1) continue;
      cs[j].add(ln{w.first, val[w.second]});
    }
    vi xs(s);
    for (int j = int(i); j < int(min(i + B, q)); j++) {
      int l = lower_bound(pos.begin(), pos.end(), in[qs[j].first] * 2) -
              pos.begin();
      int r = lower_bound(pos.begin(), pos.end(), out[qs[j].first] * 2) -
              pos.begin();
      if (qs[j].second == -1) {
        ll mx = 0;
        for (int k = int(l); k < int(r); k++) chmax(mx, cs[k].query(xs[k]));
        ans.push_back(mx);
      } else {
        for (int k = int(l); k < int(r); k++) xs[k] += qs[j].second;
      }
    }
    for (auto w : bi) {
      int j = cur[w.second];
      if (j == -1) continue;
      val[w.second] += ll(w.first) * xs[j];
    }
  }
  for (auto v : ans) cout << v << "\n";
}