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;
using ld = long double;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
const ld pi = acos(0) * 2;
template <typename T>
inline void read(T &x) {
  char c;
  bool nega = 0;
  while ((!isdigit(c = getchar())) && (c != '-'))
    ;
  if (c == '-') {
    nega = 1;
    c = getchar();
  }
  x = c - 48;
  while (isdigit(c = getchar())) x = x * 10 + c - 48;
  if (nega) x = -x;
}
template <typename T>
inline void writep(T x) {
  if (x > 9) writep(x / 10);
  putchar(x % 10 + 48);
}
template <typename T>
inline void write(T x) {
  if (x < 0) {
    putchar('-');
    x = -x;
  }
  writep(x);
}
template <typename T>
inline void writeln(T x) {
  write(x);
  putchar('\n');
}
template <typename CT, typename T>
inline void reset_container(CT &c, int sz, T v) {
  c.resize(sz);
  for (auto &x : c) x = v;
}
int n, q;
vector<int> g[200001];
int first[200001];
int last[200001];
ll ra[200001];
ll rb[200001];
ll a[200001];
ll b[200001];
int cnt = 0;
void dfs(int u) {
  cnt++;
  first[u] = cnt;
  a[cnt] = ra[u];
  b[cnt] = abs(rb[u]);
  for (int v : g[u]) {
    rb[v] += rb[u];
    ra[v] += ra[u];
    dfs(v);
  }
  last[u] = cnt;
}
class line {
 public:
  ll a, b;
  line(ll a, ll b) : a(a), b(b) {}
  ll at(ll x) { return a * x + b; }
  ll first_less(line L) {
    ll x = (b - L.b) / (L.a - a);
    while ((L.a - a) * x < (b - L.b)) x++;
    return x;
  }
  bool operator==(line P) { return (a == P.a) && (b == P.b); }
};
const int sz = 401;
class CHT {
 public:
  vector<line> L;
  vector<pair<ll, line>> F;
  ll get(ll x) {
    int low = 0, high = F.size() - 1, mid, res;
    while (low <= high) {
      mid = (low + high) / 2;
      if (F[mid].first <= x) {
        res = mid;
        low = mid + 1;
      } else
        high = mid - 1;
    }
    return F[res].second.at(x);
  }
  void build() {
    sort(L.begin(), L.end(), [](line A, line B) {
      return (A.a < B.a) || (A.a == B.a && A.b > B.b);
    });
    for (auto l : L) {
      while ((!F.empty()) &&
             (l.at(F.back().first) >= F.back().second.at(F.back().first)))
        F.pop_back();
      if (F.empty())
        F.push_back(make_pair(0, l));
      else {
        if ((F.back().second.a == l.a) && (F.back().second.b >= l.b)) continue;
        ll nx = F.back().second.first_less(l);
        F.push_back(make_pair(nx, l));
      }
    }
  }
  void clear() {
    F.clear();
    L.clear();
  }
  void insert(line A) { L.push_back(A); }
} f[200000 / sz + 100];
int start[200000 / sz + 100];
int finish[200000 / sz + 100];
ll w[200000 / sz + 100];
int block[200001];
vector<line> lines[200001];
void update_block(int x) {
  for (int i = (start[x]); i <= (finish[x]); i++) {
    a[i] += w[x];
  }
  w[x] = 0;
  f[x].clear();
  for (int i = (start[x]); i <= (finish[x]); i++) {
    f[x].insert(line(b[i], a[i] * b[i]));
    if (a[i] < 0) f[x].insert(line(-b[i], -a[i] * b[i]));
  }
  f[x].build();
}
void update(int u, int v, int x) {
  for (int i = (u); i <= (v); i++) {
    if (block[i] != block[u]) break;
    a[i] += x;
  }
  update_block(block[u]);
  if (block[u] == block[v]) return;
  for (int i = (v); i >= (u); i--) {
    if (block[i] != block[v]) break;
    a[i] += x;
  }
  update_block(block[v]);
  for (int i = (block[u] + 1); i < (block[v]); i++) w[i] += x;
}
ll get(int u, int v) {
  ll ans = 0;
  for (int i = (u); i <= (v); i++) {
    if (block[i] != block[u]) break;
    ans = max(ans, abs(a[i] + w[block[i]]) * b[i]);
  }
  if (block[u] == block[v]) return ans;
  for (int i = (v); i >= (u); i--) {
    if (block[i] != block[v]) break;
    ans = max(ans, abs(a[i] + w[block[i]]) * b[i]);
  }
  for (int i = (block[u] + 1); i < (block[v]); i++) {
    ans = max(ans, f[i].get(w[i]));
  }
  return ans;
}
int main() {
  read(n);
  read(q);
  for (int i = (2); i <= (n); i++) {
    int p;
    read(p);
    g[p].push_back(i);
  }
  for (int i = (1); i <= (n); i++) read(ra[i]);
  for (int i = (1); i <= (n); i++) read(rb[i]);
  dfs(1);
  block[0] = 0;
  for (int i = (1); i <= (n); i++)
    if ((i - 1) % sz == 0)
      block[i] = block[i - 1] + 1;
    else
      block[i] = block[i - 1];
  for (int i = (1); i <= (n); i++)
    if (start[block[i]] == 0) start[block[i]] = i;
  for (int i = (n); i >= (1); i--)
    if (finish[block[i]] == 0) finish[block[i]] = i;
  for (int i = (1); i <= (block[n]); i++) update_block(i);
  for (int i = (1); i <= (q); i++) {
    int o, v, x;
    read(o);
    read(v);
    if (o == 1) {
      read(x);
      update(first[v], last[v], x);
    } else {
      writeln(get(first[v], last[v]));
    }
  }
}