

물풍선 아티스트 마리드를 기억하는가?
마리드는 다음 작품을 위해 총 $N$ 개의 물풍선을 2차원 격자판에 설치했다.
이때 $i$ 번째 물풍선은 $(x_i, y_i)$ 칸에 세기 $p_i$로 설치되어 있다.
설치된 물풍선의 위치는 모두 다르다.

물풍선이 터지면 물풍선의 세기만큼 십자모양으로 물줄기를 발사한다.
다시 말해, 가로 방향으로는 $(x_i - p_i, y_i)$, $(x_i - p_i + 1, y_i)$, $\cdots$,
$(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)$, $\cdots$,
$(x_i, y_i + p_i - 1)$, $(x_i, y_i + p_i)$에 해당하는 칸에 물줄기가 닿게 된다.
물론, $(x_i, y_i)$에도 물줄기가 닿게 된다. 만약 이 물줄기가 다른 물풍선이 있는 칸에 닿는다면
그 물풍선 또한 터지며, 이로 인해 연쇄적인 물풍선 폭발이 일어날 수도 있다.
단, 각각의 물줄기가 닿는 범위는 독립적이며
그 과정에서 터지는 다른 물폭탄의 영향을 받지 않는다. 즉, 물풍선이 중첩된다고 세기가 커지는 것은 아니다.


![사진](https://s3.ap-northeast-2.amazonaws.com/bikoprodweb-static-production/problem/116/statement/images/e96f44506abcb08006b8)

<그림 1> 세기 3의 물풍선이 터질 때 물줄기 범위 예시


그런데 이때 문제가 발생했다. 설치된 물풍선들의 세기 $p_i$를 모두 잊어버린 것이다!
마리드는 물풍선 애널리스트 모스에게 의뢰해서 다음과 같은 정보를 얻었다.

* $i$ 번째 물풍선을 터트렸을 때 $N$ 개의 물풍선이 모두 터지는지 여부 $t_i$ ($0 \le t_i \le 1$) 
  * $t_i$가 $1$이면 $N$ 개의 물풍선이 모두 터진다는 뜻이고, $t_i$가 $0$이면 그렇지 않다는 뜻이다.

모스는 유능한 물풍선 애널리스트이기 때문에, 모스의 정보가 틀렸을 가능성은 없다.
다시 말해, $t_i$를 모두 만족하는 물풍선 세기 $p_i$의 조합의 존재함이 보장된다.

설치되어 있는 $N$ 개의 물풍선 위치와 모스의 정보가 주어질 때,
이를 만족하는 물풍선 세기의 조합을 구하는 프로그램을 작성하시오.

## 입력 형식

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

이어지는 $N$ 줄의 $i$ 번째 줄에 $i$ 번째 물풍선의 위치와 모스의 정보를 나타내는 정수
$x_i$, $y_i$, $t_i$가 공백으로 구분되어 주어진다.
($1 \le x_i,y_i \le 1\,000\,000\,000$; $0 \le t_i \le 1$)

주어지는 물풍선의 위치는 서로 다르다.

## 출력 형식

$i$ 번째 줄에 $i$ 번째 물풍선의 세기를 나타내는 $p_i$를 출력한다.
($1 \le p_i \le 1\,000\,000\,000$)

주어진 $t_i$를 모두 만족하며, 출력 형식 또한 만족하는 $p_i$의 조합의 존재함이 보장된다.
만약 답이 여러 가지인 경우, 그중 아무거나 하나 출력한다.

## 입력 예제

```
4
1 1 1
5 1 0
5 3 0
1 3 1
```

## 출력 예제

```
4
2
2
2
```

## 예제 설명

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

## 채점 방식

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

* 종류 1 (13점): $N \le 3$
* 종류 2 (31점): $N \le 2\,500$
* 종류 3 (56점): 추가적인 제한 조건이 없음.
