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;
clock_t timeStart, timeFinish;
void timeBegin() { timeStart = clock(); }
void timeEnd() { timeFinish = clock(); }
void timeDuration() {
  timeEnd();
  double time_taken = double(timeFinish - timeStart) / double(CLOCKS_PER_SEC);
  cout << "Time taken by program is : " << fixed << time_taken
       << setprecision(5);
  cout << " sec " << endl;
}
class InputReader {
 public:
  InputReader() {
    input_file = stdin;
    cursor = 0;
    fread(buffer, SIZE, 1, input_file);
  }
  InputReader(const char *file_name) {
    input_file = fopen(file_name, "r");
    cursor = 0;
    fread(buffer, SIZE, 1, input_file);
  }
  inline InputReader &operator>>(int &n) {
    while ((buffer[cursor] < '0' || buffer[cursor] > '9') &&
           buffer[cursor] != '-') {
      advance();
    }
    int sign = 1;
    if (buffer[cursor] == '-') {
      sign = -1;
      advance();
    }
    n = 0;
    while ('0' <= buffer[cursor] && buffer[cursor] <= '9') {
      n = n * 10 + buffer[cursor] - '0';
      advance();
    }
    n *= sign;
    return *this;
  }

 private:
  FILE *input_file;
  static const int SIZE = 1 << 17;
  int cursor;
  char buffer[SIZE];
  inline void advance() {
    ++cursor;
    if (cursor == SIZE) {
      cursor = 0;
      fread(buffer, SIZE, 1, input_file);
    }
  }
};
const int MAXN = 200000;
const int MAXSQRT = 200000;
vector<int> g[1 + MAXN];
vector<int> bucket[MAXSQRT];
int a[1 + MAXN], b[1 + MAXN];
int first[1 + MAXN], last[1 + MAXN], id;
int v[MAXN];
long long aSum[1 + MAXN], bSum[1 + MAXN], x[MAXSQRT];
int p[MAXSQRT];
long long myAbs(long long x) { return (x < 0 ? -x : x); }
void DFS(int node) {
  v[id] = node;
  first[node] = id++;
  aSum[node] += a[node];
  bSum[node] += b[node];
  for (auto son : g[node]) {
    aSum[son] = aSum[node];
    bSum[son] = bSum[node];
    DFS(son);
  }
  bSum[node] = myAbs(bSum[node]);
  last[node] = id - 1;
}
inline bool compareSlope(const int &a, const int &b) {
  return bSum[a] < bSum[b];
}
struct Line {
  long long a;
  long long b;
  long long evaluate(long long x) { return a * x + b; }
};
vector<Line> st[MAXSQRT];
long double intersect(Line p, Line q) {
  return (long double)(q.b - p.b) / (p.a - q.a);
}
void addLine(Line l, int id) {
  if (l.a == 0) {
    return;
  }
  if (!st[id].empty() && st[id].back().a == l.a) {
    l.b = max(st[id].back().b, l.b);
    st[id].pop_back();
  }
  while (st[id].size() >= 2 &&
         intersect(l, st[id].back()) <=
             intersect(st[id].back(), st[id][st[id].size() - 2])) {
    st[id].pop_back();
  }
  st[id].push_back(l);
}
void addLines(int id, int sign) {
  reverse(bucket[id].begin(), bucket[id].end());
  for (auto it : bucket[id]) {
    Line l = {bSum[it] * sign, bSum[it] * aSum[it] * sign};
    addLine(l, id);
  }
}
void shift(int id, int val) {
  x[id] += val;
  while (p[id] + 1 < st[id].size() &&
         intersect(st[id][p[id]], st[id][p[id] + 1]) <= x[id]) {
    p[id]++;
  }
}
void redoHull(int id) {
  for (auto it : bucket[id]) {
    aSum[it] += x[id];
  }
  x[id] = 0;
  st[id].clear();
  addLines(id, -1);
  addLines(id, 1);
  p[id] = 0;
  shift(id, 0);
}
long long getBest(int id) {
  shift(id, 0);
  if (st[id].empty()) {
    return 0;
  } else {
    return st[id][p[id]].evaluate(x[id]);
  }
}
int main() {
  timeBegin();
  InputReader cin;
  int n, q;
  cin >> n >> q;
  for (int i = 2; i <= n; i++) {
    int p;
    cin >> p;
    g[p].push_back(i);
  }
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  for (int i = 1; i <= n; i++) {
    cin >> b[i];
  }
  DFS(1);
  int len = sqrt(n / 6) + 1;
  for (int b = 0; b * len < n; b++) {
    int i = b * len, j = min(n - 1, (b + 1) * len - 1);
    for (int k = i; k <= j; k++) {
      bucket[b].push_back(v[k]);
    }
    sort(bucket[b].begin(), bucket[b].end(), compareSlope);
    redoHull(b);
  }
  for (int t = 1; t <= q; t++) {
    int type;
    cin >> type;
    if (type == 1) {
      int node, val;
      cin >> node >> val;
      int l = first[node], r = last[node];
      for (int b = l / len; b <= r / len; b++) {
        int i = b * len, j = min(n - 1, (b + 1) * len - 1);
        if (l <= i && j <= r) {
          shift(b, val);
        } else {
          for (int k = max(l, i); k <= min(r, j); k++) {
            aSum[v[k]] += val;
          }
          redoHull(b);
        }
      }
    } else {
      int node;
      cin >> node;
      int l = first[node], r = last[node];
      long long answer = 0;
      for (int b = l / len; b <= r / len; b++) {
        int i = b * len, j = min(n - 1, (b + 1) * len - 1);
        if (l <= i && j <= r) {
          answer = max(answer, getBest(b));
        } else {
          for (int k = max(l, i); k <= min(r, j); k++) {
            answer = max(answer, myAbs(aSum[v[k]] + x[b]) * bSum[v[k]]);
          }
        }
      }
      cout << answer << "\n";
    }
  }
  return 0;
}