물풍선 테러리스트

물풍선 테러리스트 로두마니는 물풍선 아티스트 마리드의 그림을 망치기 위해 마리드가 설치해놓은 물풍선을 모두 터트리려고 한다. (아쉽게도 물풍선이 모두 터져야 마리드가 원하는 그림이 완성된다는 사실은 모르는 듯하다.)

총 $N$ 개의 물풍선이 무한한 2차원 격자판에 설치되어 있다. 이때 $i$ 번째 $(1 \le i \le N)$ 물풍선은 $(x_i, y_i)$ 위치에 세기 $p_i$로 설치되어 있다. 설치된 물풍선의 위치는 모두 다르다.

물풍선이 터지면 물풍선의 세기만큼 가로세로 방향으로 물줄기를 발사한다. $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)$에도 물줄기가 닿게 된다. 만약 이 물줄기가 다른 물풍선에 닿는다면 해당 물풍선 또한 터지게 되며, 이로 인해 연쇄적인 물풍선 폭발이 일어날 수도 있다. 단, 각각의 물줄기가 닿는 범위는 독립적이며 그 과정에서 터지는 다른 물폭탄의 영향을 받지 않는다.

로두마니는 다음과 같은 과정을 통해 이 물풍선들을 전부 터트리려 한다:

1. 물풍선이 남아있는지 확인한다. 남아있는 물풍선이 없다면 과정을 종료한다.
2. 남아있는 물풍선 중 하나를 골라 바늘로 터트린다.
3. 물풍선 폭발이 모두 종료되길 기다린 후, 1단계로 돌아간다.

로두마니에게 필요한 바늘 개수는 위 과정 중 2단계가 반복된 횟수와 같다. 다만 로두마니는 아직 본인의 바늘을 사용할지 남의 바늘을 훔쳐서 사용할지 결정하지 않았기 때문에 필요한 바늘 개수의 최솟값과 최댓값 중 무엇을 구할지 고민하고 있다.

설치되어 있는 $N$ 개의 물풍선 정보가 주어지면, 물풍선을 모두 터트리기 위해 필요한 바늘의 최솟값 또는 최댓값을 출력하는 프로그램을 작성하시오.

입력 형식

첫 줄에 설치된 물풍선의 개수를 나타내는 정수 $N$이 주어진다. $(1 \le N \le 500\,000)$

둘째 줄에는 문자열 $S$가 주어진다. $S$는 min 또는 max 이다. $S$가 min이면 필요한 바늘 개수의 최솟값을, max이면 필요한 바늘 개수의 최댓값을 구해야 한다는 의미이다.

다음 $N$ 개의 줄에 걸쳐 물풍선의 위치와 세기를 나타내는 정수 $x_i, y_i, p_i$가 공백을 사이에 두고 주어진다. $(1 \le x_i,y_i,p_i \le 1\,000\,000\,000)$

모든 물풍선은 서로 다른 위치에 설치되어 있다.

출력 형식

$S$가 min인 경우에는 필요한 바늘 개수의 최솟값, max이면 필요한 바늘 개수의 최댓값을 첫 줄에 출력한다.

예제 1

5
min
1 1 10
3 1 1
5 1 3
1 5 3
1 8 3

1

예제 2

5
max
1 1 10
3 1 1
5 1 3
1 5 3
1 8 3

4

예제 설명

입력 예제 1의 경우 $(1, 1)$ 위치의 물풍선을 바늘로 터트리면 모든 물풍선이 연쇄적인 폭발로 터지게 된다. 이때 $(1, 1)$ 위치의 물풍선의 물줄기가 $(3, 1)$ 위치의 물풍선에 가로막히지 않고 $(5, 1)$ 위치의 물풍선에게도 닿게 됨을 유의하라.

입력 예제 2의 경우 $(1, 5)$, $(1, 8)$ 위치의 물풍선 중 하나를 바늘로 터트리면 나머지 하나도 터지게 되므로, 필요한 바늘 개수가 5인 방법은 존재하지 않는다.

채점 방식

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

해설