二维平面上有$n$束激光，其中每条激光是一条射线，由$(x,y,d)$给出（使用平面直角坐标系）：

• 如果d=0，表示激光是由(x,y)向右水平射出的射线，其包含点集${(x+t,y)∣t≥0}$。
• 如果d=1，表示激光是由(x,y)向上竖直射出的射线，其包含点集${(x,y+t)∣t≥0}$。

假设你从起点$(0.5,0.5)$出发，想前往终点$(X+0.5,Y+0.5)$，每步可以选择上下左右四种方向中的一种，向选择的方向移动长度为1的线段，问最少需要经过多少次激光？

对于激光重合的情况，例如同时存在向右的$(1,1,0),(2,1,0)$两条激光，从$(2.5,0.5)$向上走一步到$(2.5,1.5)$同时经过这两条激光，需要算作两次。注意，激光的发射点也有可能重合。

输入格式

第一行三个正整数$n,X,Y$。

接下来n行每行三个整数$(x,y,d)$描述一条激光，满足$0<x≤X,0<y≤Y$。

输出格式

一行一个整数，表示从起点$(X+0.5,Y+0.5)$最少经过多少次激光。

样例

Sample Input 1

2 3 3
1 2 0
2 1 1

Sample Output 1

1

Sample Input 2

2 3 3
1 2 1
2 1 0

Sample Output 2

0

Sample Input/Output 3

见下发文件。满足$X,Y=20,n=5$。

Sample Input/Output 4

见下发文件。满足$X,Y=109,n=5⋅105$。

样例包链接

数据规模与约定

本题​不使用子任务打包测试​。测试数据按照类型划分，有以下性质：

对于所有的数据，保证n≤5⋅105,0<X,Y≤109。