Zhang Junhao's Life Tree

Zhu Zhixin has magically obtained Zhang Junhao's Life Tree. The tree has (n) nodes, and each node (i) has a weight (w_i). Initially, the tree is given with (n) nodes and (n-1) edges. You are then given (m) operations. At any moment, let (s) be the current number of nodes in the tree.

There are two types of operations:

1. Query Operation: You are given four integers (u_1, v_1, u_2, v_2) (with (1 \le u_1, v_1, u_2, v_2 \le s)). Let array (a) be the weights on the simple path from (u_1) to (v_1) (in order) and array (b) be the weights on the simple path from (u_2) to (v_2). The similarity (LRP(a,b)) is defined as the largest integer (i) (with (i \le \min(|a|, |b|))) such that for all (1 \le j \le i), [ b_j = a_j + j ] If no such (i) exists, then (LRP(a,b)=0). For each query operation, output the value of (LRP(a,b)).

2. Append Operation: You are given two integers (u) and (w'). Create a new node with weight (w') and label (s+1) and add an undirected edge between node (s+1) and node (u) (with (u \le s)). Then update (s \leftarrow s+1).

Input Format:

• The first line contains two integers \(n\) and \(m\).
• The second line contains \(n\) integers representing \(w_1, w_2, \dots, w_n\).
• The next \(n-1\) lines each contain two integers describing an edge between two nodes.
• Then follow \(m\) lines, each representing an operation. An operation is given as follows:
  • If the line contains four integers, it is a query operation: \(u_1, v_1, u_2, v_2\).
  • If the line contains two integers, it is an append operation: \(u, w'\).

Output Format: For each query operation, output a single integer — the computed similarity (LRP(a,b)) — on a separate line.

inputFormat

The first line contains two integers (n) and (m). The second line contains (n) integers representing the weights of the nodes. The next (n-1) lines describe the edges of the tree. Then (m) lines follow, each representing an operation. An operation will either consist of four integers (query) or two integers (append).

outputFormat

For every query operation, output a single integer — the similarity (LRP(a,b)) — on a separate line.

sample

3 4
1 2 3
1 2
2 3
1 3 1 2
2 2 10
4 3 2 4
1 4 1 4

0
0
0