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 = 200200, K = 160;
struct Hull {
  long long a[K * 2], b[K * 2], curX;
  double x[K * 2];
  int head, tail;
  Hull() : head(0), tail(-1), curX(0) {}
  void add(long long aNew, long long bNew) {
    double xNew = -1e18;
    while (head <= tail) {
      if (aNew == a[tail]) {
        if (bNew <= b[tail]) return;
        tail--;
        continue;
      }
      xNew = 1.0 * (b[tail] - bNew) / (aNew - a[tail]);
      if (head == tail || xNew >= x[tail]) break;
      tail--;
    }
    a[++tail] = aNew;
    b[tail] = bNew;
    x[tail] = xNew;
  }
  long long get(int addX) {
    curX += addX;
    while (head < tail && x[head + 1] < curX) head++;
    return a[head] * curX + b[head];
  }
};
int n;
vector<int> adj[N], order;
vector<pair<int, int>> sortedBlocks[N];
int dfsTime, timeIn[N], timeOut[N];
vector<Hull> hulls;
long long a[N], b[N];
void visit(int x, int par) {
  order.push_back(x);
  timeIn[x] = dfsTime++;
  for (int y : adj[x])
    if (y != par) {
      a[y] += a[x];
      b[y] += b[x];
      visit(y, x);
    }
  swap(a[x], b[x]);
  b[x] *= a[x];
  timeOut[x] = dfsTime;
}
bool compare(pair<int, int> u, pair<int, int> v) {
  return a[u.first] * u.second < a[v.first] * v.second;
}
void initBlock(int id) {
  int from = id * K, to = min(n, (id + 1) * K);
  for (int i = from; i < to; i++)
    for (int j = -1; j <= 1; j += 2) sortedBlocks[id].push_back({order[i], j});
  sort(sortedBlocks[id].begin(), sortedBlocks[id].end(), compare);
}
Hull buildHull(int id) {
  Hull hull;
  for (auto u : sortedBlocks[id])
    hull.add(a[u.first] * u.second, b[u.first] * u.second);
  return hull;
}
void update(int v, int x) {
  int from = timeIn[v], firstBlock = from / K;
  int to = timeOut[v], lastBlock = (to - 1) / K;
  for (int i = lastBlock * K; i < min(n, (lastBlock + 1) * K); i++) {
    if (from <= i && i < to) b[order[i]] += a[order[i]] * x;
    b[order[i]] += a[order[i]] * hulls[lastBlock].curX;
  }
  hulls[lastBlock] = buildHull(lastBlock);
  if (firstBlock != lastBlock) {
    for (int i = firstBlock * K; i < (firstBlock + 1) * K; i++) {
      if (from <= i && i < to) b[order[i]] += a[order[i]] * x;
      b[order[i]] += a[order[i]] * hulls[firstBlock].curX;
    }
    hulls[firstBlock] = buildHull(firstBlock);
  }
  for (int i = firstBlock + 1; i < lastBlock; i++) hulls[i].get(x);
}
long long get(int v) {
  long long res = 0;
  int from = timeIn[v], firstBlock = from / K;
  int to = timeOut[v], lastBlock = (to - 1) / K;
  for (int i = from; i < min(to, min(n, (firstBlock + 1) * K)); i++)
    res = max(res, llabs(a[order[i]] * hulls[firstBlock].curX + b[order[i]]));
  for (int i = max(from, lastBlock * K); i < to; i++)
    res = max(res, llabs(a[order[i]] * hulls[lastBlock].curX + b[order[i]]));
  for (int i = firstBlock + 1; i < lastBlock; i++)
    res = max(res, hulls[i].get(0));
  return res;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int q, x, query, v;
  cin >> n >> q;
  for (int i = 1; i < n; i++) {
    cin >> x;
    adj[i].push_back(--x);
    adj[x].push_back(i);
  }
  for (int i = 0; i < n; i++) cin >> a[i];
  for (int i = 0; i < n; i++) cin >> b[i];
  dfsTime = 0;
  visit(0, -1);
  int numBlock = (n + K - 1) / K;
  for (int i = 0; i < numBlock; i++) {
    initBlock(i);
    hulls.push_back(buildHull(i));
  }
  while (q--) {
    cin >> query >> v;
    if (query == 1) {
      cin >> x;
      update(--v, x);
    } else
      cout << get(--v) << '\n';
  }
}