34376번 - Galactic Reconstruction 다국어

문제

A technological disaster has struck an intergalactic civilization. For unknown reasons, all warp drives used to travel between colonies have stopped working. However, they have a new warp drive technology they can employ to connect colonies and form new clusters of colonies.

Initially, there are $n$ colonies numbered 1ドル$ through $n,ドル with the $i$-th colony having an initial wealth of $w_i$. Each colony initially belongs to its own cluster of size 1ドル,ドル with the wealth of the cluster being the wealth of its constituent colony. Clusters can be combined into a larger cluster by building a warp gate that connects two colonies belonging to two different clusters. That is, if cluster $X$ of size $p$ contains colonies $a_1, a_2, \dots, a_p$ and cluster $Y$ of size $q$ contains colonies $b_1, b_2, \dots, b_q,ドル then building a warp gate connecting any $a_i$ and $b_j$ would combine clusters $X$ and $Y$ to form a single cluster $Z$ of size $p + q,ドル containing $a_1, a_2, \dots, a_n, b_1, b_2, \dots, b_q$.

There is an ordered list of $m$ warp gates that have been proposed to be built. The $j$-th proposal suggests building a warp gate that connects colonies $a_j$ and $b_j$ at a cost of $c_j$. If colonies $a_j$ and $b_j$ belong to different clusters, and both of the clusters they belong to individually have a total wealth of least $c_j,ドル then the warp gate between $a_j$ and $b_j$ will be built. Before building the warp gate, the clusters that $a_j$ and $b_j$ belong to will both spend $c_j$ to build the warp gate. This means that both clusters each decrease their total wealth by $c_j$ before the two clusters are combined. If $a_j$ and $b_j$ already belong to the same cluster, or one or both of the clusters containing $a_j$ and $b_j$ don't have a total wealth of at least $c_j,ドル the warp gate will not be built, and both clusters will maintain their wealth.

The proposals are reviewed in the order they appear in the list, and the next proposal is not reviewed until the previous warp gate is either built, or determined not to be built. Your task is to determine which warp gates will be BUILT, which are IMPOSSIBLE because one or both of the colonies lack the necessary wealth, and which are UNNECESSARY because the two colonies already belong to the same cluster. If it is both impossible and unnecessary to build a proposed warp gate, you should only report UNNECESSARY.

For example, consider a scenario where colonies 1ドル$ and 2ドル$ are connected by a warp gate (they form a cluster) with a total wealth of 5ドル,ドル and 3ドル$ and 4ドル$ also make up a cluster with a wealth of 9ドル$. If building a warp gate connecting 2ドル$ and 3ドル$ were proposed at a cost of 5ドル$ wealth, the cost of this warp gate would have to be paid by both the cluster made up of 1ドル$ and 2ドル$ as well as the cluster made up of 3ドル$ and 4ドル,ドル if it were to be built. Since both clusters have at least 5ドル$ wealth, the warp gate is built and now colonies 1,ドル 2, 3$ and 4ドル$ form a cluster with a total wealth of $(5-5) + (9-5) = 4$. Afterward, if it were proposed to build a warp gate between colonies 1ドル$ and 4ドル,ドル it would be reported unnecessary because colonies 1ドル$ and 4ドル$ already belong to the same cluster. Finally, if it were proposed to build a warp gate between colonies 1ドル$ and 5ドル$ at a cost of 5ドル$ wealth, regardless of 5ドル$'s cluster's wealth, it would be impossible because 1ドル$'s cluster only has 4ドル$ wealth.

입력

The first line contains two integers 2ドル \leq n \leq 10^6$ and 1ドル \leq m \leq 10^6,ドル the number of colonies and the number of warp gate proposals, respectively.

The second line contains $n$ space separated integers where the $i$-th integer is the wealth of the $i$-th colony, 0ドル \leq w_i \leq 10^9$.

Then follows $m$ lines, the $j$-th of which contains three integers 1ドル \leq a_j,b_j \leq n,ドル and 0ドル \leq c_j \leq 10^9$ where $a_j$ and $b_j$ denote the colony numbers to connect with the $j$-th proposed warp gate (where $a_j \neq b_j$) and $c_j$ being the cost.

출력

For each of the $m$ proposed warp gates, output a line containing:

• BUILT if the warp gate can and should be built.
• UNNECESSARY if the colonies that would be connected by the warp gate already belong to the same cluster.
• IMPOSSIBLE if it cannot be built because one or both of the clusters lack the necessary wealth to built the warp gate.

Note: If it is both unnecessary and impossible to build a warp gate, you should only report UNNECESSARY.

제한

노트