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
struct segment_change {
  int add;
  segment_change(int _add = 0) : add(_add) {}
  void reset() { add = 0; }
  bool has_change() const { return add != 0; }
  segment_change combine(const segment_change &other) const {
    return segment_change(add + other.add);
  }
};
struct segment {
  int A, B;
  int wait;
  segment(int _A = 0, int _B = 0, int _wait = INT_MAX)
      : A(_A), B(_B), wait(_wait) {}
  long long value() const { return (long long)A * B; }
  bool apply(int, const segment_change &change) {
    A += change.add;
    wait -= change.add;
    return wait >= 0;
  }
  void join(const segment &other) {
    int A2 = other.A, B2 = other.B;
    if ((long long)A2 * B2 > (long long)A * B) {
      swap(A, A2);
      swap(B, B2);
    }
    wait = min(wait, other.wait);
    if (B2 > B)
      wait = min((long long)wait,
                 ((long long)A * B - (long long)A2 * B2) / (B2 - B));
  }
  void join(const segment &a, const segment &b) {
    *this = a;
    join(b);
  }
};
struct kinetic_tournament_tree {
  int tree_n = 0;
  vector<segment> tree;
  vector<segment_change> changes;
  kinetic_tournament_tree(int n = 0) {
    if (n > 0) init(n);
  }
  void init(int n) {
    tree_n = 1;
    while (tree_n < n) tree_n *= 2;
    tree.assign(2 * tree_n, segment());
    changes.assign(tree_n, segment_change());
  }
  void build(const vector<segment> &initial) {
    int n = initial.size();
    assert(n <= tree_n);
    for (int i = 0; i < n; i++) tree[tree_n + i] = initial[i];
    for (int position = tree_n - 1; position > 0; position--)
      tree[position].join(tree[2 * position], tree[2 * position + 1]);
  }
  void push_down(int position, int length) {
    if (!changes[position].has_change()) return;
    if (2 * position < tree_n) {
      changes[2 * position] = changes[2 * position].combine(changes[position]);
      changes[2 * position + 1] =
          changes[2 * position + 1].combine(changes[position]);
    }
    tree[2 * position].apply(length / 2, changes[position]);
    tree[2 * position + 1].apply(length / 2, changes[position]);
    changes[position].reset();
  }
  template <typename T_range_op>
  void process_range(int position, int start, int end, int a, int b,
                     bool needs_join, T_range_op &&range_op) {
    if (a <= start && end <= b && range_op(position, end - start)) return;
    if (position >= tree_n) return;
    push_down(position, end - start);
    int mid = (start + end) / 2;
    if (a < mid)
      process_range(2 * position, start, mid, a, b, needs_join, range_op);
    if (b > mid)
      process_range(2 * position + 1, mid, end, a, b, needs_join, range_op);
    if (needs_join)
      tree[position].join(tree[2 * position], tree[2 * position + 1]);
  }
  segment query(int a, int b) {
    assert(0 <= a && a <= b && b <= tree_n);
    segment answer;
    process_range(1, 0, tree_n, a, b, false, [&](int position, int) {
      answer.join(tree[position]);
      return true;
    });
    return answer;
  }
  void update(int a, int b, const segment_change &change) {
    assert(0 <= a && a <= b && b <= tree_n);
    process_range(1, 0, tree_n, a, b, true, [&](int position, int length) {
      bool result = tree[position].apply(length, change);
      if (result && position < tree_n)
        changes[position] = changes[position].combine(change);
      return result;
    });
  }
};
struct vertex {
  int A = 0, B = 0;
};
int N, Q;
vector<int> parent;
vector<vector<int>> children;
vector<vertex> vertices, sums;
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;
}
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);
  kinetic_tournament_tree tree(2 * N);
  vector<segment> initial(2 * N);
  for (int i = 0; i < N; i++) {
    sums[i].B = abs(sums[i].B);
    initial[2 * i] = segment(sums[i].A, -sums[i].B);
    initial[2 * i + 1] = segment(sums[i].A, sums[i].B);
  }
  tree.build(initial);
  for (int q = 0; q < Q; q++) {
    int type, v, x;
    IO::read_int(type, v);
    v--;
    if (type == 1) {
      IO::read_int(x);
      tree.update(2 * tour_start[v], 2 * tour_end[v], x);
    } else if (type == 2) {
      IO::write_int(tree.query(2 * tour_start[v], 2 * tour_end[v]).value(),
                    '\n');
    } else {
      assert(false);
    }
  }
}