물풍선 아티스트

물풍선 아티스트 마리드는 무한한 2차원 격자판에 물풍선 $k$ 개를 원하는 위치와 세기로 놓을 것이다. $i$ 번째 물풍선의 위치는 $(x_i, y_i)$이며, 세기는 $p_i$이다. 이때, 물풍선의 세기 $p_i$는 0보다 큰 정수다.

물풍선은 놓은 즉시 터지며 터진 물풍선의 세기만큼 가로세로 방향으로 물줄기를 발사한다. $i$ 번째 물풍선이 터지면, 가로 방향으로는 $(x_i - p_i, y_i)$, $(x_i - p_i + 1, y_i)$, ..., $(x_i + p_i - 1, y_i)$, $(x_i + p_i, y_i)$에 해당하는 부분에 물줄기가 닿게 되며, 세로 방향으로는 $(x_i, y_i - p_i)$, $(x_i, y_i - p_i + 1)$, ..., $(x_i, y_i + p_i - 1)$, $(x_i, y_i + p_i)$에 해당하는 부분에 물줄기가 닿게 된다. $(x_i, y_i)$에도 물줄기가 닿게 된다.

물줄기가 한 번 이상 닿은 위치의 바닥은 젖어서 색이 어두워지는데, 이 성질을 이용해 마리드는 바닥에 그림을 그리려 한다. 목표 그림은 $N$ 개의 위치 $(a_1, b_1)$, $(a_2, b_2)$, $\dots$, $(a_N, b_N)$으로 이루어져 있으며, 물줄기가 한 번 이상 닿은 위치가 목표 그림과 정확히 일치해야 한다.

목표 그림이 주어지면, 물풍선을 놓아서 해당 그림을 정확히 그리는 것이 가능한지, 가능하다면 그 방법을 출력하는 프로그램을 작성하시오.

입력 형식

첫 줄에 목표 그림을 이루는 위치의 개수를 나타내는 정수 $N$이 주어진다. $(1 \le N \le 1\,000\,000)$

다음 $N$ 개의 줄에 걸쳐 각각에 목표 그림의 위치를 나타내는 정수 $a_i, b_i$가 공백을 사이에 두고 주어진다. $(1 \le a_i,b_i \le 1\,000\,000\,000)$

주어지는 모든 위치는 서로 다르다.

출력 형식

첫 줄에 놓을 물풍선의 개수 $k$를 출력하고, 다음 $k$ 개의 줄에 걸쳐 $i$ 번째 물풍선의 위치와 세기를 나타내는 세 정수 $x_i$, $y_i$, $p_i$를 공백을 사이에 두고 출력한다. 만약, 가능한 답이 여러 가지인 경우 그중 아무거나 하나 출력한다. $k$를 최소화할 필요는 없다. $(1 \le k \le 3\,000\,000;$ $1 \le x_i, y_i, p_i \le 1\,000\,000\,000)$

단, 위 조건을 만족하면서 목표 그림을 정확히 그리는 것이 불가능하다면 첫 줄에 -1을 출력한다.

예제 1

12
1 3
2 3
3 1
3 2
3 3
3 4
3 5
4 1
4 2
4 3
5 2
5 3

2
3 3 2
4 2 1

예제 2

4
1 1
2 1
2 2
3 2

-1

예제 설명

예제 1의 경우 주어진 출력 예제 외에도 가능한 올바른 출력들이 더 존재할 수 있으며, 그중 어느 것을 출력해도 된다.

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞추어야 그 종류에 배정된 점수를 받을 수 있다.

해설