所驼门王的宝藏

题目描述

地下宫殿由 $R\times C$ 间矩形宫室组成，其中 $N$ 间宫室里埋藏着宝藏。每间藏宝宫室都有一扇传送门，没有宝藏的宫室没有传送门。传送门分为三种：

1. 横天门：可以传送到同一行的任意藏宝宫室；
2. 纵寰门：可以传送到同一列的任意藏宝宫室；
3. 任意门：可以传送到以当前宫室为中心的周围 $8$ 格中的任意藏宝宫室。

你可以选择任意一间宫室进入宫殿，并在任意一间宫室结束后离开。宫室内传送门的使用次数不限，同一宫室也可以经过多次。

请安排一条路线，使经过的不同藏宝宫室数尽可能多，并输出这个最大值。

输入格式

第一行三个正整数 $N,R,C$。

接下来 $N$ 行，每行三个正整数 $x_i,y_i,T_i$，表示第 $i$ 间藏宝宫室位于第 $x_i$ 行、第 $y_i$ 列，其传送门类型为 $T_i$。

$T_i=1$ 表示横天门，$T_i=2$ 表示纵寰门，$T_i=3$ 表示任意门。所有藏宝宫室的位置互不相同。

输出格式

输出一个正整数，表示一条路线最多能够经过多少间不同的藏宝宫室。

样例输入 1

10 7 7
2 2 1
2 4 2
1 7 2
2 7 3
4 2 2
4 4 1
6 7 3
7 7 1
7 5 2
5 2 1

样例输出 1

9

数据范围

对于所有数据，$1\le N\le 10^5$，$1\le R,C\le 10^6$，$1\le x_i\le R$，$1\le y_i\le C$，$1\le T_i\le 3$。