// 又是一道线段树的题目，很容易超时的。。。
// 这题没有用离散化。。。
// http://acm.zju.edu.cn/show_problem.php?pid=1610
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct segtree {
struct segtree *lchild;
struct segtree *rchild;
int color;
int lw, hi; // 线段的区间的左右端点。
};
struct segtree *initree(int lw, int hi)
{
struct segtree *root;
if (lw >= hi) return NULL;
root = (struct segtree *)malloc(sizeof(struct segtree));
if (hi - lw == 1) {
root->lchild = root->rchild = NULL;
} else {
root->lchild = initree(lw, (lw + hi)/2);
root->rchild = initree((lw + hi)/2, hi);
}
root->color = -1;
root->lw = lw;
root->hi = hi;
return root;
}
void insert(struct segtree *root, int lw, int hi, int color)
{
int mid;
if (lw >= hi) return;
if (root->color == color || (root->lw == lw && root->hi == hi)) root->color = color;
else {
// skillfull...
if (root->color >= 0) root->lchild->color = root->rchild->color = root->color;
mid = (root->lw + root->hi)/2;
if (hi <= root->lchild->hi) insert(root->lchild, lw, hi, color);
else if (lw >= root->rchild->lw) insert(root->rchild, lw, hi, color);
else {
if (root->lchild) insert(root->lchild, lw, mid, color);
if (root->rchild) insert(root->rchild, mid, hi, color);
}
root->color = -1;
}
}
void destroy(struct segtree *root)
{
if (root->lchild) destroy(root->lchild);
if (root->rchild) destroy(root->rchild);
free(root);
}
int cx, cc, tree[8001];
void output(struct segtree *root)
{
if (root == NULL) return;
if (root->color >= 0) {
if (root->color == cc) {
if (cx == root->lw) cx = root->hi;
else {
cx = root->hi;
tree[cc]++;
}
} else {
cx = root->hi;
cc = root->color;
tree[cc]++;
}
} else {
output(root->lchild);
output(root->rchild);
}
}
int list[8001][3];
int main(void)
{
int i, n, x1, x2, color, min, max, maxc;
struct segtree *root;
while (scanf("%d", &n) == 1) {
min = 8001;
max = 0;
maxc= 0;
for (i = 0; i < n; i++) {
scanf("%d %d %d", &x1, &x2, &color);
list[i][0] = x1;
list[i][1] = x2;
list[i][2] = color;
if (x2 > max) max = x2;
if (x1 < min) min = x1;
if (color > maxc) maxc = color;
}
root = initree(min, max);
for (i = 0; i < n; i++)
insert(root, list[i][0], list[i][1], list[i][2]);
memset(tree, 0, sizeof(int)*(maxc + 1));
cx = cc = -1;
output(root);
for (i = 0; i <= maxc; i++) {
if (tree[i]) printf("%d %d\n", i, tree[i]);
}
printf("\n");
destroy(root);
}
return 0;
}