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;
namespace IO {
const int BUFFER_SIZE = 1 << 15;
char input_buffer[BUFFER_SIZE];
int input_pos = 0, input_len = 0;
char output_buffer[BUFFER_SIZE];
int output_pos = 0;
char number_buffer[100];
uint8_t lookup[100];
void _update_input_buffer() {
  input_len = fread(input_buffer, sizeof(char), BUFFER_SIZE, stdin);
  input_pos = 0;
  if (input_len == 0) input_buffer[0] = EOF;
}
inline char next_char(bool advance = true) {
  if (input_pos >= input_len) _update_input_buffer();
  return input_buffer[advance ? input_pos++ : input_pos];
}
template <typename T>
inline void read_int(T &number) {
  bool negative = false;
  number = 0;
  while (!isdigit(next_char(false)))
    if (next_char() == '-') negative = true;
  do {
    number = 10 * number + (next_char() - '0');
  } while (isdigit(next_char(false)));
  if (negative) number = -number;
}
template <typename T, typename... Args>
inline void read_int(T &number, Args &...args) {
  read_int(number);
  read_int(args...);
}
void _flush_output() {
  fwrite(output_buffer, sizeof(char), output_pos, stdout);
  output_pos = 0;
}
inline void write_char(char c) {
  if (output_pos == BUFFER_SIZE) _flush_output();
  output_buffer[output_pos++] = c;
}
template <typename T>
inline void write_int(T number, char after = '\0') {
  if (number < 0) {
    write_char('-');
    number = -number;
  }
  int length = 0;
  while (number >= 10) {
    uint8_t lookup_value = lookup[number % 100];
    number /= 100;
    number_buffer[length++] = (lookup_value & 15) + '0';
    number_buffer[length++] = (lookup_value >> 4) + '0';
  }
  if (number != 0 || length == 0) write_char(number + '0');
  for (int i = length - 1; i >= 0; i--) write_char(number_buffer[i]);
  if (after) write_char(after);
}
void init() {
  bool exit_success = atexit(_flush_output) == 0;
  assert(exit_success);
  for (int i = 0; i < 100; i++) lookup[i] = (i / 10 << 4) + i % 10;
}
}  // namespace IO
const long long LL_INF = (long long)2e18 + 5;
struct point {
  long long x, y;
  point() : x(0), y(0) {}
  point(long long _x, long long _y) : x(_x), y(_y) {}
};
bool left_turn(const point &a, const point &b, const point &c) {
  return (double)(b.x - a.x) * (c.y - b.y) > (double)(c.x - b.x) * (b.y - a.y);
}
struct monotonic_dp_hull {
  vector<point> points;
  int front = 0;
  int size() const { return (int)points.size() - front; }
  void clear() {
    points.clear();
    front = 0;
    prev_x = -LL_INF;
    prev_y = 1;
  }
  void insert(const point &p) {
    assert(size() == 0 || p.x >= points.back().x);
    if (size() > 0 && p.x == points.back().x) {
      if (p.y <= points.back().y) return;
      points.pop_back();
    }
    while (size() >= 2 &&
           left_turn(points[points.size() - 2], points.back(), p))
      points.pop_back();
    points.push_back(p);
  }
  void insert(long long a, long long b) { insert(point(a, b)); }
  long long prev_x = -LL_INF, prev_y = 1;
  long long query(long long x, long long y = 1) {
    assert(prev_x == -LL_INF || x * prev_y >= prev_x * y);
    prev_x = x;
    prev_y = y;
    while (size() >= 2 && x * (points[front + 1].x - points[front].x) >=
                              (points[front].y - points[front + 1].y) * y)
      front++;
    return points[front].x * x + points[front].y * y;
  }
};
struct vertex {
  long long A = 0, B = 0;
  int index;
  bool operator<(const vertex &other) const { return B < other.B; }
};
int N, Q;
int BUCKET_SIZE;
vector<int> parent;
vector<vector<int>> children;
vector<vertex> vertices;
vector<vertex> sums;
vector<int> reverse_index;
vector<int> tour_start, tour_end;
void dfs(int node) {
  static int tour;
  if (parent[node] < 0) tour = 0;
  tour_start[node] = tour++;
  sums[tour_start[node]].A =
      vertices[node].A +
      (parent[node] < 0 ? 0 : sums[tour_start[parent[node]]].A);
  sums[tour_start[node]].B =
      vertices[node].B +
      (parent[node] < 0 ? 0 : sums[tour_start[parent[node]]].B);
  for (int child : children[node]) dfs(child);
  tour_end[node] = tour;
}
vector<monotonic_dp_hull> hulls;
vector<long long> bucket_add;
int get_bucket_start(int index) { return index - index % BUCKET_SIZE; }
int get_bucket_end_from_start(int start) { return min(start + BUCKET_SIZE, N); }
void build_bucket(int start, int end) {
  hulls[start].clear();
  if (bucket_add[start] != 0) {
    for (int i = start; i < end; i++) sums[i].A += bucket_add[start];
    bucket_add[start] = 0;
  }
  static vector<pair<long long, long long>> candidates;
  candidates.resize(2 * BUCKET_SIZE);
  int n_cands = 0;
  for (int i = end - 1; i >= start; i--)
    if (sums[i].A < 0)
      candidates[n_cands++] = {-sums[i].B, -sums[i].A * sums[i].B};
  for (int i = start; i < end; i++)
    candidates[n_cands++] = {sums[i].B, sums[i].A * sums[i].B};
  static vector<bool> useless;
  useless.assign(2 * BUCKET_SIZE, true);
  long long max_second = -LL_INF;
  for (int i = n_cands - 1; i >= 0; i--)
    if (candidates[i].second > max_second) {
      max_second = candidates[i].second;
      useless[i] = false;
    }
  for (int i = 0; i < n_cands; i++)
    if (!useless[i])
      hulls[start].insert(candidates[i].first, candidates[i].second);
}
void build() {
  BUCKET_SIZE = 0.5 * sqrt(N) + 1;
  hulls.resize(N);
  bucket_add.assign(N, 0);
  for (int start = 0, end = 0; start < N; start = end) {
    end = get_bucket_end_from_start(start);
    sort(sums.begin() + start, sums.begin() + end);
    build_bucket(start, end);
  }
  reverse_index.resize(N);
  for (int i = 0; i < N; i++) reverse_index[sums[i].index] = i;
}
void update_bucket(int start, int x) { bucket_add[start] += x; }
long long query_bucket(int start) {
  return hulls[start].query(bucket_add[start]);
}
void update_partial_bucket(int bucket_start, int bucket_end, int start, int end,
                           int x) {
  for (int i = start; i < end; i++) sums[reverse_index[i]].A += x;
  build_bucket(bucket_start, bucket_end);
}
long long query_partial_bucket(int bucket_start, int start, int end) {
  long long most = 0;
  for (int i = start; i < end; i++) {
    int index = reverse_index[i];
    most = max(most,
               abs(sums[index].A + bucket_add[bucket_start]) * sums[index].B);
  }
  return most;
}
void update(int start, int end, int x) {
  int bucket_start = get_bucket_start(start);
  int bucket_end = get_bucket_end_from_start(bucket_start);
  if (bucket_start < start) {
    update_partial_bucket(bucket_start, bucket_end, start, min(end, bucket_end),
                          x);
    start = bucket_end;
  }
  while (start < end && get_bucket_end_from_start(start) <= end) {
    update_bucket(start, x);
    start = get_bucket_end_from_start(start);
  }
  if (start < end)
    update_partial_bucket(start, get_bucket_end_from_start(start), start, end,
                          x);
}
long long query(int start, int end) {
  long long best = 0;
  int bucket_start = get_bucket_start(start);
  int bucket_end = get_bucket_end_from_start(bucket_start);
  if (bucket_start < start) {
    best = query_partial_bucket(bucket_start, start, min(end, bucket_end));
    start = bucket_end;
  }
  while (start < end && get_bucket_end_from_start(start) <= end) {
    best = max(best, query_bucket(start));
    start = get_bucket_end_from_start(start);
  }
  if (start < end) best = max(best, query_partial_bucket(start, start, end));
  return best;
}
int main() {
  IO::init();
  IO::read_int(N, Q);
  parent.assign(N, -1);
  children.assign(N, {});
  vertices.resize(N);
  sums.resize(N);
  tour_start.resize(N);
  tour_end.resize(N);
  for (int i = 1; i < N; i++) {
    IO::read_int(parent[i]);
    parent[i]--;
    children[parent[i]].push_back(i);
  }
  for (int i = 0; i < N; i++) IO::read_int(vertices[i].A);
  for (int i = 0; i < N; i++) IO::read_int(vertices[i].B);
  dfs(0);
  for (int i = 0; i < N; i++) {
    vertices[i].index = i;
    sums[i].index = i;
    sums[i].B = abs(sums[i].B);
  }
  build();
  for (int q = 0; q < Q; q++) {
    int type, v, x;
    IO::read_int(type, v);
    v--;
    if (type == 1) {
      IO::read_int(x);
      update(tour_start[v], tour_end[v], x);
    } else if (type == 2) {
      IO::write_int(query(tour_start[v], tour_end[v]), '\n');
    } else {
      assert(false);
    }
  }
}