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>
#pragma GCC optimize("O3")
using namespace std;
const int maxn = 2e5 + 10;
const int maxsn = 10000;
const int INF = 0x7f7f7f7f;
inline int read() {
  int x = 0;
  char c = getchar();
  bool f = false;
  for (; c < '0' || c > '9'; c = getchar())
    if (c == '-') f = true;
  for (; c >= '0' && c <= '9'; c = getchar()) x = x * 10 + (c ^ 48);
  return f ? -x : x;
}
inline int mabs(int x) { return x < 0 ? -x : x; }
int n, q, sn;
vector<int> E[maxn];
int a[maxn], b[maxn], dfn[maxn], siz[maxn], tim;
void input() {
  int i;
  n = read();
  q = read();
  sn = sqrt(n);
  if (sn >= 120) sn -= 100;
  for (i = 2; i <= n; i++) E[read()].push_back(i);
  for (i = 1; i <= n; i++) a[i] = read();
  for (i = 1; i <= n; i++) b[i] = read();
}
void dfs(int x) {
  int i;
  dfn[x] = tim++;
  siz[x] = 1;
  for (i = 0; i < (int)E[x].size(); i++) {
    a[E[x][i]] += a[x];
    b[E[x][i]] += b[x];
    dfs(E[x][i]);
    siz[x] += siz[E[x][i]];
  }
}
inline void Convex(vector<pair<int, long long> > &V) {
  int i;
  vector<pair<int, long long> > Q;
  int qn;
  for (i = 0; i < (int)V.size(); i++) {
    while ((qn = Q.size()) && Q[qn - 1].first == V[i].first) {
      if (Q[qn - 1].second < V[i].second)
        Q.pop_back();
      else
        goto fail;
    }
    while ((qn = Q.size()) > 1 &&
           (long double)(V[i].second - Q[qn - 1].second) *
                   (Q[qn - 1].first - Q[qn - 2].first) >=
               (long double)(Q[qn - 1].second - Q[qn - 2].second) *
                   (V[i].first - Q[qn - 1].first))
      Q.pop_back();
    Q.push_back(V[i]);
  fail:;
  }
  V.swap(Q);
}
struct Block;
Block *AA;
inline long long Getval(int t, pair<int, long long> x) {
  return x.second - (long long)x.first * t;
}
struct Block {
  vector<pair<int, long long> > A;
  int T, mia;
  vector<pair<int, long long> > Bo;
  int *a, *b;
  void init() {
    int i;
    for (i = 0; i < sn; i++) Bo.push_back(pair<int, long long>(b[i], i));
    sort(Bo.begin(), Bo.end());
  }
  void rebuild() {
    int i, j;
    for (i = 0; i < sn; i++) a[i] += T;
    T = 0;
    mia = -INF;
    A.clear();
    for (j = sn - 1; ~j; j--)
      if (a[i = (Bo[j].second)] >= 0)
        A.push_back(pair<int, long long>(-b[i], (long long)a[i] * b[i]));
    for (j = 0; j < sn; j++)
      if (a[i = (Bo[j].second)] < 0) {
        mia = max(mia, a[i]);
        A.push_back(pair<int, long long>(b[i], -(long long)a[i] * b[i]));
      }
    Convex(A);
  }
  void add(int d) {
    T += d;
    mia += d;
    if (mia > 0) rebuild();
  }
  long long mx() {
    int n;
    while ((n = A.size()) > 1 && Getval(T, A[n - 1]) < Getval(T, A[n - 2]))
      A.pop_back();
    return Getval(T, A.back());
  }
} B[maxsn];
void pre() {
  AA = B;
  int i, j;
  static int tmp[maxn];
  for (i = 0; i < n; i++) tmp[dfn[i + 1]] = a[i + 1];
  for (i = 0; i < n; i++) a[i] = tmp[i];
  for (i = 0; i < n; i++) tmp[dfn[i + 1]] = b[i + 1];
  for (i = 0; i < n; i++) b[i] = mabs(tmp[i]);
  for (i = j = 0; i < n; i += sn, j++) {
    B[j].a = a + i;
    B[j].b = b + i;
    B[j].T = 0;
    B[j].init();
    B[j].rebuild();
  }
}
void solve() {
  int i, typ = read(), x = read(), L = dfn[x], R = dfn[x] + siz[x] - 1;
  long long D;
  if (typ == 1) {
    D = read();
    for (i = L; i <= R && i % sn; i++) a[i] += D;
    for (; i + sn - 1 <= R; i += sn) B[i / sn].add(D);
    for (; i <= R; i++) a[i] += D;
    B[L / sn].rebuild();
    if (R / sn != L / sn) B[R / sn].rebuild();
  } else {
    D = 0;
    B[L / sn].rebuild();
    if (R / sn != L / sn) B[R / sn].rebuild();
    for (i = L; i <= R && i % sn; i++) D = max(D, (long long)mabs(a[i]) * b[i]);
    for (; i + sn - 1 <= R; i += sn) D = max(D, B[i / sn].mx());
    for (; i <= R; i++) D = max(D, (long long)mabs(a[i]) * b[i]);
    printf("%I64d\n", D);
  }
}
int main() {
  input();
  dfs(1);
  pre();
  while (q--) solve();
  return 0;
}