Range Queries and Copies

Source: CSES

Version: Phuoc Hung OJ Extended

Problem

Initially the list contains one array. Operation 1 k a x changes position $a$ of array $k$ to $x$; 2 k a b asks its range sum; 3 k appends an independent copy of array $k$.

Input

The first line contains $n,q$, followed by the initial array and $q$ operations.

Output

Print the answer to every type-2 operation.

Subtasks

Subtask 1 (20%)

• $n\le 30$, number of queries $\le 30$.
• All other conditions are the same as Subtask 3.

Subtask 2 (30%)

• $n\le 3000$, number of queries $\le 3000$.
• All other conditions are the same as Subtask 3.

Subtask 3 (50%)

• $1\le n,q\le2\cdot10^5$
• $1\le t_i,x\le10^9$
• $1\le a\le b\le n$
• every version index refers to an existing array

Example

Input

5 6
2 3 1 2 5
3 1
2 1 1 5
2 2 1 5
1 2 2 5
2 1 1 5
2 2 1 5

Output

13
13
13
15

Explanation

After copying array 1, updating position 2 of array 2 changes only that copy. Their full sums become $13$ and $15$.