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 comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#pragma GCC target( \
    "sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")
using namespace std;
const int MN = 1000005, inf = 1000000005, mod = 1000000007;
const long long INF = 1000000000000000005LL;
const int __BS = 4096;
static char __bur[__BS + 16], *__er = __bur + __BS, *__ir = __er;
template <class T = int>
T readInt() {
  auto c = [&]() {
    if (__ir == __er)
      std::fill(__bur, __bur + __BS, 0), cin.read(__bur, __BS), __ir = __bur;
  };
  c();
  while (*__ir && (*__ir < '0' || *__ir > '9') && *__ir != '-') ++__ir;
  c();
  bool m = false;
  if (*__ir == '-') ++__ir, c(), m = true;
  T r = 0;
  while (*__ir >= '0' && *__ir <= '9') r = r * 10 + *__ir - '0', ++__ir, c();
  ++__ir;
  return m ? -r : r;
}
string readString() {
  auto c = [&]() {
    if (__ir == __er)
      std::fill(__bur, __bur + __BS, 0), cin.read(__bur, __BS), __ir = __bur;
  };
  string r;
  c();
  while (*__ir && isspace(*__ir)) ++__ir, c();
  while (!isspace(*__ir)) r.push_back(*__ir), ++__ir, c();
  ++__ir;
  return r;
}
char readChar() {
  auto c = [&]() {
    if (__ir == __er)
      std::fill(__bur, __bur + __BS, 0), cin.read(__bur, __BS), __ir = __bur;
  };
  c();
  while (*__ir && isspace(*__ir)) ++__ir, c();
  return *__ir++;
}
static char __buw[__BS + 20], *__iw = __buw, *__ew = __buw + __BS;
template <class T>
void writeInt(T x, char endc = '\n') {
  if (x < 0) *__iw++ = '-', x = -x;
  if (x == 0) *__iw++ = '0';
  char *s = __iw;
  while (x) {
    T t = x / 10;
    char c = x - 10 * t + '0';
    *__iw++ = c;
    x = t;
  }
  char *f = __iw - 1;
  while (s < f) swap(*s, *f), ++s, --f;
  if (__iw > __ew) cout.write(__buw, __iw - __buw), __iw = __buw;
  if (endc) {
    *__iw++ = endc;
  }
}
template <class T>
void writeStr(const T &str) {
  int i = 0;
  while (str[i]) {
    *__iw++ = str[i++];
    if (__iw > __ew) cout.write(__buw, __iw - __buw), __iw = __buw;
  }
}
struct __FL__ {
  ~__FL__() {
    if (__iw != __buw) cout.write(__buw, __iw - __buw);
  }
};
static __FL__ __flushVar__;
inline int mo(int &a) { return (a > 0 ? a : -a); }
int pocz[MN], kon[MN], A[MN], B[MN], sa[MN], sb[MN];
vector<int> G[MN];
int czas;
void dfs(int x, int a, int b) {
  pocz[x] = ++czas;
  kon[x] = pocz[x];
  a += A[x];
  b += B[x];
  sa[pocz[x]] = a, sb[pocz[x]] = b;
  for (auto v : G[x])
    if (!pocz[v]) {
      dfs(v, a, b);
      kon[x] = kon[v];
    }
}
void add(int *t, int n, int x) {
  for (int i = 0; i < n; ++i) t[i] += x;
}
long long ask(int *t, int *u, int n) {
  long long ans1 = 0LL, ans2 = 0LL;
  for (int i = 0; i < n; ++i) {
    long long r = t[i] * 1LL * u[i];
    ans1 = ans1 < r ? r : ans1;
    ans2 = ans2 > r ? r : ans2;
  }
  return max(ans1, -ans2);
}
int main() {
  int n, q;
  n = readInt();
  q = readInt();
  for (int i = 2; i <= n; ++i) {
    int p;
    p = readInt();
    G[p].push_back(i);
  }
  for (int i = 1; i <= n; ++i) A[i] = readInt();
  for (int i = 1; i <= n; ++i) B[i] = readInt();
  dfs(1, 0, 0);
  while (q--) {
    int typ, v, x, a, b;
    typ = readInt();
    if (typ == 1) {
      v = readInt();
      x = readInt();
      a = pocz[v], b = kon[v];
      add(sa + a, b - a + 1, x);
    } else {
      v = readInt();
      a = pocz[v], b = kon[v];
      long long ans = ask(sa + a, sb + a, b - a + 1);
      writeInt(ans);
    }
  }
}