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;
constexpr int maxn = 2e5 + 10;
int n, q, tot_id, in[maxn], out[maxn];
long long a[maxn], b[maxn];
long long suma[maxn], sumb[maxn];
vector<int> G[maxn];
bool cmp(long double a, long double b, long double c, long double d) {
  return a * d >= b * c;
}
void dfs(int u, int fa) {
  in[u] = ++tot_id;
  suma[u] = suma[fa] + a[u];
  sumb[u] = sumb[fa] + b[u];
  for (int x : G[u]) {
    if (x == fa) continue;
    dfs(x, u);
  }
  out[u] = tot_id;
}
struct Upper {
  pair<long long, long long> q[2005];
  int line_cnt = 0, now = 1;
  long long x_value = 0;
  void insert(long long k, long long b) {
    while (line_cnt >= 2 && cmp(q[line_cnt - 1].second - q[line_cnt].second,
                                q[line_cnt].first - q[line_cnt - 1].first,
                                q[line_cnt].second - b, k - q[line_cnt].first))
      line_cnt--;
    q[++line_cnt] = make_pair(k, b);
  }
  void add(long long x) {
    x_value += x;
    while (now < line_cnt && x_value * q[now + 1].first + q[now + 1].second >
                                 x_value * q[now].first + q[now].second)
      now++;
  }
  long long get_max_value() { return q[now].first * x_value + q[now].second; }
  void clear() {
    x_value = line_cnt = 0;
    now = 1;
  }
};
struct block {
 public:
  int L, R;
  Upper U;
  vector<pair<pair<long long, long long>, int>> lines;
  long long offset = 0;
  bool binit = false;
  void init(int _l, int _r) {
    if (!lines.empty()) {
      binit = true;
      sort(lines.begin(), lines.end());
      build();
      L = _l;
      R = _r;
    }
  }
  void build() {
    U.clear();
    for (int i = 0; i < (int)lines.size(); i++)
      U.insert(lines[i].first.first, lines[i].first.second);
    U.add(0);
  }
  void add(long long x, int l, int r) {
    if (r < L || l > R) return;
    if (l <= L && R <= r) {
      U.add(x);
      offset += x;
    } else {
      for (int i = 0; i < (int)lines.size(); i++) {
        lines[i].first.second += offset * lines[i].first.first;
        if (l <= lines[i].second && lines[i].second <= r) {
          lines[i].first.second += x * lines[i].first.first;
        }
      }
      offset = 0;
      U.clear();
      build();
    }
  }
  long long get(int l, int r) {
    if (r < L || l > R) return numeric_limits<long long>::min();
    if (l <= L && R <= r) {
      return U.get_max_value();
    } else {
      long long ans = numeric_limits<long long>::min();
      for (int i = 0; i < (int)lines.size(); i++) {
        if (l <= lines[i].second && lines[i].second <= r) {
          ans = max(ans, lines[i].first.first * offset + lines[i].first.second);
        }
      }
      return ans;
    }
    return 0;
  }
} blocks[2005];
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  cin >> n >> q;
  for (int i = 2; i <= n; i++) {
    int p;
    cin >> p;
    G[p].emplace_back(i);
    G[i].emplace_back(p);
  }
  for (int i = 1; i <= n; i++) cin >> a[i];
  for (int i = 1; i <= n; i++) cin >> b[i];
  int block_sz = max(1, (int)sqrt(n / 6));
  dfs(1, 1);
  for (int i = 1; i <= n; i++) {
    int block_id = ((in[i] - 1) / block_sz) + 1;
    blocks[block_id].lines.emplace_back(make_pair(
        pair<long long, long long>(sumb[i], suma[i] * sumb[i]), in[i]));
    if (suma[i] < 0 || sumb[i] < 0)
      blocks[block_id].lines.emplace_back(
          make_pair(-sumb[i], -suma[i] * sumb[i]), in[i]);
  }
  int tot_block = 0;
  for (tot_block = 1;; tot_block++) {
    blocks[tot_block].init((tot_block - 1) * block_sz + 1,
                           min(tot_block * block_sz, n));
    if (!blocks[tot_block].binit) {
      tot_block--;
      break;
    }
  }
  for (int i = 1; i <= q; i++) {
    int opt;
    cin >> opt;
    if (opt == 1) {
      int v;
      long long x;
      cin >> v >> x;
      for (int j = 1; j <= tot_block; j++) {
        blocks[j].add(x, in[v], out[v]);
      }
    } else {
      int v;
      cin >> v;
      long long ans = numeric_limits<long long>::min();
      for (int j = 1; j <= tot_block; j++) {
        ans = max(ans, blocks[j].get(in[v], out[v]));
      }
      cout << ans << endl;
    }
  }
  return 0;
}