#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <algorithm>
using namespace std;
struct Obstacle {
int id;
int x, y;
char type;
vector<int> adj; // Lưu các đỉnh kề trong đồ thị chu trình
};
map<int, int> obs_at_pos[4]; // UP, DOWN, LEFT, RIGHT
vector<int> bipartite_color;
vector<bool> visited;
vector<int> final_colors;
// DFS để tìm chu trình và tô màu 2 phía
bool find_and_color_cycles(int u, int c, const vector<Obstacle>& obstacles) {
visited[u] = true;
bipartite_color[u] = c;
int current = u;
int len = 0;
do {
visited[current] = true;
len++;
if(obstacles[current].adj.empty()) { // Path, not cycle
len = 0;
break;
}
current = obstacles[current].adj[0]; // Chỉ có 1 đường ra
} while (current != u && !visited[current]);
if (current == u) { // Found a cycle
if (len % 8 != 0) return false;
}
// Tô màu 2 phía cho toàn bộ thành phần liên thông
vector<int> q;
q.push_back(u);
visited.assign(obstacles.size(), false);
visited[u] = true;
int head = 0;
while(head < q.size()){
int curr = q[head++];
for(int neighbor : obstacles[curr].adj){
if(!visited[neighbor]){
visited[neighbor] = true;
bipartite_color[neighbor] = 1 - bipartite_color[curr];
q.push_back(neighbor);
}
}
}
return true;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin >> n;
vector<Obstacle> obstacles(n);
map<int, vector<pair<int, int>>> group_by_x, group_by_y;
for (int i = 0; i < n; ++i) {
obstacles[i].id = i;
cin >> obstacles[i].x >> obstacles[i].y >> obstacles[i].type;
group_by_x[obstacles[i].x].push_back({obstacles[i].y, i});
group_by_y[obstacles[i].y].push_back({obstacles[i].x, i});
}
for (auto const& [x_val, vec] : group_by_x) {
sort(group_by_x[x_val].begin(), group_by_x[x_val].end());
}
for (auto const& [y_val, vec] : group_by_y) {
sort(group_by_y[y_val].begin(), group_by_y[y_val].end());
}
// Xây dựng đồ thị
for (int i = 0; i < n; ++i) {
int x = obstacles[i].x;
int y = obstacles[i].y;
// Tìm hàng xóm trên/dưới
auto& col = group_by_x[x];
auto it = lower_bound(col.begin(), col.end(), make_pair(y, i));
int my_idx_in_col = distance(col.begin(), it);
int up_neighbor = (my_idx_in_col + 1 < col.size()) ? col[my_idx_in_col + 1].second : -1;
int down_neighbor = (my_idx_in_col > 0) ? col[my_idx_in_col - 1].second : -1;
// Tìm hàng xóm trái/phải
auto& row = group_by_y[y];
it = lower_bound(row.begin(), row.end(), make_pair(x, i));
int my_idx_in_row = distance(row.begin(), it);
int right_neighbor = (my_idx_in_row + 1 < row.size()) ? row[my_idx_in_row + 1].second : -1;
int left_neighbor = (my_idx_in_row > 0) ? row[my_idx_in_row - 1].second : -1;
if (obstacles[i].type == '/') {
if(left_neighbor != -1) obstacles[i].adj.push_back(up_neighbor);
if(up_neighbor != -1) obstacles[i].adj.push_back(left_neighbor);
if(right_neighbor != -1) obstacles[i].adj.push_back(down_neighbor);
if(down_neighbor != -1) obstacles[i].adj.push_back(right_neighbor);
} else { // type == '\'
if(left_neighbor != -1) obstacles[i].adj.push_back(down_neighbor);
if(down_neighbor != -1) obstacles[i].adj.push_back(left_neighbor);
if(right_neighbor != -1) obstacles[i].adj.push_back(up_neighbor);
if(up_neighbor != -1) obstacles[i].adj.push_back(right_neighbor);
}
// Rút gọn lại adj, vì mỗi đỉnh chỉ có 2 cạnh ra
sort(obstacles[i].adj.begin(), obstacles[i].adj.end());
obstacles[i].adj.erase(remove(obstacles[i].adj.begin(), obstacles[i].adj.end(), -1), obstacles[i].adj.end());
}
// Tìm chu trình, kiểm tra và tô màu 2 phía
bipartite_color.assign(n, -1);
visited.assign(n, false);
for (int i = 0; i < n; ++i) {
if (!visited[i]) {
if (!find_and_color_cycles(i, 0, obstacles)) {
cout << -1 << endl;
return 0;
}
}
}
// Tô 4 màu cuối cùng
final_colors.assign(n, 0);
vector<int> counts(2, 0);
for (int i = 0; i < n; ++i) {
int c = bipartite_color[i];
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;
}
