전국시대

전국시대에는 $N$개의 국가가 있다. 각 국가에는 $1$부터 $N$까지의 번호가 붙어 있으며, 각 국가는 자신의 힘을 나타내는 병력을 가지고 있다.

$M$개의 기록이 순서대로 주어진다. 각 기록은 동맹과 전쟁 중 하나이다.

• 동맹: 두 국가가 동맹을 맺으면 두 국가가 속한 집단이 하나로 합쳐지고, 병력은 두 집단의 병력을 합한 값이 된다.
• 전쟁: 두 국가가 속한 집단이 전쟁을 벌이면 병력이 많은 쪽이 승리하고, 패배한 집단은 승리한 집단의 속국이 되어 하나로 합쳐진다. 이때 남은 병력은 승리한 집단의 병력에서 패배한 집단의 병력을 뺀 값이 된다. 두 집단의 병력이 같으면 두 집단이 모두 멸망한다.

모든 국가는 약속을 지키므로, 내 동맹의 동맹도 나의 동맹이며, 동맹 중 하나가 전쟁을 시작하면 같은 집단 전체가 함께 참전한다. 속국이 된 집단도 동맹과 같은 방식으로 취급되므로, 전쟁에서 진 집단과 같은 편이었던 모든 국가는 승리한 집단의 속국이 된다. 동맹이나 속국 관계로 묶인 여러 국가는 하나의 국가로 취급한다.

모든 기록이 끝났을 때 살아남은 국가의 수와 각 국가의 남은 병력을 구하는 프로그램을 작성하시오. 남은 병력은 오름차순으로 출력한다.

첫째 줄에 국가의 수 $N$과 기록의 수 $M$이 주어진다. ($1 \le N \le 100{,}000$, $1 \le M \le 100{,}000$)

둘째 줄부터 $N$개의 줄에 걸쳐 $i$번째 국가의 병력 $A_i$가 자연수로 주어진다. ($1 \le A_i \le 10{,}000$)

다음 $M$개의 줄에는 기록이 세 정수 $O$, $P$, $Q$로 주어진다. $O = 1$이면 $P$와 $Q$가 동맹을 맺었음을 의미하고, $O = 2$이면 $P$와 $Q$가 전쟁을 벌였음을 의미한다. ($1 \le P, Q \le N$)

이미 같은 집단에 속한 두 국가가 다시 동맹을 맺거나 전쟁을 벌이는 기록은 주어지지 않으며, 이미 멸망한 국가가 포함된 기록도 주어지지 않는다.

첫째 줄에 살아남은 국가의 수를 출력한다.

살아남은 국가가 있으면 다음 줄에 각 국가의 남은 병력을 오름차순으로 공백으로 구분하여 출력한다. 살아남은 국가가 없으면 첫째 줄의 $0$만 출력한다.