#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <algorithm>
using namespace std;
struct Obstacle {
int id;
int u_coord_id, v_coord_id;
};
vector<int> adj[1000005];
vector<int> bipartite_color;
vector<bool> visited;
// DFS để tìm thành phần liên thông và tô màu 2 phía
void color_component(int start_node, int color, int& node_count, int& edge_count, vector<bool>& component_visited) {
bipartite_color[start_node] = color;
component_visited[start_node] = true;
node_count++;
edge_count += adj[start_node].size();
for (int neighbor : adj[start_node]) {
if (!component_visited[neighbor]) {
color_component(neighbor, 1 - color, node_count, edge_count, component_visited);
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin >> n;
vector<Obstacle> obstacles(n);
map<int, int> u_map, v_map;
vector<pair<int, int>> edges;
// Rời rạc hóa tọa độ u, v
for (int i = 0; i < n; ++i) {
int x, y;
char type;
cin >> x >> y >> type;
u_map[x + y] = 0;
v_map[x - y] = 0;
edges.push_back({x + y, x - y});
}
int u_nodes = 0;
for (auto& pair : u_map) {
pair.second = u_nodes++;
}
int v_nodes = 0;
for (auto& pair : v_map) {
pair.second = u_nodes + v_nodes++;
}
int total_nodes = u_nodes + v_nodes;
// Xây dựng đồ thị hai phía
for (int i = 0; i < n; ++i) {
obstacles[i].id = i;
obstacles[i].u_coord_id = u_map[edges[i].first];
obstacles[i].v_coord_id = u_map.size() + v_map[edges[i].second];
int u_node = u_map[edges[i].first];
int v_node = v_map[edges[i].second] + u_nodes;
adj[u_node].push_back(v_node);
adj[v_node].push_back(u_node);
}
// Tìm chu trình, kiểm tra và tô màu
visited.assign(total_nodes, false);
for (int i = 0; i < total_nodes; ++i) {
if (!visited[i] && !adj[i].empty()) {
int node_count = 0;
long long edge_sum_degree = 0;
vector<int> component_nodes;
vector<int> q;
q.push_back(i);
visited[i] = true;
int head = 0;
while(head < q.size()){
int u = q[head++];
component_nodes.push_back(u);
edge_sum_degree += adj[u].size();
for(int v : adj[u]){
if(!visited[v]){
visited[v] = true;
q.push_back(v);
}
}
}
node_count = component_nodes.size();
// Một thành phần liên thông là một chu trình (hoặc tập các chu trình)
// nếu bậc của mọi đỉnh là 2. Tương đương tổng bậc = 2 * số đỉnh.
if (edge_sum_degree != (long long)node_count * 2) {
continue; // Là một đường đi, không phải chu trình
}
int cycle_len = node_count; // Trong đồ thị hai phía, số cạnh bằng số đỉnh trong một chu trình đơn
if (cycle_len % 4 != 0) { // L_bipartite = L_pinball / 2
cout << -1 << endl;
return 0;
}
}
}
// Tô màu 2 phía
bipartite_color.assign(total_nodes, -1);
for (int i = 0; i < total_nodes; ++i) {
if (bipartite_color[i] == -1 && !adj[i].empty()) {
vector<bool> component_visited(total_nodes, false);
int node_count = 0, edge_count = 0;
color_component(i, 0, node_count, edge_count, component_visited);
}
}
// Tô 4 màu cuối cùng
vector<int> final_colors(n);
vector<int> counts(2, 0); // Đếm cho mỗi phía của đồ thị 2 màu
for (int i = 0; i < n; ++i) {
int u_node = obstacles[i].u_coord_id;
int c = bipartite_color[u_node];
final_colors[i] = (2 * c + 1) + (counts[c] % 2);
counts[c]++;
}
for (int i = 0; i < n; ++i) {
cout << final_colors[i] << (i == n - 1 ? "" : " ");
}
cout << endl;
return 0;
}
