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;
struct line {
  long long k, b, poc;
  bool operator<(const line& other) const {
    return tie(k, b) < tie(other.k, other.b);
  }
  bool iznad(const line& other) const {
    return other.poc * other.k + other.b <= other.poc * k + b;
  }
  long long presek(const line& other) const {
    long long p = other.b - b;
    long long q = k - other.k;
    return p < 0 ? p / q : (p + q - 1) / q;
  }
};
struct convexhull {
  vector<line> a;
  int p;
  void dodaj(long long k, long long b) { a.push_back({k, b, -3000000000ll}); }
  void zavrsi() {
    sort(a.begin(), a.end());
    vector<line> b;
    for (line c : a) {
      while (b.size() >= 1 && c.iznad(b.back())) b.pop_back();
      if (b.size()) c.poc = c.presek(b.back());
      b.push_back(c);
    }
    swap(a, b);
    p = 0;
  }
  long long resi(long long x) {
    while (p + 1 < (int)a.size() && a[p + 1].poc <= x) p++;
    return a[p].k * x + a[p].b;
  }
};
struct upit {
  int t, v, x;
} u[100005];
int n, q;
basic_string<int> e[200005];
int a[200005], b[200005];
int sa[200005], sb[200005];
int el[200005], er[200005], t;
void dfs(int x, int p) {
  el[x] = t;
  sa[t] = sa[el[p]] + a[x];
  sb[t] = sb[el[p]] + b[x];
  t++;
  for (int y : e[x]) dfs(y, x);
  er[x] = t;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  cerr.tie(nullptr);
  cin >> n >> q;
  for (int i = 2; i <= n; i++) {
    int p;
    cin >> p;
    e[p] += i;
  }
  for (int i = 1; i <= n; i++) cin >> a[i];
  for (int i = 1; i <= n; i++) cin >> b[i];
  for (int i = 0; i < q; i++) {
    cin >> u[i].t >> u[i].v;
    if (u[i].t == 1) cin >> u[i].x;
  }
  dfs(1, 0);
  for (int i = 1; i <= n; i++) sb[i] = abs(sb[i]);
  for (int ul = 0, ur = 2000; ul < q; ul += 2000, ur += 2000) {
    ur = min(ur, q);
    basic_string<int> cm;
    for (int j = ul; j < ur; j++) {
      cm += el[u[j].v];
      cm += er[u[j].v];
    }
    sort(cm.begin(), cm.end());
    cm.erase(unique(cm.begin(), cm.end()), cm.end());
    int b = cm.size() - 1;
    vector<convexhull> ha(b), hb(b);
    vector<int> d(b);
    for (int i = 0; i < b; i++) {
      for (int j = cm[i]; j < cm[i + 1]; j++) {
        ha[i].dodaj(sb[j], 1ll * sa[j] * sb[j]);
        hb[i].dodaj(-sb[j], -1ll * sa[j] * sb[j]);
      }
      ha[i].zavrsi();
      hb[i].zavrsi();
    }
    for (int j = ul; j < ur; j++) {
      int wl = lower_bound(cm.begin(), cm.end(), el[u[j].v]) - cm.begin();
      int wr = lower_bound(cm.begin(), cm.end(), er[u[j].v]) - cm.begin();
      if (u[j].t == 1) {
        for (int k = wl; k < wr; k++) d[k] += u[j].x;
      } else {
        long long ans = 0;
        for (int k = wl; k < wr; k++) {
          ans = max(ans, ha[k].resi(d[k]));
          ans = max(ans, hb[k].resi(d[k]));
        }
        cout << ans << '\n';
      }
    }
    for (int i = 0; i < b; i++) {
      for (int j = cm[i]; j < cm[i + 1]; j++) {
        sa[j] += d[i];
      }
    }
  }
}