여러 길드가 각자의 전투력을 가지고 있다.

길드들은 때때로 동맹을 맺어 하나의 연합이 되기도 하고, 다른 연합과 전쟁을 벌이기도 한다.

동맹을 맺으면 두 연합은 하나의 연합이 되며, 새 연합의 전투력은 두 연합의 전투력의 합이 된다.

전쟁이 일어나면 전투력이 더 큰 연합이 살아남고, 살아남은 연합의 전투력은 두 연합의 전투력의 차이가 된다. 두 연합의 전투력이 같다면 두 연합은 모두 사라진다.

전쟁에서 한쪽 연합이 살아남는 경우, 패배한 연합에 속해 있던 길드들은 모두 승리한 연합에 흡수된다. 따라서 이후 명령에서 패배했던 길드 번호가 다시 등장하면, 그 길드는 승리한 연합에 속한 것으로 처리한다.

모든 명령을 처리한 뒤 살아남은 연합들의 전투력을 오름차순으로 출력하시오.

입력

첫째 줄에 길드의 수 \(N\)과 명령의 수 \(M\)이 공백으로 구분되어 주어진다.

둘째 줄부터 \(N\)개의 줄에 걸쳐 각 길드의 초기 전투력 \(A_i\)가 한 줄에 하나씩 주어진다.

다음 \(M\)개의 줄에는 명령이 하나씩 주어진다.

명령은 다음 두 종류 중 하나이다.

• 1 a b: \(a\)번 길드가 속한 연합과 \(b\)번 길드가 속한 연합이 동맹을 맺는다.
• 2 a b: \(a\)번 길드가 속한 연합과 \(b\)번 길드가 속한 연합이 전쟁을 벌인다.

이미 같은 연합에 속한 두 길드에 대한 명령은 아무 일도 일어나지 않는다.

전쟁에서 두 연합의 전투력이 같아 둘 다 사라진 경우, 그 연합에 속한 길드들은 이후 명령에 등장하지 않는다.

출력

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

둘째 줄에 살아남은 연합들의 전투력을 오름차순으로 출력한다.

살아남은 연합이 없다면 둘째 줄은 빈 줄로 출력한다.

제한 사항

• \(1 \le N \le 100,000\)
• \(1 \le M \le 100,000\)
• \(1 \le A_i \le 10,000\)
• \(1 \le a, b \le N\)
• \(a \ne b\)

예제 입력 1

6 5
5
8
13
21
34
55
1 1 2
1 3 4
2 2 3
1 5 6
2 1 5

예제 출력 1

1
68

예제 설명 1

\(1\)번 길드와 \(2\)번 길드가 동맹을 맺어 전투력 \(13\)인 연합이 된다.

\(3\)번 길드와 \(4\)번 길드가 동맹을 맺어 전투력 \(34\)인 연합이 된다.

이후 \(2\)번 길드가 속한 연합과 \(3\)번 길드가 속한 연합이 전쟁을 벌인다. 전투력 \(34\)인 연합이 승리하고, 남은 전투력은 \(21\)이다. 이때 \(1\)번 길드와 \(2\)번 길드는 승리한 연합에 흡수된다.

\(5\)번 길드와 \(6\)번 길드가 동맹을 맺어 전투력 \(89\)인 연합이 된다.

마지막으로 \(1\)번 길드가 속한 연합과 \(5\)번 길드가 속한 연합이 전쟁을 벌인다. \(1\)번 길드는 앞선 전쟁에서 흡수되었으므로 현재 전투력 \(21\)인 연합에 속한다.

전투력 \(89\)인 연합이 승리하고, 남은 전투력은 \(68\)이다.

예제 입력 2

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

예제 출력 2

0