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;
const int N = 2e5 + 100;
struct CHT {
  vector<long long> M;
  vector<long long> C;
  int ptr = 0;
  void init() {
    M.clear();
    C.clear();
    ptr = 0;
  }
  bool useless(int l1, int l2, int l3) {
    return (long double)(C[l3] - C[l1]) * (M[l1] - M[l2]) <=
           (long double)(C[l2] - C[l1]) * (M[l1] - M[l3]);
  }
  long long f(int id, long long x) { return M[id] * x + C[id]; }
  void add(long long m, long long c) {
    M.push_back(m);
    C.push_back(c);
    int s = M.size();
    while (s >= 3 && useless(s - 3, s - 2, s - 1)) {
      M.erase(M.end() - 2);
      C.erase(C.end() - 2);
      s--;
    }
  }
  long long query(long long x) {
    if (M.size() == 0) return 0LL;
    if (ptr >= M.size()) ptr = M.size() - 1;
    while (ptr < M.size() - 1 && f(ptr, x) < f(ptr + 1, x)) ptr++;
    return f(ptr, x);
  }
} cht;
int Timer;
int st[N], en[N];
long long slope[N];
long long a[N], b[N], c[N];
vector<int> G[N];
void dfs(int u, int p, long long sum, long long asum) {
  st[u] = ++Timer;
  st[u]--;
  sum += b[u];
  asum += a[u];
  slope[st[u]] = abs(sum);
  c[st[u]] = asum;
  for (int v : G[u]) {
    if (v != p) dfs(v, u, sum, asum);
  }
  en[u] = Timer - 1;
}
int typ[N], node[N], X[N];
long long res[N];
const int B = 200;
pair<long long, int> buffer[N];
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n, q;
  cin >> n >> q;
  for (int u = 2; u <= n; u++) {
    int pu;
    cin >> pu;
    G[pu].push_back(u);
  }
  for (int i = 1; i <= n; i++) cin >> a[i];
  for (int i = 1; i <= n; i++) cin >> b[i];
  dfs(1, -1, 0, 0);
  for (int i = 1; i <= q; i++) {
    cin >> typ[i] >> node[i];
    if (typ[i] == 1) cin >> X[i];
  }
  int tot_block = n / B + 1;
  for (int b = 0; b < tot_block; b++) {
    int L = b * B, R = min(L + B - 1, n - 1);
    long long off = 0;
    int ptr = 0;
    vector<pair<long long, int>> A;
    for (int i = L; i <= R; i++) A.push_back({slope[i], i});
    sort(A.begin(), A.end());
    for (int i = 1; i <= q; i++) {
      int l = st[node[i]], r = en[node[i]];
      if (l > R or r < L) continue;
      if (typ[i] == 1) {
        if (l > L or r < R) {
          cht.init();
          for (int j = (int)A.size() - 1; j >= 0; j--) {
            int idx = A[j].second;
            if (slope[idx]) cht.add(-slope[idx], -slope[idx] * c[idx]);
          }
          for (int j = 0; j < A.size(); j++) {
            int idx = A[j].second;
            if (slope[idx]) cht.add(slope[idx], slope[idx] * c[idx]);
          }
          for (int j = 0; j < ptr; j++) {
            auto t = buffer[j];
            int idx = t.second;
            long long x = t.first;
            res[idx] = max(res[idx], cht.query(x));
          }
          ptr = 0;
          for (int j = max(l, L); j <= min(r, R); j++) {
            c[j] += X[i];
          }
        } else
          off += X[i];
      } else {
        if (l > L or r < R) {
          for (int j = max(l, L); j <= min(r, R); j++) {
            res[i] = max(res[i], abs(c[j] + off) * slope[j]);
          }
        } else
          buffer[ptr++] = {off, i};
      }
    }
    cht.init();
    for (int j = (int)A.size() - 1; j >= 0; j--) {
      int idx = A[j].second;
      cht.add(-slope[idx], -slope[idx] * c[idx]);
    }
    for (int j = 0; j < A.size(); j++) {
      int idx = A[j].second;
      cht.add(slope[idx], slope[idx] * c[idx]);
    }
    sort(buffer, buffer + ptr);
    for (int j = 0; j < ptr; j++) {
      auto t = buffer[j];
      int idx = t.second;
      long long x = t.first;
      res[idx] = max(res[idx], cht.query(x));
    }
    ptr = 0;
  }
  for (int i = 1; i <= q; i++) {
    if (typ[i] == 2) cout << res[i] << "\n";
  }
  return 0;
}