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 + 50, B = 1111;
const long double inf = 5e18;
const long double eps = 1e-12;
int n, q, a[N], b[N], f[N], blo[N], sq, num, ll[N], rr[N], dfn[N], dfm[N], clk,
    idfn[N];
vector<int> v[N];
int read() {
  int x = 0, c, f = 1;
  while (!isdigit(c = getchar())) c == '-' ? f = -1 : 0;
  while (isdigit(c)) x = x * 10 + c - 48, c = getchar();
  return x * f;
}
void dfs(int x) {
  dfn[x] = ++clk;
  idfn[clk] = x;
  for (int i = 0; i < v[x].size(); i++) dfs(v[x][i]);
  dfm[x] = clk;
}
long double k(long long y, int x) {
  return x ? 1.0 * y / x : y > 0 ? inf : -inf;
}
void cmax(long long &x, long long y) { y > x ? x = y : 0; }
bool cmp(int x, int y) { return b[idfn[x]] < b[idfn[y]]; }
struct node {
  int a[N], b[N], t[N], st[B][B], tp[B];
  long long y[N];
  vector<int> v[B];
  void build(int i) {
    int *Q = st[i], &R = tp[i];
    R = 0;
    for (int j = 0; j < v[i].size(); j++) {
      int x = v[i][j];
      assert(!j || b[x] >= b[v[i][j - 1]]);
      while (R > 1 && k(y[Q[R]] - y[Q[R - 1]], b[Q[R]] - b[Q[R - 1]]) -
                              k(y[x] - y[Q[R]], b[x] - b[Q[R]]) <
                          eps)
        R--;
      Q[++R] = x;
    }
  }
  void init() {
    for (int i = 1; i <= num; i++) {
      for (int j = ll[i]; j <= rr[i]; j++)
        v[i].push_back(j), y[j] = 1ll * a[j] * b[j];
      sort(v[i].begin(), v[i].end(), cmp);
      build(i);
    }
  }
  void change(int l, int r, int x) {
    for (int i = l; i <= min(r, rr[blo[l]]); i++)
      a[i] -= x, y[i] = 1ll * a[i] * b[i];
    build(blo[l]);
    if (blo[l] != blo[r]) {
      for (int i = ll[blo[r]]; i <= r; i++) a[i] -= x, y[i] = 1ll * a[i] * b[i];
      build(blo[r]);
    }
    for (int i = blo[l] + 1; i < blo[r]; i++) t[i] += x;
  }
  long long query(int l, int r) {
    long long ret = 0;
    for (int i = l; i <= min(r, rr[blo[l]]); i++)
      cmax(ret, 1ll * (a[i] - t[blo[l]]) * b[i]);
    if (blo[l] != blo[r])
      for (int i = ll[blo[r]]; i <= r; i++)
        cmax(ret, 1ll * (a[i] - t[blo[r]]) * b[i]);
    for (int i = blo[l] + 1; i < blo[r]; i++) {
      int *Q = st[i], &R = tp[i];
      while (R > 1 &&
             k(y[Q[R]] - y[Q[R - 1]], b[Q[R]] - b[Q[R - 1]]) < t[i] + eps)
        R--;
      cmax(ret, 1ll * (a[Q[R]] - t[i]) * b[Q[R]]);
    }
    return ret;
  }
} F, G;
int main() {
  scanf("%d%d", &n, &q);
  sq = max((int)sqrt(n / 6), 1);
  for (int i = 2; i <= n; i++) v[f[i] = read()].push_back(i);
  dfs(1);
  for (int i = 1; i <= n; i++) a[i] = read() + a[f[i]];
  for (int i = 1; i <= n; i++) b[i] = read() + b[f[i]];
  for (int i = 1; i <= n; i++) blo[i] = (i - 1) / sq + 1;
  num = blo[n];
  for (int i = 1; i <= num; i++) ll[i] = (i - 1) * sq + 1, rr[i] = i * sq;
  rr[num] = n;
  for (int i = 1; i <= n; i++)
    F.a[i] = G.a[i] = -a[idfn[i]], F.b[i] = b[idfn[i]], G.b[i] = -b[idfn[i]];
  F.init();
  for (int i = 1; i <= n; i++) b[i] = -b[i];
  G.init();
  for (int i = 1, op, x, y; i <= q; i++) {
    op = read();
    x = read();
    if (op == 1)
      y = read(), F.change(dfn[x], dfm[x], y), G.change(dfn[x], dfm[x], y);
    else
      cout << max(F.query(dfn[x], dfm[x]), G.query(dfn[x], dfm[x])) << endl;
  }
  return 0;
}