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 long long oo = 1000000000000015;
pair<int, int> inter[200005];
vector<int> g[200005];
int n, q, p, cnt, len, t, v;
long long a[200005], b[200005], sa[200005], sb[200005], val;
struct LINE {
  int id;
  long long a, b;
  LINE(long long a, long long b, int id) : a(a), b(b), id(id){};
  double intersectX(LINE l) { return double(b - l.b) / double(l.a - a); }
  long long cal(long long x) { return a * x + b; }
};
bool cmp(const LINE &a, const LINE &b) { return a.a < b.a; }
struct CONVEX {
  long long t;
  deque<LINE> convex;
  void buildConvex(vector<LINE> line) {
    convex.clear();
    t = 0;
    for (auto i : line) {
      if (convex.size() > 0 && convex[0].a == i.a && convex[0].b >= i.b)
        continue;
      while (convex.size() > 0 &&
             (convex[0].b < i.b || (convex[0].b == i.b && convex[0].a < i.a)))
        convex.pop_front();
      while (convex.size() > 1 &&
             i.intersectX(convex[0]) <= convex[0].intersectX(convex[1]))
        convex.pop_front();
      convex.push_front(i);
    }
  }
  long long get(long long x) {
    t += x;
    while (convex.size() > 1 &&
           convex.back().cal(t) < convex[convex.size() - 2].cal(t))
      convex.pop_back();
    return convex.back().cal(t);
  }
};
struct BLOCK {
  int left, right;
  long long cur, carry;
  CONVEX convex;
  vector<LINE> line;
  BLOCK(int l, int r) : left(l), right(r), carry(0), cur(0) {
    for (int i = l; i <= r; i++) {
      line.push_back(LINE(sb[i], sa[i] * sb[i], i));
      if (sa[i] < 0 || sb[i] < 0)
        line.push_back(LINE(-sb[i], -sa[i] * sb[i], i));
    }
    sort(line.begin(), line.end(), cmp);
    convex.buildConvex(line);
    cur = convex.get(0);
  }
  void add(int l, int r, long long val) {
    if (right < l || r < left) return;
    if (l <= left && right <= r) {
      cur = convex.get(val);
      carry += val;
    } else {
      for (auto &i : line) {
        i.b += i.a * carry;
        if (l <= i.id && i.id <= r) i.b += i.a * val;
      }
      carry = 0;
      convex.buildConvex(line);
      cur = convex.get(0);
    }
  }
  long long get(int l, int r) {
    if (right < l || r < left) return -oo;
    if (l <= left && right <= r)
      return cur;
    else {
      long long ans = -oo;
      for (auto i : line)
        if (l <= i.id && i.id <= r) ans = max(ans, i.cal(carry));
      return ans;
    }
  }
};
void DFS(int u, long long sx, long long sy) {
  inter[u].first = ++cnt;
  a[u] += sx;
  b[u] += sy;
  for (int v : g[u]) DFS(v, a[u], b[u]);
  inter[u].second = cnt;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> q;
  for (int i = 2; i <= n; i++) {
    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, 0, 0);
  for (int i = 1; i <= n; i++) {
    sa[inter[i].first] = a[i];
    sb[inter[i].first] = b[i];
  }
  len = max(1, int(sqrt(n / 6)));
  vector<BLOCK> block;
  for (int i = 1; i <= n; i += len)
    block.push_back(BLOCK(i, min(n, i + len - 1)));
  while (q--) {
    cin >> t >> v;
    if (t == 1) {
      cin >> val;
      for (auto &b : block) b.add(inter[v].first, inter[v].second, val);
    } else {
      long long res = -oo;
      for (auto &b : block)
        res = max(res, b.get(inter[v].first, inter[v].second));
      cout << res << "\n";
    }
  }
}