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>
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
using namespace ::std;
const long long maxn = 2e5 + 500;
const long long sq = 330;
inline long long sagh(long long a, long long b) { return a / b + (a % b != 0); }
struct cht {
  vector<pair<long long, long long> > ves;
  vector<pair<long long, long long> > ans;
  long long poi;
  long long barkhord(long long a, long long b) {
    return sagh(ves[a].first - ves[b].first, ves[b].second - ves[a].second);
  }
  long long findMinAt(long long t) {
    while (poi + 1 < ans.size() && ans[poi + 1].first <= t) {
      poi++;
    }
    long long v = ans[poi].second;
    return ves[v].first + ves[v].second * t;
  }
  void add(vector<pair<long long, long long> > vec) {
    ves.clear();
    ans.clear();
    poi = 0;
    for (auto v : vec) {
      while (ves.size() && ves.back().first >= v.first) ves.pop_back();
      if (ves.empty() || ves.back().second != v.second) ves.push_back(v);
    }
    for (long long i = 0; i < ves.size(); i++) {
      while (ans.size() && barkhord(ans.back().second, i) <= ans.back().first) {
        ans.pop_back();
      }
      if (ans.empty()) {
        ans.push_back(make_pair(0, i));
      } else {
        ans.push_back(make_pair(barkhord(ans.back().second, i), i));
      }
    }
  }
};
cht s[(maxn / sq + 3) * 2];
long long sa[maxn];
long long sb[maxn];
long long n;
long long lazy[maxn / sq + 3];
vector<pair<long long, long long> > tar[maxn / sq + 2];
void bild(long long x) {
  long long l = x * sq;
  long long r = min(n, (x + 1) * sq);
  if (tar[x].empty()) {
    for (long long i = l; i < r; i++) {
      tar[x].push_back(make_pair(sb[i], i));
    }
    sort(tar[x].begin(), tar[x].end());
    reverse(tar[x].begin(), tar[x].end());
  }
  for (long long i = l; i < r; i++) {
    sa[i] += lazy[x];
  }
  lazy[x] = 0;
  vector<pair<long long, long long> > vec;
  for (auto v : tar[x]) {
    vec.push_back(make_pair(sa[v.second] * v.first, v.first));
  }
  s[2 * x].add(vec);
  for (long long i = 0; i < vec.size(); i++) {
    vec[i].first *= -1;
    vec[i].second *= -1;
  }
  reverse(vec.begin(), vec.end());
  s[2 * x + 1].add(vec);
}
long long findMx(long long l, long long r) {
  long long ans = 0;
  if (l / sq == (r - 1) / sq) {
    for (long long i = l; i < r; i++) {
      ans = max(ans, sb[i] * abs(sa[i] + lazy[i / sq]));
    }
    return ans;
  }
  for (long long i = l; i / sq == l / sq; i++) {
    ans = max(ans, sb[i] * abs(sa[i] + lazy[i / sq]));
  }
  for (long long i = r - 1; i / sq == (r - 1) / sq; i--) {
    ans = max(ans, sb[i] * abs(sa[i] + lazy[i / sq]));
  }
  for (long long i = l / sq + 1; i < (r - 1) / sq; i++) {
    ans = max(ans, abs(s[i * 2].findMinAt(lazy[i])));
    ans = max(ans, abs(-s[i * 2 + 1].findMinAt(lazy[i])));
  }
  return ans;
}
void update(long long l, long long r, long long v) {
  if (l / sq == (r - 1) / sq) {
    for (long long i = l; i < r; i++) {
      sa[i] += v;
    }
    bild(l / sq);
    return;
  }
  for (long long i = l; i / sq == l / sq; i++) {
    sa[i] += v;
  }
  for (long long i = r - 1; i / sq == (r - 1) / sq; i--) {
    sa[i] += v;
  }
  for (long long i = l / sq + 1; i < (r - 1) / sq; i++) {
    lazy[i] += v;
  }
  bild(l / sq);
  bild((r - 1) / sq);
}
vector<long long> ger[maxn];
long long a[maxn];
long long b[maxn];
long long st[maxn];
long long et[maxn];
long long tt = 0;
void dfs(long long A, long long SA = 0, long long SB = 0) {
  st[A] = tt++;
  SA += a[A];
  SB += b[A];
  sa[st[A]] = SA;
  sb[st[A]] = abs(SB);
  for (auto v : ger[A]) {
    dfs(v, SA, SB);
  }
  et[A] = tt;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  long long q;
  cin >> n >> q;
  for (long long i = 2; i <= n; i++) {
    long long p;
    cin >> p;
    ger[p].push_back(i);
  }
  for (long long i = 1; i <= n; i++) {
    cin >> a[i];
  }
  for (long long i = 1; i <= n; i++) {
    cin >> b[i];
  }
  dfs(1);
  for (long long i = 0; i <= (n - 1) / sq; i++) {
    bild(i);
  }
  while (q--) {
    long long typ;
    cin >> typ;
    if (typ == 1) {
      long long v, x;
      cin >> v >> x;
      update(st[v], et[v], x);
    } else {
      long long v;
      cin >> v;
      cout << findMx(st[v], et[v]) << endl;
    }
  }
}