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 inf = (int)1.01e9;
const long long infll = (long long)1.01e18;
const long double eps = 1e-9;
const long double pi = acos((long double)-1);
mt19937 mrand(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x) { return mrand() % x; }
void precalc() {}
const int maxn = (int)2e5 + 5;
int n, q;
vector<int> g[maxn];
int as[maxn], bs[maxn];
bool read() {
  if (scanf("%d%d", &n, &q) < 2) {
    return false;
  }
  for (int i = 0; i < n; i++) {
    g[i].clear();
  }
  for (int i = 1; i < n; i++) {
    int p;
    scanf("%d", &p);
    p--;
    g[p].push_back(i);
  }
  for (int i = 0; i < n; i++) {
    scanf("%d", &as[i]);
  }
  for (int i = 0; i < n; i++) {
    scanf("%d", &bs[i]);
  }
  return true;
}
int tl[maxn], tr[maxn];
vector<int> path;
void dfs(int v) {
  tl[v] = ((int)(path).size());
  path.push_back(v);
  for (int i = 0; i < ((int)(g[v]).size()); i++) {
    int u = g[v][i];
    as[u] += as[v];
    bs[u] += bs[v];
    dfs(u);
  }
  tr[v] = ((int)(path).size());
}
struct line {
  long long a, b;
  line() : a(0), b(0) {}
  line(long long _a, long long _b) : a(_a), b(_b) {}
  bool operator<(const line &l) const {
    if (b != l.b) {
      return b < l.b;
    }
    return a < l.a;
  }
  long long eval(long long x) { return a + b * x; }
};
bool bad(const line &l0, const line &l1, const line &l2) {
  return (long double)(l0.a - l1.a) / (l1.b - l0.b) >=
         (long double)(l1.a - l2.a) / (l2.b - l1.b);
}
const int K = 200, maxb = (maxn + K - 1) / K;
vector<pair<line, int>> allls[maxb];
vector<line> ls[maxb];
long long x[maxb];
int pos[maxb];
void buildBlock(int b) {
  ls[b].clear();
  x[b] = 0;
  pos[b] = 0;
  int k = 0;
  for (int i = 0; i < ((int)(allls[b]).size()); i++) {
    auto cur = allls[b][i].first;
    {
      bool bad = false;
      while (k && cur.b == ls[b][k - 1].b) {
        if (cur.a <= ls[b][k - 1].a) {
          bad = true;
          break;
        }
        ls[b].pop_back();
        k--;
      }
      if (bad) {
        continue;
      }
    }
    while (k >= 2 && bad(ls[b][k - 2], ls[b][k - 1], cur)) {
      ls[b].pop_back();
      k--;
    }
    ls[b].push_back(cur);
    k++;
  }
}
void updateBlock(int b, int l, int r, int y) {
  for (int i = 0; i < ((int)(allls[b]).size()); i++) {
    auto &cur = allls[b][i].first;
    int id = allls[b][i].second;
    cur.a += x[b] * cur.b;
    if (l <= id && id < r) {
      cur.a += y * cur.b;
    }
  }
  buildBlock(b);
}
void update(int l, int r, int y) {
  for (int b = 0; b * K < n; b++) {
    int bl = b * K, br = min(bl + K, n);
    if (l <= bl && br <= r) {
      x[b] += y;
      continue;
    }
    int ll = max(l, bl), rr = min(r, br);
    if (ll < rr) {
      updateBlock(b, ll, rr, y);
    }
  }
}
long long get1(int b) {
  while (pos[b] + 1 < ((int)(ls[b]).size()) &&
         ls[b][pos[b] + 1].eval(x[b]) > ls[b][pos[b]].eval(x[b])) {
    pos[b]++;
  }
  return ls[b][pos[b]].eval(x[b]);
}
long long getBlock(int b, int l, int r) {
  long long res = 0;
  bool bb = true;
  for (int i = 0; i < ((int)(allls[b]).size()); i++) {
    auto curl = allls[b][i].first;
    int id = allls[b][i].second;
    if (l <= id && id < r) {
      long long cur = curl.eval(x[b]);
      if (bb) {
        res = cur;
        bb = false;
      } else {
        res = max(res, cur);
      }
    }
  }
  return res;
}
long long get(int l, int r) {
  long long res = 0;
  bool bb = true;
  for (int b = 0; b * K < n; b++) {
    int bl = b * K, br = min(bl + K, n);
    if (l <= bl && br <= r) {
      long long cur = get1(b);
      if (bb) {
        res = cur;
        bb = false;
      } else {
        res = max(res, cur);
      }
      continue;
    }
    int ll = max(l, bl), rr = min(r, br);
    if (ll < rr) {
      long long cur = getBlock(b, ll, rr);
      if (bb) {
        res = cur;
        bb = false;
      } else {
        res = max(res, cur);
      }
    }
  }
  return res;
}
void solve() {
  path.clear();
  dfs(0);
  for (int i = 0; i < n; i++) {
    bs[i] = abs(bs[i]);
  }
  for (int b = 0; b * K < n; b++) {
    int bl = b * K, br = min(bl + K, n);
    allls[b].clear();
    for (int i = bl; i < br; i++) {
      int id = path[i];
      allls[b].push_back(
          make_pair(line((long long)as[id] * bs[id], (long long)bs[id]), i));
      allls[b].push_back(
          make_pair(line((long long)-as[id] * bs[id], (long long)-bs[id]), i));
    }
    sort(allls[b].begin(), allls[b].end());
    buildBlock(b);
  }
  for (int qq = 0; qq < q; qq++) {
    int t;
    scanf("%d", &t);
    if (t == 1) {
      int v, y;
      scanf("%d%d", &v, &y);
      v--;
      update(tl[v], tr[v], y);
    } else {
      int v;
      scanf("%d", &v);
      v--;
      printf("%lld\n", get(tl[v], tr[v]));
    }
  }
}
int main() {
  precalc();
  while (read()) {
    solve();
  }
  return 0;
}