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;
template <typename T>
bool get_int(T &x) {
  char t = getchar();
  bool neg = false;
  x = 0;
  for (; (t > '9' || t < '0') && t != '-' && t != EOF; t = getchar())
    ;
  if (t == '-') neg = true, t = getchar();
  if (t == EOF) return false;
  for (; t <= '9' && t >= '0'; t = getchar()) x = x * 10 + t - '0';
  if (neg) x = -x;
  return true;
}
template <typename T>
void print_int(T x) {
  if (x < 0) putchar('-'), x = -x;
  short a[20] = {}, sz = 0;
  while (x > 0) a[sz++] = x % 10, x /= 10;
  if (sz == 0) putchar('0');
  for (int i = sz - 1; i >= 0; i--) putchar('0' + a[i]);
}
const int inf = 0x3f3f3f3f;
const long long Linf = 1ll << 61;
const double pi = acos(-1.0);
const int maxn = 200111;
const int B = 200;
int n, q, a[maxn], b[maxn], fa[maxn], ord[maxn];
bool cmp_by_b(int x, int y) { return b[x] < b[y]; }
int bl[maxn / B + 100], br[maxn / B + 100], bid[maxn], btot;
inline bool chk(const pair<long long, long long> &a,
                const pair<long long, long long> &b,
                const pair<long long, long long> &c) {
  double Tl = ((double)a.second - b.second) * ((double)c.first - a.first),
         Tr = ((double)b.first - a.first) * ((double)a.second - c.second);
  if (abs(Tl - Tr) > 1e16) return Tl > Tr;
  return (a.second - b.second) * (c.first - a.first) -
             (b.first - a.first) * (a.second - c.second) >=
         0;
}
inline long long val(const pair<long long, long long> &a, int x) {
  return a.first * x + a.second;
}
struct block {
  pair<long long, long long> mn[B + 1], mx[B + 1];
  int mntot, mxtot, mnit, mxit, cur_x;
  block() { cur_x = 0; }
  void addmn(long long a, long long b) {
    if (mntot && mn[mntot - 1].first == a) {
      if (mn[mntot - 1].second > b)
        return;
      else
        mntot--;
    }
    while (mntot > 1 && chk(mn[mntot - 2], mn[mntot - 1], make_pair(a, b)))
      mntot--;
    mn[mntot++] = make_pair(a, b);
  }
  void addmx(long long a, long long b) {
    if (mxtot && mx[mxtot - 1].first == a) {
      if (mx[mxtot - 1].second < b)
        return;
      else
        mxtot--;
    }
    while (mxtot > 1 && chk(mx[mxtot - 2], mx[mxtot - 1], make_pair(a, b)))
      mxtot--;
    mx[mxtot++] = make_pair(a, b);
  }
  void getmn() {
    while (mnit < mntot - 1 && val(mn[mnit], cur_x) < val(mn[mnit + 1], cur_x))
      mnit++;
  }
  void getmx() {
    while (mxit < mxtot - 1 && val(mx[mxit], cur_x) > val(mx[mxit + 1], cur_x))
      mxit++;
  }
  void rebuild(int l, int r) {
    mntot = mxtot = 0;
    mnit = mxit = 0;
    for (int i = l; i <= r; i++)
      addmn(b[ord[i]], (long long)a[ord[i]] * b[ord[i]]);
    for (int i = r; i >= l; i--)
      addmx(b[ord[i]], (long long)a[ord[i]] * b[ord[i]]);
    getmn();
    getmx();
  }
  void modify(int x) {
    cur_x += x;
    getmn();
    getmx();
  }
  long long querymx() { return val(mn[mnit], cur_x); }
  long long querymn() { return val(mx[mxit], cur_x); }
};
block blk[maxn / B + 100];
void modify(int l, int r, int v) {
  int idl = bid[l], idr = bid[r];
  if (idl == idr) {
    for (int i = l; i <= r; i++) a[i] += v;
    blk[idl].rebuild(bl[idl], br[idl]);
    return;
  }
  if (bl[idl] != l) {
    for (int i = l; i <= br[idl]; i++) a[i] += v;
    blk[idl].rebuild(bl[idl], br[idl]);
    idl++;
  }
  if (br[idr] != r) {
    for (int i = bl[idr]; i <= r; i++) a[i] += v;
    blk[idr].rebuild(bl[idr], br[idr]);
    idr--;
  }
  for (int i = idl; i <= idr; i++) blk[i].modify(v);
}
inline long long getval(int i) {
  return (long long)(a[i] + blk[bid[i]].cur_x) * b[i];
}
long long query(int l, int r) {
  int idl = bid[l], idr = bid[r];
  long long mn = getval(l), mx = mn;
  if (idl == idr) {
    for (int i = l; i <= r; i++) {
      long long tmp = getval(i);
      mn = min(mn, tmp);
      mx = max(mx, tmp);
    }
    return max(mx, -mn);
  }
  if (bl[idl] != l) {
    for (int i = l; i <= br[idl]; i++) {
      long long tmp = getval(i);
      mn = min(mn, tmp);
      mx = max(mx, tmp);
    }
    idl++;
  }
  if (br[idr] != r) {
    for (int i = bl[idr]; i <= r; i++) {
      long long tmp = getval(i);
      mn = min(mn, tmp);
      mx = max(mx, tmp);
    }
    idr--;
  }
  for (int i = idl; i <= idr; i++) {
    mn = min(mn, blk[i].querymn());
    mx = max(mx, blk[i].querymx());
  }
  return max(mx, -mn);
}
vector<int> g[maxn];
int dfn[maxn], edfn[maxn], timer;
void dfs(int x) {
  dfn[x] = ++timer;
  for (auto v : g[x]) dfs(v);
  edfn[x] = timer;
}
void re_number(int *a, int *ord) {
  static int tmp[maxn];
  for (int i = 1; i <= n; i++) tmp[ord[i]] = a[i];
  for (int i = 1; i <= n; i++) a[i] = tmp[i];
}
int main() {
  (get_int(n) && get_int(q));
  for (int i = 2; i <= n; i++) get_int(fa[i]);
  for (int i = 1; i <= n; i++) get_int(a[i]);
  for (int i = 1; i <= n; i++) get_int(b[i]);
  for (int i = 2; i <= n; i++) {
    a[i] += a[fa[i]];
    b[i] += b[fa[i]];
    g[fa[i]].push_back(i);
  }
  dfs(1);
  re_number(a, dfn);
  re_number(b, dfn);
  for (int i = 1; i <= n; i++) ord[i] = i;
  for (int i = 1; i <= n; i += B) {
    btot++;
    for (int j = i; j <= n && j < i + B; j++) {
      if (!bl[btot]) bl[btot] = j;
      br[btot] = j;
      bid[j] = btot;
    }
    sort(ord + bl[btot], ord + br[btot] + 1, cmp_by_b);
    blk[btot].rebuild(bl[btot], br[btot]);
  }
  int tp, x, y;
  while (q--) {
    (get_int(tp) && get_int(x));
    if (tp == 1) {
      get_int(y);
      modify(dfn[x], edfn[x], y);
    } else
      printf("%lld\n", query(dfn[x], edfn[x]));
  }
  return 0;
}