A school has organized a popular "Sunshine Long-Distance Running" event. To "work healthily for the motherland for fifty years," students have left their dormitories, classrooms, and laboratories to participate in a 3000-meter run on the playground. The playground is bustling with activity, crowded with people, and presents an unprecedented spectacle.

To help students better monitor themselves, the school has implemented a card-swiping system.

There are $n$ locations on campus, represented by integers from $1$ to $n$, and each location has a certain number of card-swiping machines. There are three types of events:

1. A running track is built connecting location $A$ and location $B$.
2. The number of card-swiping machines at location $A$ changes to $B$.
3. A long-distance run takes place. A student starts at $A$ and ends at $B$. We want to find the maximum number of times the student can swipe their card. The specific requirements are as follows:
   • When a student arrives at a location, they can swipe their card on every machine at that location. However, each machine can only be swiped once; even if the student visits the same location multiple times, they cannot swipe the card more than once at the same machine.
   • For safety reasons, each track must be assigned a direction, and the track can only be traversed in that direction. The maximum number of card swipes is the maximum number of swipes possible by choosing an orientation for each track and following any path from location $A$ to location $B$.

Input

The first line contains two positive integers $n$ and $m$, representing the number of locations and the number of operations.

The second line contains $n$ non-negative integers, where the $i$-th number is the initial number of card-swiping machines at the $i$-th location.

The next $m$ lines each contain three non-negative integers $P, A, B$, where $P$ is the event type and $A, B$ are the two parameters for the event.

• Initially, there are no tracks between any locations.
• Each number in a line is separated by a single space.
• The location indices are between $1$ and $n$, the number of card-swiping machines at each location never exceeds $10\,000$, and $P \in \{1, 2, 3\}$.

Output

The number of lines in the output should equal the number of type 3 events. Each line corresponds to a type 3 event. If there exists a configuration of track directions and a path such that the student can reach $B$ from $A$, output the maximum number of card swipes. If $A$ cannot reach $B$, output -1.

Examples

Input 1

9 31
10 20 30 40 50 60 70 80 90
3 1 2
1 1 3
1 1 2
1 8 9
1 2 4
1 2 5
1 4 6
1 4 7
3 1 8
3 8 8
1 8 9
3 8 8
3 7 5
3 7 3
1 4 1
3 7 5
3 7 3
1 5 7
3 6 5
3 3 6
1 2 4
1 5 5
3 3 6
2 8 180
3 8 8
2 9 190
3 9 9
2 5 150
3 3 6
2 1 210
3 3 6

Output 1

-1
-1
80
170
180
170
190
170
250
280
280
270
370
380
580

Constraints

For $100\%$ of the data, $m \leq 5n$, and at any time, the number of card-swiping machines at each location does not exceed $10\,000$. The specific scale of each data group is as follows: